Robust 1-Bit Compressive Sensing via Binary Stable Embeddings of Sparse Vectors

By Laurent Jacques, Jason N. Laska, Petros T. Boufounos, Richard Baraniuk. IEEE Transactions on Information Theory, 2011

690 citations recorded by the source corpus.

The compressive sensing (CS) framework aims to ease the burden on analog-to-digital converters (ADCs) by reducing the sampling rate required to acquire and stably recover sparse signals. Practical ADCs not only sample but also quantize each measurement to a finite number of bits; moreover, there is an inverse relationship between the achievable sampling rate and the bit depth. In this paper, we investigate an alternative CS approach that shifts the emphasis from the sampling rate to the number of bits per measurement. In particular, we explore the extreme case of 1-bit CS measurements, which capture just their sign. Our results come in two flavors. First, we consider ideal reconstruction from noiseless 1-bit measurements and provide a lower bound on the best achievable reconstruction error. We also demonstrate that i.i.d. random Gaussian matrices provide measurement mappings that, with overwhelming probability, achieve nearly optimal error decay. Next, we consider reconstruction robustness to measurement errors and noise and introduce the binary ε-stable embedding property, which characterizes the robustness of the measurement process to sign changes. We show that the same class of matrices that provide almost optimal noiseless performance also enable such a robust mapping. On the practical side, we introduce the binary iterative hard thresholding algorithm for signal reconstruction from 1-bit measurements that offers state-of-the-art performance.

Subfields: Biomedical Engineering, Computational Mechanics, Computer Networks and Communications

View Paper: https://www.semanticscholar.org/paper/b802af3600c1ace3c60d1f7e399cded6133e1f15

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Biomedical Engineering

In Computational Mechanics

In Computer Networks and Communications

Citations in the corpus

Robust 1-bit Compressed Sensing and Sparse Logistic Regression: A Convex Programming Approach (2012, background): “These results of Jacques et al. [14] can be extended to handle adversarial bit ﬂips.”
One‐Bit Compressed Sensing by Linear Programming (2011, positive): “In particular, Jacques et al. [18] demonstrate that x is exactly sparse and is estimated using an ` 0 -minimization-based approach; the error is upper bounded as ı D O..s=m/ 1 (cid:0) o.1/ log n/ .”
Efficient spoken term discovery using randomized algorithms (2011, background): “coding and recognition applications with a different goal of constructing efficient and robust signal decompositions [19].”
Channel Estimation in Broadband Millimeter Wave MIMO Systems With Few-Bit ADCs (2016, methodology): “The ﬁgure shows the VAMP algorithms converging in ≈ 3 iterations, the GAMP algorithms converging in ≈ 8 iterations, and QIHT converging in ≈ 35 iterations.”
An Overview of Signal Processing Techniques for Millimeter Wave MIMO Systems (2015, background): “In general, to achieve the highest performance, the wireless protocol should be designed to support beam steering [119].”
1-Bit Matrix Completion (2012, background): “As noted above, matrix completion is closely related to the ﬁeld of compressed sensing, where a theory to deal with single-bit quantization has recently been developed [10,32,33,43,51,52].”