# Binary Iterative Hard Thresholding Converges with Optimal Number of Measurements for 1-Bit Compressed Sensing

arXiv: https://arxiv.org/abs/2207.03427 · HTML: https://mlsanity.com/paper/2207.03427/

## Key facts

- Cited by 9 papers in the map (data through 14 Oct 2026).
- Builds on 4 of its 24 references that are in the map.
- First posted on arXiv 7 Jul 2022.

## Builds on (most cited first, 4 of 4)

- [One-bit compressive sensing with norm estimation](https://mlsanity.com/paper/1404.6853/) (2014)
- [Support Recovery in Universal One-bit Compressed Sensing](https://mlsanity.com/paper/2107.09091/) (2021)
- [Superset Technique for Approximate Recovery in One-Bit Compressed Sensing](https://mlsanity.com/paper/1910.13971/) (2019)
- [One Scan 1-Bit Compressed Sensing](https://mlsanity.com/paper/1503.02346/) (2015)

## Built on by (most cited first, 9 of 9)

- [Streaming Attention Approximation via Discrepancy Theory](https://mlsanity.com/paper/2502.07861/) (2025)
- [Fundamental Limits of Two-layer Autoencoders, and Achieving Them with Gradient Methods](https://mlsanity.com/paper/2212.13468/) (2022)
- [Improved Support Recovery in Universal One-bit Compressed Sensing](https://mlsanity.com/paper/2210.16657/) (2022)
- [Beyond Discreteness: Sample Complexity Analysis of Straight-Through Estimator for 1-bit Quantization](https://mlsanity.com/paper/2505.18113/) (2025)
- [Exact Recovery of Sparse Binary Vectors from Generalized Linear Measurements](https://mlsanity.com/paper/2502.16008/) (2025)
- [Finite-Sample Performance of Gradient Descent in Logistic Regression with Gaussian Design](https://mlsanity.com/paper/2606.21683/) (2026)
- [Normalized Iterative Hard Thresholding for Tensor Recovery](https://mlsanity.com/paper/2507.04228/) (2025)
- [On the Role of Normalization in Binary Iterative Hard Thresholding for 1-bit Compressed Sensing](https://mlsanity.com/paper/2607.15530/) (2026)
- [The role of parameter Jacobians in the stability of network outputs](https://mlsanity.com/paper/2608.27748/) (2026)

## Abstract (arXiv)

Compressed sensing has been a very successful high-dimensional signal acquisition and recovery technique that relies on linear operations. However, the actual measurements of signals have to be quantized before storing or processing. 1(One)-bit compressed sensing is a heavily quantized version of compressed sensing, where each linear measurement of a signal is reduced to just one bit: the sign of the measurement. Once enough of such measurements are collected, the recovery problem in 1-bit compressed sensing aims to find the original signal with as much accuracy as possible. The recovery problem is related to the traditional "halfspace-learning" problem in learning theory. For recovery of sparse vectors, a popular reconstruction method from 1-bit measurements is the binary iterative hard thresholding (BIHT) algorithm. The algorithm is a simple projected sub-gradient descent method, and is known to converge well empirically, despite the nonconvexity of the problem. The convergence property of BIHT was not theoretically justified, except with an exorbitantly large number of measurements (i.e., a number of measurement greater than maxk10, 2448, k3.5/ε, where k is the sparsity, ε denotes the approximation error, and even this expression hides other factors). In this paper we show that the BIHT algorithm converges with only tildeO(frackε) measurements. Note that, this dependence on k and ε is optimal for any recovery method in 1-bit compressed sensing. With this result, to the best of our knowledge, BIHT is the only practical and efficient (polynomial time) algorithm that requires the optimal number of measurements in all parameters (both k and ε). This is also an example of a gradient descent algorithm converging to the correct solution for a nonconvex problem, under suitable structural conditions.