A Probabilistic and RIPless Theory of Compressed Sensing

By E.J. Candes, Yaniv Plan. IEEE Transactions on Information Theory, 2010

599 citations recorded by the source corpus.

This paper introduces a simple and very general theory of compressive sensing. In this theory, the sensing mechanism simply selects sensing vectors independently at random from a probability distribution F; it includes all standard models-e.g., Gaussian, frequency measurements-discussed in the literature, but also provides a framework for new measurement strategies as well. We prove that if the probability distribution F obeys a simple incoherence property and an isotropy property, one can faithfully recover approximately sparse signals from a minimal number of noisy measurements. The novelty is that our recovery results do not require the restricted isometry property (RIP) to hold near the sparsity level in question, nor a random model for the signal. As an example, the paper shows that a signal with s nonzero entries can be faithfully recovered from about s logn Fourier coefficients that are contaminated with noise.

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

View Paper: https://www.semanticscholar.org/paper/5f8bf7b0a71825f2f47996a0cae9bcebfccdc685

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

Implicit Regularization in Nonconvex Statistical Estimation: Gradient Descent Converges Linearly for Phase Retrieval, Matrix Completion, and Blind Deconvolution (2017, methodology): “It would certainly be helpful if one could single out a few stylized structural properties/elements (like sparsity and incoherence in compressed sensing [13]) that enable near-optimal performance guarantees through an overarching method of analysis; with this in place, one would not need to start ea”
Iterative deblending of simultaneous-source seismic data using seislet-domain shaping regularization (2014, background): “To enforce sparsity, a transform domain thresholding operation can also be chosen as the shaping operator as long as the data in the transformed domain are sparse (Mallat, 2009; Candes and Plan, 2011).”
Compressed sensing, sparsity, and dimensionality in neuronal information processing and data analysis. (2012, background): “One of the key results of CS is that with such random measurement vectors, only M > O(K log(N /K )) 1. measurements are needed to guarantee perfect signal reconstruction with high probability (Candes & Tao 2005, Baraniuk et al. 2008, Candes & Plan 2010).”
Review of snapshot spectral imaging technologies (2013, background): “150 Orthogonal matrices are one example of systems that satisfy this property.”