One‐Bit Compressed Sensing by Linear Programming

By Yaniv Plan, Roman Vershynin. arXiv.org, 2011

441 citations recorded by the source corpus.

We give the first computationally tractable and almost optimal solution to the problem of one‐bit compressed sensing, showing how to accurately recover an s‐sparse vector \input amssym $x \in {\Bbb R}^n$ from the signs of $O(s \log^2(n/s))$ random linear measurements of x. The recovery is achieved by a simple linear program. This result extends to approximately sparse vectors x. Our result is universal in the sense that with high probability, one measurement scheme will successfully recover all sparse vectors simultaneously. The argument is based on solving an equivalent geometric problem on random hyperplane tessellations.

Subfields: Biomedical Engineering, Computational Mechanics, Computer Vision and Pattern Recognition

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

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 Vision and Pattern Recognition

Citations in the corpus

Robust 1-bit Compressed Sensing and Sparse Logistic Regression: A Convex Programming Approach (2012, methodology): “Further, once can use that √ n and obtain the useful comparison of Gaussian and spherical versions of mean width: Let us record some further simple but useful properties of the mean width.”
Robust 1-Bit Compressive Sensing via Binary Stable Embeddings of Sparse Vectors (2011, background): “Furthermore, since the first appearance of our work, a bound on the achievable reconstruction error for compressible signals and for signals in arbitrary subsets of appeared in [31] and [32].”
Moving Beyond Sub-Gaussianity in High-Dimensional Statistics: Applications in Covariance Estimation and Linear Regression (2018, methodology): “10) of Hastie, Tibshirani and Wainwright (2015). This assumption was verified for covariance matrices of sub-Gaussian random vectors by Rudelson and Zhou (2013), extending the work of Raskutti, Wainwright and Yu (2010) for Gaussians.”
Regularizing Neural Networks via Minimizing Hyperspherical Energy (2019, background): “In this case, the neuron weights can be well recovered [54, 55].”
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].”