Abstract
This paper concerns the problem of 1-bit compressed sensing, where the goal is to estimate a sparse signal from a few of its binary measurements. We study a non-convex sparsity-constrained program and present a novel and concise analysis that moves away from the widely used notion of Gaussian width. We show that with high probability a simple algorithm is guaranteed to produce an accurate approximation to the normalized signal of interest under the $\ell_2$-metric. On top of that, we establish an ensemble of new results that address norm estimation, support recovery, and model misspecification. On the computational side, it is shown that the non-convex program can be solved via one-step hard thresholding which is dramatically efficient in terms of time complexity and memory footprint. On the statistical side, it is shown that our estimator enjoys a near-optimal error rate under standard conditions. The theoretical results are substantiated by numerical experiments.
Introduction
In the field of high-dimensional data acquisition, Compressed Sensing (CS) has revolutionized how we recover sparse signals from limited measurements. Traditionally, CS assumes high-precision measurements. However, real-world hardware often requires quantization to manage power consumption and storage constraints. The most extreme form of this is 1-bit Compressed Sensing, where only the sign of each measurement is recorded: $y_i = \text{sign}(\langle a_i, x \rangle)$.
While 1-bit CS is highly hardware-efficient, it presents significant mathematical challenges. The sign function is non-linear and non-convex, and it inherently destroys the signal's magnitude (norm). Previous recovery methods have typically relied on computationally intensive iterative algorithms or complex geometric analyses involving Gaussian width. This paper introduces a One-Shot Hard Thresholding (OSHT) estimator that achieves near-optimal statistical performance with a fraction of the computational cost.
The One-Shot Hard Thresholding (OSHT) Framework
The proposed OSHT algorithm simplifies the recovery process into a non-iterative, two-step procedure:
- Correlation: Compute a proxy vector $v = A^\top y$, which correlates the sensing matrix $A$ with the binary observation vector $y$.
- Thresholding and Normalization: Apply a hard thresholding operator $\mathcal{H}_k(v)$ that retains only the $k$ largest elements in magnitude while setting others to zero. The result is then normalized to project it onto the unit sphere.
Unlike traditional iterative hard thresholding (IHT) or Lasso-based methods that require multiple passes over the data, OSHT performs a single projection. This "one-shot" approach reduces the time complexity to $O(dn)$, where $d$ is the signal dimension and $n$ is the number of measurements, making it exceptionally efficient for large-scale applications.
Theoretical Contributions
The core of this work is a novel, modular analysis that avoids the traditional Gaussian width framework. The authors decompose the estimation error into two distinct components: one stemming from the sensing matrix (quantization noise) and another from the signal's intrinsic structure.
Key Statistical Guarantees
- Near-Optimal Error Rate: The estimator achieves an error rate of $O(\sqrt{\frac{k \log d}{n}})$, matching the information-theoretic lower bounds for 1-bit CS.
- Sample Complexity: To achieve an estimation error of $\epsilon$, the required number of measurements scales as $n = O(\epsilon^{-2} k \log d)$.
- Robustness to Misspecification: The algorithm is resilient to cases where the user's sparsity estimate $k$ does not perfectly match the true sparsity $s$. Even if $k < s$, the estimator captures the most significant components of the signal.
- Norm Recovery: While standard 1-bit CS only recovers the signal's direction, the authors demonstrate that by incorporating known Gaussian noise (dithering) before quantization, the OSHT framework can accurately estimate the signal's norm as well.
Empirical Validation
The theoretical findings were tested using synthetic datasets where sensing vectors were drawn from a standard Gaussian distribution $N(0, I)$ and signals were $s$-sparse vectors.
In comparative simulations against state-of-the-art Lasso-based 1-bit CS estimators, OSHT demonstrated superior performance. Specifically, in high-dimensional settings (e.g., $d=10,000$), the OSHT error curve decayed significantly faster as the number of measurements increased. Furthermore, OSHT proved more reliable in support recovery—identifying the correct indices of non-zero entries—while maintaining a significantly lower memory footprint and execution time.
Conclusion and Future Work
One-Shot Hard Thresholding provides a highly efficient alternative to iterative solvers for 1-bit compressed sensing. By proving that a simple correlation-and-thresholding step is statistically near-optimal, this work bridges the gap between hardware-friendly quantization and high-performance signal recovery.
Future research directions include extending the theoretical guarantees to non-Gaussian sensing matrices (such as heavy-tailed distributions) and validating the algorithm on physical 1-bit sensing hardware, such as high-speed analog-to-digital converters (ADCs). Additionally, further exploration into automated parameter tuning for the sparsity $k$ would enhance the algorithm's utility in practical scenarios where the exact sparsity is unknown.
Summary updated