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 introduce a remarkably simple "one-shot" algorithm. By using a single hard-thresholding step, the proposed method achieves near-optimal error rates and superior computational efficiency compared to traditional iterative or optimization-based methods, while also providing robust solutions for norm estimation and model misspecification.
Introduction
In high-dimensional statistics, Compressed Sensing (CS) allows for the recovery of a sparse signal $\bar{x} \in \mathbb{R}^d$ from $n$ measurements, where $n \ll d$. While standard CS assumes infinite precision, real-world hardware often necessitates quantization. The most extreme form is 1-bit compressed sensing, where only the sign of each measurement is recorded: $y_i = \text{sign}(\langle a_i, \bar{x} \rangle)$.
This quantization introduces two primary hurdles. First, the sign function eliminates all magnitude information, meaning we can typically only recover the signal's direction (assuming $\|\bar{x}\|_2 = 1$). Second, the resulting optimization problems are often non-convex and computationally demanding, requiring complex iterative solvers that scale poorly with dimension.
The One-Shot Hard Thresholding Algorithm
The authors propose a non-convex sparsity-constrained program to address these challenges: $$\max_{x \in \mathbb{R}^d} y^\top Ax \quad \text{s.t.} \quad \|x\|_0 \le k, \|x\|_2 = 1$$ where $A$ is the sensing matrix and $y$ is the vector of 1-bit observations.
The core innovation is the One-Shot Hard Thresholding (OSHT) estimator. Unlike traditional Iterative Hard Thresholding (IHT) methods, OSHT finds a near-optimal solution in a single pass:
- Proxy Computation: Compute the proxy vector $v = A^\top y$.
- Hard Thresholding: Apply the operator $\mathcal{H}_k(v)$, which retains the $k$ largest elements in magnitude and zeroes out the rest.
- Normalization: Scale the resulting vector to have unit $\ell_2$-norm.
This approach bypasses the need for convergence checks and multiple iterations, drastically reducing the computational footprint to a single matrix-vector multiplication $O(dn)$.
Key Insights and Theoretical Guarantees
The theoretical analysis utilizes a direct probabilistic approach to prove that for Gaussian sensing matrices, the OSHT estimator achieves an error rate of $\|\hat{x} - \bar{x}\|_2 \le \epsilon$ with $n = O(\epsilon^{-2} k \log d)$ samples. This matches the information-theoretic lower bounds for 1-bit CS.
A significant insight is the "One-Shot" advantage: for Gaussian measurements, the very first iteration of a gradient-based hard thresholding approach is statistically sufficient to reach near-optimal accuracy. Furthermore, the algorithm is robust to model misspecification. Even if the user-defined sparsity $k$ differs from the true sparsity, the algorithm remains stable.
Empirical Performance
The paper evaluates OSHT using synthetic datasets with i.i.d. standard Gaussian sensing vectors and sparse signals. The results demonstrate that OSHT's error decays significantly faster than state-of-the-art Lasso-based estimators.
As shown in the simulations, the Lasso estimator's performance tends to degrade as the dimension $d$ increases, whereas the OSHT estimator maintains consistent performance. This scalability makes it particularly suitable for ultra-high-dimensional applications.
Extensions and Robustness
To overcome the "lost magnitude" problem, the authors demonstrate that adding known Gaussian noise (dithering) before quantization allows the OSHT estimator to recover the signal's actual norm. Additionally, the paper provides theoretical thresholds for the minimum signal value required to guarantee perfect recovery of the signal's support set.
Conclusion
One-Shot Hard Thresholding offers a powerful, efficient alternative for 1-bit compressed sensing. While the current theory relies on the Gaussian assumption for sensing matrices, the empirical results suggest broader applicability. Future research may focus on relaxing these distributional assumptions to include heavy-tailed data and refining parameter tuning strategies for $k$ in practical settings.
Summary updated