For most large underdetermined systems of equations, the minimal 𝓁1‐norm near‐solution approximates the sparsest near‐solution

By David L. Donoho. 2006

893 citations recorded by the source corpus.

Subfields: Applied Mathematics, Computational Mechanics, Statistics and Probability

View Paper: https://www.semanticscholar.org/paper/36ab8bd64210ac5c4f7d326ed2c0a5745e91320f

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

In Computational Mechanics

In Statistics and Probability

Citations in the corpus

The sparsity and bias of the Lasso selection in high-dimensional linear regression (2008, methodology): “For the estimation of β, Donoho (2006) proved the ℓ2-consistency of the LASSO estimator for p≍ n when X is a certain normalization of a random matrix with i.i.d.”
Image Super-Resolution Via Sparse Representation (2010, background): “Although the optimization problem (4) is NP-hard in general, recent results [7], [8] suggest that as long as the desired coefficients α are sufficiently sparse, they can be efficiently recovered by instead minimizing the `(1)-norm, as follows:”
Theoretical Results on Sparse Representations of Multiple-Measurement Vectors (2006, result): “A similar result regarding noisy data was reported in [35].”
Accurate Telemonitoring of Parkinson's Disease Progression by Noninvasive Speech Tests (2009, background): “search through all possible combinations of measures to find the smallest combination that produces the minimum prediction error [26].”
1-Bit compressive sensing (2008, background): “In several cases, including the classical compressive sensing reconstruction methods, minimizing the `1 norm has been theoretically proven equivalent to minimizing the `0 pseudonorm of the signal [9], [10].”
Novel Speech Signal Processing Algorithms for High-Accuracy Classification of Parkinson's Disease (2012, background): “The LASSO has been shown to have oracle properties (correctly identifying all the “true” features contributing toward predicting the response) in sparse settings when the features are not highly correlated [28].”
The Application of Compressed Sensing for Photo-Acoustic Tomography (2009, background): “To overcome that issue, it has been shown recently that the minimization problem is equivalent for most if the solution is sufficiently sparse (see [23] for mathematical details)”
Signal Reconstruction From Noisy Random Projections (2006, background): “Recent results show that often the solution to this convex problem coincides with or approximates the solution to the original non-convex problem [20].”
Discussion: One-step sparse estimates in nonconcave penalized likelihood models (2008, background): “The quantities c∗ and c∗ have been considered as sparse minimum and maximum eigenvalues in [2, 7].”
Rejoinder: Local Rademacher complexities and oracle inequalities in risk minimization (2006, background): “ are known in signal processing and computational harmonic analysis (basis pursuit). There has been very interesting recent work on mathematical justiﬁcation of this approach in several settings (see [2, 3, 4, 5, 6, 10, 11]). It was shown that in many cases the minimization of the ℓ 1- norm leads to”