Source-linked AI summary
One-bit compressed sensing with non-Gaussian measurements
Albert Ai, Alex Lapanowski, Yaniv Plan, Roman Vershynin
TL;DR
Prior one-bit compressed-sensing results rely on Gaussian measurements, while non-Gaussian measurements can make distinct signals indistinguishable. This paper uses convex programming to recover approximately sparse, not extremely sparse signals from sub-gaussian one-bit measurements; it also establishes recovery for sub-gaussian distributions close to Gaussian without the spread condition.
Problem
Gaussian one-bit recovery results do not generally extend to non-Gaussian measurements, for which distinct signals can produce indistinguishable signs.
Source: §1 · pp. 2–3Method
The paper reconstructs signals by convex programming from one-bit measurements with independent sub-gaussian coordinates.
Source: §1 · p. 3, §1.1 · p. 3Results
Approximately sparse signals that are not extremely sparse can be accurately recovered under general sub-gaussian measurements, while distributions close to Gaussian in total variation allow recovery without the spread assumption.
Source: §1 · p. 3, §1.1 · p. 4Takeaways & Limitations
The results establish non-Gaussian one-bit recovery for spread signals, with a separate near-Gaussian case that does not require the spread condition.
Source: §1.1 · p. 4The stated framework assumes the signal set lies in the unit Euclidean ball and measurement vectors have independent sub-gaussian coordinates.
Source: §1.1 · p. 3
Abstract
from arXiv · showhide
In one-bit compressed sensing, previous results state that sparse signals may be robustly recovered when the measurements are taken using Gaussian random vectors. In contrast to standard compressed sensing, these results are not extendable to natural non-Gaussian distributions without further assumptions, as can be demonstrated by simple counter-examples. We show that approximately sparse signals that are not extremely sparse can be accurately reconstructed from single-bit measurements sampled according to a sub-gaussian distribution, and the reconstruction comes as the solution to a convex program.
1. Introduction
One-bit measurements retain only sign information, and Gaussian-measurement recovery results do not extend generally to non-Gaussian measurements. The paper shows that convex programming can recover signals under sub-gaussian measurements when they are not extremely sparse, with a separate result for distributions close to Gaussian.
1. Introduction
- One-bit measurements encode signs rather than magnitudes, so the reconstruction target is the signal's direction.The signal may therefore be assumed to have unit Euclidean norm.Source: §1 · p. 1
- Prior one-bit work showed robust recovery from Gaussian measurements: recovered sparse support using O(s log n) adaptive measurements, [4] achieved fixed-constant relative error with O(s log n) Gaussian measurements, and [7] [8] used convex programming.Source: §1 · p. 2
- With Bernoulli measurement coordinates, a counterexample gives two different signals with identical one-bit measurements, even with infinitely many measurements.This illustrates why non-Gaussian recovery does not follow without further conditions.Source: §1 · pp. 2–3
1.1. Main Results.
- Approximately sparse, not extremely sparse signals can be accurately recovered from general sub-gaussian one-bit measurements by convex programming, even with a constant fraction of randomly flipped bits.The recovery error has an additive dependence on the signal's infinity norm; accurate recovery is still possible when nearly half the bits are flipped.Source: §1 · p. 3, §1.1 · p. 4
- The paper also establishes a version of its result for a generalized linear model in which binary measurements have conditional means determined by a response function θ.The response function may be unknown or unspecified, subject to the stated smoothness and parameter assumptions.Source: §1.1 · p. 5
- For sub-gaussian measurement distributions close to Gaussian in total variation, the paper establishes recovery without the signal-spread assumption.The stated motivation is that the Gaussian conclusions hold for all signals without dependence on ∥x∥∞.Source: §1.1 · p. 5
2. General proof structure
The proof separates recovery into concentration of a random objective and control of its expectation. When that expectation is sufficiently close to the Gaussian case, the objective’s maximizer approximates the signal with high probability.
2. General proof structure
- The objective concentrates uniformly around its expectation for any choice of θ, with the bound depending on the sub-Gaussian norm of the measurements.The objective’s distribution depends on the measurement vectors and θ.Source: §2 · p. 6
- For sub-Gaussian measurements, the expected objective need only approximately match the Gaussian case under suitable conditions on the signal and θ.In the Gaussian case, the expectation is proportional to the inner product of the signal and a candidate.Source: §2 · pp. 6–7
- The recovery argument reduces to showing that the expected objective distinguishes candidates near the signal, so its maximizer is accurate.Lemma 2.2 turns a uniform expectation condition into a high-probability recovery guarantee.Source: §2 · p. 7
3. Proof of Theorem 1.3
The proof compares the expected objective under sub-Gaussian and Gaussian measurements. A two-variable Berry–Esseen bound controls the discrepancy, which is then used to establish the recovery guarantee for the generalized linear model.
3. Proof of Theorem 1.3
- For Gaussian measurements, the expected objective equals λ⟨x, x′⟩; for sub-Gaussian measurements, the proof establishes an approximate equality under conditions on x and θ.The comparison is the ingredient used to control the approximation error in the recovery argument.Source: §3 · p. 7
- The sub-Gaussian expectation differs from its Gaussian counterpart by at most C(τ2 + τ3) E a4∥x∥∞.The bound applies uniformly over z in the unit ball and follows from a two-variable Lindeberg replacement argument.Source: §3 · p. 8
- Theorem 1.3 follows by bounding α in the recovery lemma using the right-hand side of Equation (3.2).The proof uses the sub-Gaussian fourth-moment bound E a4 ≤16κ4.Source: §3 · p. 8
4. Proof of Theorem 1.1
The proof of Theorem 1.1 establishes geometric conditions that make the expected objective informative for the signal, then applies the general recovery argument. A separate concentration proof controls deviations of the random objective from its expectation.
4. Proof of Theorem 1.1
- The proof applies the recovery lemma after bounding α; in the bit-flip model, the expected objective and its comparison scale by 2 −p.The theorem proof handles the noiseless case first and then adjusts the argument for random bit flips.Source: §4 · pp. 8–9
- The proof reduces the expected-objective comparison to ⟨vx, x⟩≈λ and ∥vx∥2 ≲λ, which place vx near the signal’s direction.These two geometric constraints imply the approximation used in Proposition 4.1.Source: §4 · p. 9
- Under a bound on ∥x∥∞, Lemma 4.5 controls ∥vx∥∞, supporting the geometric argument that establishes the expected-objective comparison.The proof normalizes vx and uses the coordinate bound together with a lower bound on ∥vx∥2.Source: §4 · pp. 10–11
4.1. Concentration: Proof of Proposition 2.1.
- The concentration proof symmetrizes the deviation process, then converts moment bounds into tail bounds to control deviations of the objective.The symmetrization step gives both an expectation bound and a deviation inequality.Source: §4.1 · p. 12
- A contraction argument replaces the sub-Gaussian measurement entries with Gaussian variables to obtain the needed moment bound.The proof applies the contraction principle to independent symmetric variables and a matrix seminorm.Source: §4.1 · pp. 12–13
5. Conclusion
The paper establishes that one-bit compressed sensing can work with non-Gaussian measurements when signals are not extremely sparse. This gives the first theoretical one-bit compressed-sensing results specifically allowing non-Gaussian measurements.
5. Conclusion
- One-bit compressed sensing with Bernoulli measurements is infeasible for extremely sparse signals, unlike standard compressed sensing.The conclusion contrasts this boundary with recovery results for signals that are sparse but not overly sparse.Source: §5 · p. 13
- Signals that are sparse but not overly sparse may be recovered from Bernoulli or, more generally, sub-Gaussian one-bit measurements.The conclusion identifies these as the first theoretical one-bit compressed-sensing results specifically allowing non-Gaussian measurements.Source: §5 · p. 13
- The paper’s stated novelty is theoretical one-bit compressed sensing that specifically permits non-Gaussian measurements.The supported scope includes Bernoulli measurements and the broader sub-Gaussian class for signals that are not overly sparse.Source: §5 · p. 13
Appendix
The appendix proves supporting bounds using Lindeberg replacement and Taylor expansions. It applies these arguments to sign and smooth noise models under total-variation closeness to Gaussian measurements.
5.1. Proof of Lemma 3.1.
- The proof of Lemma 3.1 replaces measurement variables with Gaussian variables one at a time, using Taylor expansion and cancellation through second order.The remainder bounds use independence, |z_i|≤1, and moment bounds for a.Source: §5.1 · p. 14
5.2. Total variation: sign function.
- For the sign-function case, the proof uses quadratic Taylor remainders and total-variation closeness to compare expectations under a and Gaussian measurements.The zeroth- and first-order terms cancel because both variables have mean zero.Source: §5.2 · pp. 15–16
- In the noiseless setting, assuming ∥a−g∥TV≤ε, Theorem 5.1 states that for each β>0, the solution bx to (1.2) satisfies its conclusion with probability at least 1−4e^(−β²).Source: §5.2 · p. 15
5.3. Total variation: smooth noise model.
- For the smooth-noise case, Lindeberg replacement bounds the expectation difference using second-order remainders and sixth-moment terms.The proof applies when the noise function is twice differentiable and uses total-variation closeness.Source: §5.3 · pp. 17–19
- With ∥a−g∥TV≤ε and θ(t)∈C2, Theorem 5.4 states that for each β>0, the solution bx to (1.2) satisfies a condition with probability at least 1−4e^−β².Source: §5.3 · p. 17