Sparsity and incoherence in compressive sampling
By E.J. Candes, Justin K. Romberg. 2006
2,190 citations recorded by the source corpus.
We consider the problem of reconstructing a sparse signal from a limited number of linear measurements. Given m randomly selected samples of Ux0, where U is an orthonormal matrix, we show that ℓ1 minimization recovers x0 exactly when the number of measurements exceeds where S is the number of nonzero components in x0 and μ is the largest entry in U properly normalized: . The smaller μ is, the fewer samples needed. The result holds for ‘most’ sparse signals x0 supported on a fixed (but arbitrary) set T. Given T, if the sign of x0 for each nonzero entry on T and the observed values of Ux0 are drawn at random, the signal is recovered with overwhelming probability. Moreover, there is a sense in which this is nearly optimal since any method succeeding with the same probability would require just about as many samples.
Subfields: Applied Mathematics, Biomedical Engineering, Computational Mechanics
View Paper: https://www.semanticscholar.org/paper/73f818adda65015f5cc2d48a18c7cf9169b62510
How researchers see this paper
The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.
In Applied Mathematics
- Richard Baraniuk
- Marco F. Duarte
- E.J. Candes
- Justin K. Romberg
- Yonina C. Eldar
- Joel A. Tropp
- Michael B. Wakin
- Robert D. Nowak
In Biomedical Engineering
- Marco F. Duarte
- Richard Baraniuk
- Yonina C. Eldar
- Justin K. Romberg
- E.J. Candes
- Holger Rauhut
- Wotao Yin
- Prateek Jain
In Computational Mechanics
- E.J. Candes
- Richard Baraniuk
- Wotao Yin
- Marco F. Duarte
- Yin Zhang
- Justin K. Romberg
- Yonina C. Eldar
- Prateek Jain
Citations in the corpus
- Discrete Signal Processing on Graphs: Sampling Theory (2015, methodology): “By substituting V into Theorem 1.2 in [44] and obtain (13).”
- Design and Analysis of a Hardware-Efficient Compressed Sensing Architecture for Data Compression in Wireless Sensors (2012, background): “where is a small known constant (empirically [16]) and is the dimensionality of the signal to be recovered [15].”
- The spectral norm error of the naive Nystrom extension (2011, methodology): “overy is determined by the rank of A and the coherence, ;of its range space. They use a standard result from the compressed sensing literature to quantify this phenomenon and obtain an estimate for ‘[CR07]. In [LKL10], Kwok, Li, and Lu propose replacing W with a low-rank approximation W~ to facilita”
- Unsupervised learning of invariant representations (2016, background): “This property (which is related to the notion of “incoherence” in compressive sensing [21]) requires that I and tk have a representation with sharply peaked correlation and autocorrelation.”
- Guaranteed Minimum-Rank Solutions of Linear Matrix Equations via Nuclear Norm Minimization (2007, background): “ approximation is desired. Incoherent Ensembles and Partially Observed Transforms Again, taking our lead from the compressed sensing literature, it would be of great interest to extend the results of [11] to low-rank recovery. In this work, the authors show that partially observed unitary transforma”
- Received-Signal-Strength-Based Indoor Positioning Using Compressive Sensing (2012, background): “Besides sparsity in (19), incoherence between and e is another important property that should be satisfied to enable the use of the CS theory for a sparse signal recovery from a small number of measurements [28].”
- Exploiting Structure in Wavelet-Based Bayesian Compressive Sensing (2009, background): “whelming probability” [6]–[9] one may recover exactly if ; similar relationships hold when is compressible but not exactly sparse.”
- A Systematic Review of Compressive Sensing: Concepts, Implementations and Applications (2018, background): “The number of measurements required for faithful reconstruction for particular choice of measurement matrix are given in Table 1, where c is a positive constant [6], [7].”
- Hyperspectral Unmixing Overview: Geometrical, Statistical, and Sparse Regression-Based Approaches (2012, positive): “What is, perhaps, totally unexpected is that sparse vector of fractional abundances can be reconstructed by solving (20) or (21) provided that the columns of matrix are incoherent in a given sense [186].”
- Learning partial differential equations via data discovery and sparse optimization (2017, background): “One application is in compressive sensing, which (in general) is the recovery of a signal from random measurements and results in an under-determined system of linear equations (see [5,6]).”
- Why do commercial CT scanners still employ traditional, filtered back-projection for image reconstruction? (2009, methodology): “CS concepts such as the restricted isometry property (RIP) [58], which we discuss in depth below, or related concepts such as incoherence [71], may prove to be useful analysis tools that can be applied directly to the discrete systems of optimization-based image reconstruction.”
- Off-Grid Direction of Arrival Estimation Using Sparse Bayesian Inference (2011, background): “Further, too dense a grid cannot improve the performance by the theory of CS [15, 26].”
- Compressive sensing: From theory to applications, a survey (2013, background): “Incoherence : Coherence measures the maximum correlation between any two elements of two different matrices.”
- Single-pixel imaging via compressive sampling (2008, methodology): “sets of basis vectors [7], such as Fourier, Walsh-Hadamard, or”
- Modern regularization methods for inverse problems (2018, background): “el to the eld of compressed sensing, where the focus was rather on designing the appropriate measurement setups for optimal compression than to improve reconstructions on a given inverse problem (cf. [145, 103, 99, 95, 96, 94, 146]). Despite the fact that the usual setting in compressed sensing is r”
- Matrix Coherence and the Nystrom Method (2010, background): “Recent work on compressed sensing and matrix completion, which also involve sampling-based approximations, have relied heavily on coherence assumptions (Candès and Romberg, 2007; Candès et al., 2006; Donoho, 2006).”
- Beyond Nyquist: Efficient Sampling of Sparse Bandlimited Signals (2009, methodology): “This windowing strategy relies on our ability to measure the windowed signal ψ·f .”
- Exact Matrix Completion via Convex Optimization (2008, methodology): “Using this notion, [9] showed that with high probability, a k-sparse signal could be recovered via linear programming from the observation of the inner product of the signal with m = (μ(U)k logn) randomly selected columns of the matrix U .”