# One-bit compressive sensing with norm estimation

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

## Key facts

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

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

- [High Dimensional Statistical Estimation under Uniformly Dithered One-bit Quantization](https://mlsanity.com/paper/2202.13157/) (2022)
- [OPORP: One Permutation + One Random Projection](https://mlsanity.com/paper/2302.03505/) (2023)
- [UNO: Unlimited Sampling Meets One-Bit Quantization](https://mlsanity.com/paper/2301.10155/) (2022)
- [Binary Iterative Hard Thresholding Converges with Optimal Number of Measurements for 1-Bit Compressed Sensing](https://mlsanity.com/paper/2207.03427/) (2022)
- [Quantizing Heavy-tailed Data in Statistical Estimation: (Near) Minimax Rates, Covariate Quantization, and Uniform Recovery](https://mlsanity.com/paper/2212.14562/) (2022)
- [Robust 1-bit Compressive Sensing with Partial Gaussian Circulant Matrices and Generative Priors](https://mlsanity.com/paper/2108.03570/) (2021)
- [Differential Privacy with Random Projections and Sign Random Projections](https://mlsanity.com/paper/2306.01751/) (2023)
- [Plug-in Channel Estimation with Dithered Quantized Signals in Spatially Non-Stationary Massive MIMO Systems](https://mlsanity.com/paper/2301.04641/) (2023)
- [AdaBoost and robust one-bit compressed sensing](https://mlsanity.com/paper/2105.02083/) (2021)
- [One-Bit Compressive Sensing: Can We Go Deep and Blind?](https://mlsanity.com/paper/2203.11278/) (2022)
- [One-bit Compressed Sensing using Generative Models](https://mlsanity.com/paper/2502.12762/) (2025)
- [Diffusion Model Based Signal Recovery Under 1-Bit Quantization](https://mlsanity.com/paper/2511.12471/) (2025)

## Abstract (arXiv)

Consider the recovery of an unknown signal x from quantized linear measurements. In the one-bit compressive sensing setting, one typically assumes that x is sparse, and that the measurements are of the form operatornamesign(langle ai, x rangle) ∈ ±1. Since such measurements give no information on the norm of x, recovery methods from such measurements typically assume that | x |2=1. We show that if one allows more generally for quantized affine measurements of the form operatornamesign(langle ai, x rangle + bi), and if the vectors ai are random, an appropriate choice of the affine shifts bi allows norm recovery to be easily incorporated into existing methods for one-bit compressive sensing. Additionally, we show that for arbitrary fixed x in the annulus r ≤ | x |2 ≤ R, one may estimate the norm | x |2 up to additive error δ from m gtrsim R4 r-2 δ-2 such binary measurements through a single evaluation of the inverse Gaussian error function. Finally, all of our recovery guarantees can be made universal over sparse vectors, in the sense that with high probability, one set of measurements and thresholds can successfully estimate all sparse vectors x within a Euclidean ball of known radius.