# Robust 1-bit Compressed Sensing with Iterative Hard Thresholding

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

## Key facts

- Cited by 4 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 12 Oct 2023.

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

- [Exact Recovery of Sparse Binary Vectors from Generalized Linear Measurements](https://mlsanity.com/paper/2502.16008/) (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)
- [Efficient Support Recovery of Mixtures of Sparse Linear Classifiers with Fewer Measurements](https://mlsanity.com/paper/2609.32176/) (2026)

## Abstract (arXiv)

In 1-bit compressed sensing, the aim is to estimate a k-sparse unit vector x∈ Sn-1 within an ε error (in ℓ2) from minimal number of linear measurements that are quantized to just their signs, i.e., from measurements of the form y = Sign(langle a, xrangle). In this paper, we study a noisy version where a fraction of the measurements can be flipped, potentially by an adversary. In particular, we analyze the Binary Iterative Hard Thresholding (BIHT) algorithm, a proximal gradient descent on a properly defined loss function used for 1-bit compressed sensing, in this noisy setting. It is known from recent results that, with tildeO(frackε) noiseless measurements, BIHT provides an estimate within ε error. This result is optimal and universal, meaning one set of measurements work for all sparse vectors. In this paper, we show that BIHT also provides better results than all known methods for the noisy setting. We show that when up to τ-fraction of the sign measurements are incorrect (adversarial error), with the same number of measurements as before, BIHT agnostically provides an estimate of x within an tildeO(ε+τ) error, maintaining the universality of measurements. This establishes stability of iterative hard thresholding in the presence of measurement error. To obtain the result, we use the restricted approximate invertibility of Gaussian matrices, as well as a tight analysis of the high-dimensional geometry of the adversarially corrupted measurements.