Source-linked AI summary
One-bit compressive sensing with norm estimation
Karin Knudson, Rayan Saab, Rachel Ward
TL;DR
One-bit linear measurements lose signal-norm information, so the paper asks how to recover sparse signals without assuming unit norm. It introduces affine shifts and two norm-recovery methods, obtaining universal sparse-recovery guarantees and direct annulus-based norm estimation with m ≳ R^4r^-2δ^-2 measurements.
Problem
One-bit linear measurements reveal direction but no magnitude, forcing prior recovery methods to assume a known normalization.
Method
The paper uses affine measurements with Gaussian vectors and develops augmented convex programming plus an empirical distribution function estimator based on negative-measurement proportions.
Results
m ≳ R^4r^-2δ^-2 binary measurements suffice to estimate ∥x∥2 within additive error δ for fixed x in r ≤ ∥x∥2 ≤ R, while sparse recovery has universal high-probability guarantees.
Takeaways & Limitations
Affine shifts incorporate norm estimation into one-bit compressive sensing, and one measurement set can support accurate recovery uniformly over sparse vectors within a known norm bound.
Takeaways & Limitations
Both methods require a known upper norm bound, EDF additionally requires a known lower bound, and the convex-programming theorem relies on independently random shifts.
Abstract
from arXiv · showhide
Consider the recovery of an unknown signal ${x}$ from quantized linear measurements. In the one-bit compressive sensing setting, one typically assumes that ${x}$ is sparse, and that the measurements are of the form $\operatorname{sign}(\langle {a}_i, {x} \rangle) \in \{\pm1\}$. Since such measurements give no information on the norm of ${x}$, recovery methods from such measurements typically assume that $\| {x} \|_2=1$. We show that if one allows more generally for quantized affine measurements of the form $\operatorname{sign}(\langle {a}_i, {x} \rangle + b_i)$, and if the vectors ${a}_i$ are random, an appropriate choice of the affine shifts $b_i$ allows norm recovery to be easily incorporated into existing methods for one-bit compressive sensing. Additionally, we show that for arbitrary fixed ${x}$ in the annulus $r \leq \| {x} \|_2 \leq R$, one may estimate the norm $\| {x} \|_2$ up to additive error $δ$ from $m \gtrsim R^4 r^{-2} δ^{-2}$ such binary measurements through a single evaluation of the inverse Gaussian error function. Finally, all of our recovery guarantees can be made universal over sparse vectors, in the sense that with high probability, one set of measurements and thresholds can successfully estimate all sparse vectors ${x}$ within a Euclidean ball of known radius.
1 Introduction
One-bit linear measurements recover signal direction but lose magnitude, motivating affine shifts that enable norm estimation. The paper develops two recovery strategies with uniform sparse-signal guarantees and distinct assumptions on the shifts.
- Measurement model: The proposed affine model uses Gaussian measurement vectors and either random Gaussian shifts or fixed thresholds selected using a lower norm bound.The vectors are drawn once and then fixed; the fixed-threshold model targets norm estimation for signals in a prescribed annulus.
- Motivation: One-bit measurements sign(⟨a_i, x⟩) provide no information about the magnitude of x, so prior guarantees typically require known normalization.The paper addresses this limitation using affine measurements sign(⟨a_i, x⟩ + b_i).
- Recovery methods: The augmented convex-programming method embeds affine measurements as one-bit linear measurements in n+1 dimensions and applies an existing one-bit recovery method.The augmented signal is ˜x = (x, 1), after which the recovered scale is used to estimate x and its norm.
- Recovery methods: The empirical distribution function method estimates the norm from the fraction of negative measurements using the Gaussian distribution of ⟨a_i, x⟩ and one inverse Gaussian error-function evaluation.For arbitrary fixed x with r ≤ ∥x∥2 ≤ R, the method uses m ≳ R^4r^-2δ^-2 measurements for additive error δ.
- Guarantees and scope: The two methods provide universal high-probability sparse-recovery guarantees, with error scaling ∥x − x♯∥2 ≲ 1/m^1/5 and, for EDF in some regimes, ∥x − x♯∥2 ≲ 1/m^1/2.Both methods assume a known upper norm bound, while EDF additionally assumes a known lower norm bound.
2 Preliminaries
The preliminaries establish the paper’s vector, norm, sparsity, and Gaussian notation, then introduce geometric and inverse-error-function lemmas used in the main results.
- Notation: Vectors use bold italics, coordinates use plain text, and the ℓ1 and ℓ2 norms are defined coordinatewise.The ith coordinate of x is written x_i; the supplied passage begins the corresponding norm definitions.
- Notation: The number of nonzero coordinates is denoted by ∥x∥0, and Gaussian variables are written X ∼ N(µ, σ2).The support size notation quantifies sparsity, while the Gaussian notation specifies mean and variance.
- Auxiliary lemmas: A geometric lemma bounds the norm difference between two vectors under constraints on their norms and scalar parameters.Its proof uses the reverse triangle inequality and bounds involving α, η, t1, and t2.
- Auxiliary lemmas: A subsequent lemma analyzes variation in a function involving the inverse Gaussian error function.The surrounding proof develops derivative-based bounds for the function and its inverse-error-function dependence.
3 Main results
The paper develops two one-bit affine-measurement methods for estimating an unknown signal’s norm, with or without its direction. It provides recovery guarantees for random shifts, fixed-shift empirical distribution estimation, and universal sparse-vector recovery.
- Overview: Two methods estimate ∥x∥2 from affine one-bit measurements: augmented convex programming and an empirical distribution function estimator.The first can recover norm and direction together; the second directly estimates the norm using a fixed shift.
- 3.2 Estimating ∥x∥2 using the empirical distribution function: The empirical distribution estimator requires only one inverse Gaussian error-function evaluation and is computationally cheaper than convex programming, but more sensitive to parameter uncertainty.Its statistical analysis uses the DKW inequality and applies first to fixed signals in an annulus.
- 3.1 Augmented convex programming: Random Gaussian shifts reduce augmented recovery to standard one-bit compressed sensing on the vector (x, τ).The augmented vector has an effective structural constraint bounded by √s + 1, enabling existing recovery guarantees.
- 3.1 Augmented convex programming: The augmented convex program provides uniform recovery guarantees for effectively sparse vectors under affine one-bit measurements.The theorem assumes Gaussian measurement vectors, Gaussian shifts, bounded norm, and a prescribed measurement condition.
- 3.2 Estimating ∥x∥2 using the empirical distribution function: A fixed shift τ converts the fraction of negative signs into an empirical Gaussian distribution value, which can be inverted to estimate ∥x∥2.The estimator uses the Gaussianity of ⟨a_i, x⟩ and the empirical cumulative distribution function, with accuracy analyzed by the DKW inequality.
- 3.2 Estimating ∥x∥2 using the empirical distribution function: Universal norm estimation extends the fixed-signal result to all s-sparse vectors with r ≤ ∥x∥2 ≤ R using one random measurement set.The paper also combines norm estimation with a directional estimate to recover x itself.
4 Numerical Experiments
The experiments compare EDF and PVaug norm-recovery methods across measurement counts and threshold choices. PVaug performs better in the plotted measurement regime, while EDF can be slightly better at its optimal threshold and PVaug is more robust to threshold misspecification.
- Measurement count: PVaug outperforms EDF across the plotted measurement ratios, but requires more computation time.Figure 1 reports average errors for both signal and norm recovery.
- Threshold choice: Both methods show poor recovery when the threshold τ is too small or too large relative to ∥x∥2.These extremes produce U-shaped error curves because the negative-measurement proportion becomes uninformative.
- Threshold choice: At the optimal τ, EDF may slightly outperform PVaug, whereas PVaug error increases more gradually as τ moves away from ∥x∥2.Figure 2 varies τ relative to the signal norm with m/n=6.
5 Conclusions
The paper shows that affine one-bit measurements can recover signal norms, unlike homogeneous one-bit measurements, and develops uniform recovery guarantees under norm information. It presents randomized-shift recovery of both norm and direction alongside deterministic-shift norm estimation.
- Main conclusion: Affine measurements sign(⟨a_i,x⟩+b_i) enable norm recovery that is impossible from homogeneous one-bit measurements sign(⟨a_i,x⟩).The measurement vectors have i.i.d. standard Gaussian entries and the shifts are known and nonzero.
- Main conclusion: The methods provide uniform high-probability recovery guarantees when sufficient measurements and prior norm bounds are available.The required prior information is an upper bound, or both lower and upper bounds, depending on the method.