Source-linked AI summary
Robust 1-bit compressed sensing and sparse logistic regression: A convex programming approach
Yaniv Plan, Roman Vershynin
TL;DR
The paper addresses recovery of high-dimensional structured signals from noisy one-bit or Bernoulli measurements. It uses a single convex program governed by mean width, obtaining sparse-signal guarantees under random and adversarial noise while also identifying scope limits such as unidentifiable signal magnitude.
Problem
Recovering high-dimensional structured signals from limited one-bit measurements requires guarantees for noisy compressed sensing and sparse binomial regression.
Method
The paper uses one convex program over a signal set K, with mean width measuring its effective complexity and an unknown link function allowed in the generalized model.
Results
O(s log(2n/s)) one-bit noisy measurements suffice for effective estimation of s-sparse signals, with guarantees extending to uniform recovery and adversarial noise.
Takeaways & Limitations
The framework connects noisy 1-bit compressed sensing with sparse logistic regression and extends beyond sparsity to general signal sets characterized by mean width.
Takeaways & Limitations
The signal magnitude cannot be recovered without a bound on ∥x∥2, and correlated measurement vectors are treated through eigenvalue conditions on their covariance matrix.
Abstract
from arXiv · showhide
This paper develops theoretical results regarding noisy 1-bit compressed sensing and sparse binomial regression. We show that a single convex program gives an accurate estimate of the signal, or coefficient vector, for both of these models. We demonstrate that an s-sparse signal in R^n can be accurately estimated from m = O(slog(n/s)) single-bit measurements using a simple convex program. This remains true even if each measurement bit is flipped with probability nearly 1/2. Worst-case (adversarial) noise can also be accounted for, and uniform results that hold for all sparse inputs are derived as well. In the terminology of sparse logistic regression, we show that O(slog(n/s)) Bernoulli trials are sufficient to estimate a coefficient vector in R^n which is approximately s-sparse. Moreover, the same convex program works for virtually all generalized linear models, in which the link function may be unknown. To our knowledge, these are the first results that tie together the theory of sparse logistic regression to 1-bit compressed sensing. Our results apply to general signal structures aside from sparsity; one only needs to know the size of the set K where signals reside. The size is given by the mean width of K, a computable quantity whose square serves as a robust extension of the dimension.
1. Introduction
The paper develops convex-programming guarantees for noisy 1-bit compressed sensing and generalized linear models, using mean width to quantify signal-set complexity. It covers stochastic and adversarial noise, fixed and uniform recovery, and sparse signals with O(s log(2n/s)) measurements.
- Generalized models: The same framework applies to generalized linear models with an unknown link function, requiring only measurement vectors and observed responses.The model includes sparse logistic regression as a special case.
- Main results: One convex program provides theoretical accuracy guarantees for noisy 1-bit compressed sensing using a polynomial-time solver.The program is convex when the signal set K is convex.
- Signal complexity: O(w(K)^2) one-bit noisy measurements suffice for effective estimation when signals lie in a set K.The target is the normalized signal because one-bit measurements lose magnitude information.
- Noise robustness: Uniform recovery extends the guarantees to all signals in K and worst-case noise modeled by a bounded fraction of adversarial bit flips.The uniform result is based on random hyperplane tessellations.
- Main results: O(s log(2n/s)) one-bit noisy measurements suffice to effectively estimate an s-sparse signal in R^n.This follows from the mean-width estimate for sparse signal sets.
2. Mean width and sparsity
Mean width measures the average directional width of a set, using either spherical directions or an equivalent Gaussian formulation. The paper uses Gaussian mean width to analyze signal structure.
- Mean width: Mean width is presented as a geometric quantity with basic properties and examples relevant to sparsity.The section introduces the geometric meaning of mean width before applying it to sparse signal sets.
- Mean width: Mean width is the average width of K over directions η uniformly distributed on the unit sphere.The width in direction η is the smallest slab width between parallel hyperplanes with normal η that contains K.
- Figure 1: Figure 1 illustrates the width of K in a direction η with a dashed line.The dashed line represents the directional width described in the text.
- Mean width: Gaussian mean width replaces spherical averaging with a standard Gaussian vector g.The paper uses the Gaussian version as its definition of mean width.
- Mean width: The spherical and Gaussian versions of mean width are proportional through the factor E ∥g∥2.Rotation invariance gives w(K) = E ∥g∥2 · ˜w(K), and E ∥g∥2 is comparable to √n.
1. The mean width is invariant under orthogonal transformations and translations.
Mean width has invariance, dimension, and robustness properties that make it suitable for convex signal-set analysis. For sparse vectors, its square scales as s log(2n/s), close to the sparse set’s effective dimension.
- Invariance and effective dimension: Mean width is invariant under taking the convex hull, so convex relaxation preserves the signal set’s effective dimension.This property is highlighted as useful in compressed sensing, where non-convex programs are commonly relaxed to convex ones.
- Basic properties: Mean width is related to Euclidean diameter and distance from the origin through bounds that become equalities for origin-symmetric sets.The section records inequalities involving diam(K), dist(0,K), and suprema of Gaussian inner products.
- Invariance and effective dimension: w(K)^2 serves as an effective dimension that is bounded by linear algebraic dimension and changes continuously under small perturbations.The paper describes this effective dimension as robust because small perturbations of K cause small changes in w(K)^2.
- Computation and examples: Mean width can be computed using tools including Dudley’s inequality, Sudakov minoration, Gaussian concentration, Slepian’s inequality, and generic chaining.The sparse-set estimate uses Gaussian concentration for the upper bound and Sudakov minoration for the lower bound.
- Sparsity: S_n,s consists of vectors in R^n with at most s nonzero entries and Euclidean norm at most 1.The set is the sparse signal structure analyzed in the paper’s example.
- Sparsity: For sparse vectors, w^2(S_n,s) is bounded above and below by constant multiples of s log(2n/s).This makes the mean-width-based effective dimension closer to the sparse manifold dimension s than to the ambient dimension n.
3. Applications to sparse signal models
The paper specializes its general convex-programming framework to approximately sparse vectors, 1-bit compressed sensing, sparse logistic regression, and related measurement models. These applications retain efficient convex estimation while providing sparse-signal recovery guarantees under substantial noise and correlated designs.
- Sparse signal models: conv(Sn,s) ⊂ Kn,s ⊂ 2 conv(Sn,s) makes Kn,s a convex relaxation representing approximately sparse or compressible vectors.Exact sparsity is nonconvex, whereas the relaxed set supports a polynomial-time solver.
- Sparse signal models: The convex program (3.2) estimates exactly or approximately sparse signals without requiring the estimate to lie on the unit sphere.Its accuracy and the unit-norm assumption on x imply that the recovered norm is approximately one.
- 1-bit compressed sensing: m = Cδ−2s log(2n/s) measurements suffice for the stated sparse recovery guarantee in the noiseless 1-bit case.The bound is described as similar to results available in [23].
- 1-bit compressed sensing: The recovery error matches the minimax error for unquantized compressed sensing up to a constant, indicating essentially no loss from single-bit quantization.The paper also states that noise can exceed the magnitude of the linear measurements while estimation remains possible.
- Extensions and related models: O(s log(2n/s)) one-bit noisy measurements effectively estimate s-sparse signals, while the framework also covers adversarial noise, uniform results, sparse logistic regression, low-rank matrices, and correlated designs.For correlated Gaussian measurements, the required measurement count scales by κ(Σ), and the error bound scales by λmin(Σ)−1.
4. Deducing Theorems 1.1 and 1.3 from concentration inequalities
Theorems 1.1 and 1.3 follow by showing that the convex-program objective is large at the true signal and uniformly controlled away from it, including adversarial and random noise.
- Theorem 1.1: The estimator is near the true signal because its objective cannot remain large for candidates far from the truth.The solution achieves at least the true signal’s objective because the true signal is feasible.
- Theorem 1.1: Proposition 4.2 supplies the concentration inequality that directly yields Theorem 1.1.The proof applies the inequality to z = ˆx − x and selects t to complete the error bound.
- Theorem 1.3: Uniform recovery requires concentration simultaneously over candidate differences, signals, and measurement vectors with small Hamming distance from the observations.This is the content of Proposition 4.3 and is deeper than the fixed-signal concentration result.
- Noise models: Random bit flips modify the error bound by dividing it by 2p −1.The same proof remains valid for independent flips with P{ξi = 1} = p.
- Noise models: Additive Gaussian noise before quantization is represented by augmenting each measurement vector and signal with one extra coordinate.This reduction returns the model to the original 1-bit framework after adjusting K.
5. Concentration: proof of Proposition 4.2
Proposition 4.2 is proved by combining symmetrization, Gaussian-process concentration, and Gaussian rotational symmetry to control the objective uniformly.
- Core tools: The proof uses symmetrization and Gaussian concentration as its main probability tools.These standard Banach-space techniques convert the objective’s fluctuations into a Gaussian-process deviation problem.
- Gaussian concentration: The Gaussian concentration theorem controls centered Gaussian processes indexed by a finite set.The theorem extends to separable metric sets through approximation.
- Symmetrization: Rademacher signs preserve the distribution of the Gaussian measurement vectors after multiplication by the observed signs.This follows from symmetry and rotational invariance of the Gaussian distribution.
- Concentration step: The resulting expectation bound is supplemented by a deviation inequality from the second symmetrization estimate and Gaussian concentration.Choosing r = t√m/2 completes the proof of Proposition 4.2.
6. Concentration: proof of Proposition 4.3
Proposition 4.3 establishes uniform concentration by combining covering nets, mean-width bounds, sparse-coordinate control, and random hyperplane tessellation results.
- Geometric ingredients: Sudakov minoration bounds the covering number of K ∩ S^{n−1} through the mean width w(K).The net satisfies log |Nδ| ≤ Cδ^-2w(K)^2.
- Geometric ingredients: Random hyperplane tessellations make sign(Ax) an almost-isometric embedding of K ∩ S^{n−1} under geodesic and Hamming distances.This controls changes in sign patterns for nearby signals.
- Uniform control: Under m ≥ Cδ^-6w(K)^2, the auxiliary events needed for uniform control hold with high probability.Lemma 6.4 provides bounds on the net, sign-pattern deviations, and deviations of sums.
- Uniform control: The proof approximates each signal by a net point and transfers concentration from the net to all signals and candidate differences.The argument uses bounds on nearby sign-pattern changes and the inclusion K − K ⊂ 2B_n.
- Adversarial noise: Allowing τm adversarial bit flips requires enlarging the sign-deviation parameter from 2mδ to τm + 2mδ.This modification completes Proposition 4.3 for arbitrary permitted flips.
7. Discussion
The discussion positions noisy 1-bit compressed sensing as an emerging theory, presents a polynomial-time convex solver, and connects it to sparse binomial regression.
- Contributions: The paper proposes a polynomial-time convex program for noisy 1-bit compressed sensing with theoretical performance guarantees.The discontinuity of 1-bit measurements creates distinctive mathematical challenges.
- Connections: The work connects 1-bit compressed sensing with sparse binomial regression and derives new results for that problem.This connection extends the paper’s scope beyond the original 1-bit formulation.
- Open questions: A bridge to finer quantization remains open, with 2-bit compressed sensing suggested as one example.The paper contrasts its elegant 1-bit setup with compressed-sensing results using substantially finer quantization.