Source-linked AI summary
One-bit compressed sensing by linear programming
Yaniv Plan, Roman Vershynin
TL;DR
The paper addresses whether sparse signals can be recovered accurately and computationally from measurements containing only one bit each. It replaces a theoretically useful non-convex formulation with a simple convex program and proves uniform recovery from O(s log^2(n/s)) random measurements, including effectively sparse signals. The argument connects recovery to random hyperplane tessellations, while the measurement-complexity bound remains one logarithmic factor from the classical benchmark.
Problem
Classical compressed sensing assumes infinite bit precision, motivating the question of how many bits per measurement suffice for tractable and accurate sparse recovery.
Method
The paper uses a simple convex program whose analysis is connected to an equivalent geometric problem involving random hyperplane tessellations.
Results
m = O(s log^2(n/s)) one-bit random measurements yield arbitrarily accurate uniform recovery of every s-sparse vector with high probability, and the result extends to effectively sparse vectors.
Takeaways & Limitations
One-bit measurements can support universal recovery of sparse and approximately sparse signals using a computationally tractable method, with measurement count nearly linear in sparsity.
Abstract
from arXiv · showhide
We give the first computationally tractable and almost optimal solution to the problem of one-bit compressed sensing, showing how to accurately recover an s-sparse vector x in R^n from the signs of O(s log^2(n/s)) random linear measurements of x. The recovery is achieved by a simple linear program. This result extends to approximately sparse vectors x. Our result is universal in the sense that with high probability, one measurement scheme will successfully recover all sparse vectors simultaneously. The argument is based on solving an equivalent geometric problem on random hyperplane tessellations.
1. Introduction
One-bit compressed sensing asks whether sparse signals can be recovered accurately and tractably when measurements retain only their signs. The paper proposes a convex-programming approach that achieves uniform recovery with nearly optimal measurement complexity, extending to effectively sparse signals and selected rotationally invariant ensembles.
- One bit per measurement is sufficient for tractable and accurate sparse recovery despite discarding measurement magnitudes.The motivation is to determine the bit precision needed when classical compressed sensing assumes infinite precision.
- The recovery method modifies a convex program so that the estimate remains sign-consistent and avoids the zero solution through a linear normalization constraint.The sign constraints encode measurement consistency, while the normalization constraint is linear and makes the program representable as a linear program.
- With high probability, one random measurement scheme succeeds uniformly for all signals in the stated sparsity class.The theorem assumes an m × n matrix with independent standard normal entries and gives probability at least 1−C exp(−cδm).
- The guarantee extends from exactly sparse signals to effectively sparse signals measured by (∥x∥1 / ∥x∥2)^2.Effective sparsity is a real-valued robust extension of ∥x∥0 that accommodates approximately sparse vectors.
- m = O(s log^2(n/s)) one-bit random measurements suffice for arbitrarily accurate recovery of every s-sparse vector with high probability.The implicit factor depends on the desired accuracy level δ; more precisely, m ∼δ^-5s log^2(n/s) up to an absolute constant factor.
- The result is unchanged for independently sampled rows from any rotationally invariant distribution, but not for Bernoulli measurements.For Bernoulli matrices, distinct fixed signals can produce identical sign measurements for every number of measurements.
2. Strategy of the proof
The proof separates recovery into a geometric one-bit tessellation result and a convex-program sparsity result, then combines them to establish accurate recovery.
- Proof strategy: The constraint ∥Ax′∥1 = m is, in expectation, equivalent to ∥x′∥2 = 1 up to the constant c for Gaussian measurements.This motivates analyzing the simpler non-convex program before returning to the tractable convex formulation.
- Geometric ingredient: The non-convex program accurately recovers effectively sparse signals when sign consistency and unit-norm conditions hold.The relevant signal class satisfies ∥x∥1 / ∥x∥2 ≤√s, and the result holds uniformly with probability at least 1 −C exp(−cδm).
- Geometric ingredient: Matching measurements imply Euclidean error at most δ for the normalized signals under the hyperplane-tessellation result.The key implication is sign(Aˆx) = sign(Ax) ⇒ ∥ˆx −x∥2 ≤δ.
- Proof strategy: The analysis uses two ingredients: a geometric theorem for a non-convex normalized program and a theorem showing the convex solution preserves effective sparsity.The non-convex program replaces ∥Ax′∥1 = m with ∥x′∥2 = 1, while the convex program's solution is shown to remain effectively sparse.
- Convex-to-geometric reduction: The convex program preserves effective sparsity once m ≥Cs log(n/s), allowing the geometric theorem to be applied to its solution.This is the second main ingredient and holds uniformly with probability at least 1 −C exp(−cm).
- Conclusion: The resulting recovery guarantee uses m log(2n/s) log(2n/m + 2m/n) measurements in the proof's quantitative bound.The proof combines effective-sparsity preservation with the geometric one-bit recovery result.
3. Geometry of signal sets
The geometric analysis focuses on effectively sparse signals, representing their feasible set through convexification and controlling its metric entropy with sparse approximations and nets.
- Signal sets: The set K_n,s consists of effectively s-sparse signals and is the central geometric object in the analysis.The arguments rely on entropy bounds for this set and its relationship to sparse unit vectors.
- Convexification: K_n,s is convex, unlike S_n,s, and satisfies conv(S_n,s) ⊂K_n,s ⊂2 conv(S_n,s).Thus K_n,s acts as a controlled convexification of the set of s-sparse unit vectors.
- Metric entropy: An ε-net approximates every point in a set within Euclidean distance ε, and N(K, ε) denotes the minimum net cardinality.The metric entropy is log N(K, ε).
- Sparse approximation: Vectors in K_n,s can be approximated by t-sparse vectors when t is sufficiently larger than s relative to the target accuracy.The sparse-net construction selects the t largest coefficients and controls the Euclidean tail.
- Metric entropy: The entropy of sparse unit vectors is bounded using coordinate-subspace decompositions and volumetric nets.Each s-dimensional coordinate subspace admits an ε-net of cardinality at most (3/ε)^s, and the nets are combined across supports.
- Metric entropy: The entropy bounds for K_n,s follow by combining convexification, sparse approximation, and nets for sparse vectors.The construction splits into accuracy regimes and uses t := 4s/ε^2 in the fine-scale approximation regime.
4. Random hyperplane tessellations
The paper studies random hyperplane tessellations of effectively sparse points on the sphere, asking how many hyperplanes make every cell small. It proves uniform separation through covering arguments, center–tail decomposition, and concentration.
- Problem setting: Random hyperplane tessellations partition K by intersecting K with randomly oriented half-spaces, with cell geometry as the central object of study.Here K is a subset of the sphere, including the effectively sparse set K = S^{n−1} ∩ √sB_1^n.
- Problem setting: The target question is how many random hyperplanes ensure that all cells of the tessellation of K have small diameter.The paper focuses on K = S^{n−1} ∩ √sB_1^n and a prescribed accuracy level δ.
- Main geometric result: m = O(s log(n/s)) hyperplanes suffice with high probability to make every tessellation cell have diameter at most δ.Theorem 4.1 gives probability at least 1 − 2 exp(−δm).
- Proof strategy: The proof reduces uniform control over all distant point pairs to separating an ε-net of centers and controlling the corresponding tails.Each x ∈ K is decomposed as x = x0 + x′, where x0 belongs to an ε-net and x′ is a tail with controlled effective sparsity.
- Separation of centers: For net centers separated by more than δ, at least δm/24 hyperplanes separate them under the stated high-probability event.The result follows from one-hyperplane separation, a union bound over net pairs, and concentration.
- Putting centers and tails together: After incorporating the tails, the full pair x, y has a separating set I0 = Iδ/24(x, y) with |I0| ≥ δm/48.The center separation and uniform tail control are combined to obtain the separation required by the main geometric theorem.
5. Effective sparsity of solutions
The section proves that solutions of the convex program have controlled Euclidean norm uniformly over all signals, which supports effective-sparsity guarantees. The proof reduces possible solutions to finitely many linear-program vertices and applies Gaussian concentration with a union bound.
- Proof strategy: Theorem 2.3 is proved by combining a lower bound on ∥ˆx∥2 with an upper bound on ∥x∥2.These bounds are supplied by Lemmas 5.1 and 5.4.
- Uniform norm control: Lemma 5.1 gives, with probability at least 1 − C exp(−cm log(2n/m + 2m/n)), a uniform Euclidean-norm guarantee for the program’s solution.The guarantee holds uniformly for all signals x ∈ R^n.
- Uniform probability: A union bound over the exp(Cm log(2n/m + 2m/n)) possible candidates yields the stated uniform probability estimate.For each fixed candidate, Gaussian concentration provides the required lower-tail control.
- Vertex reduction: The linear program attains its solution at a polytope vertex, and Gaussian general position makes that solution unique with probability 1.Characterizing vertices reduces the space of possible solutions.
- Vertex reduction: Vertex constraints imply that each candidate solution is indexed by a support T and measurement subset Ω with |T| = |Ω| + 1.The equality count supplies the relation between the support size and the active measurement constraints.
Appendix. Uniform concentration inequality.
The appendix establishes concentration for fixed signals and extends it uniformly to effectively sparse signals through covering, approximation, and union-bound arguments. The resulting bounds require a measurement count scaling with the effective sparsity and logarithmic ambient-dimension factor.
- Fixed-signal concentration: For a fixed vector x, concentration follows because the Gaussian inner products are independent random variables controlled by standard inequalities.The proof normalizes ∥x∥2 = 1 and uses sub-Gaussian estimates.
- Uniform extension: The stronger result is uniform over all effectively sparse signals x by covering Kn,s ∩ S^n−1 with a t/4-net.Each signal is approximated by a nearby net point before applying concentration.
- Uniform extension: The approximation argument controls the difference between a signal and its net representative using both ℓ2 and ℓ1 bounds.The supplied proof uses ∥x − x̄∥2 ≤ t/4 and ∥x − x̄∥1 ≤ 2√s.
- Probability bounds: 64s/t^2 is used as the relevant sparsity level for a restricted-isometry bound in controlling one concentration term.The proof combines this estimate with a Gaussian concentration bound.
- Probability bounds: The bound P{R1 > t/4} ≤ C exp(−cmt^2) holds when m ≥ Ct^−4s log(2n/s).This follows from a net cardinality estimate and a union bound.