For most large underdetermined systems of linear equations the minimal 𝓁1‐norm solution is also the sparsest solution

By David L. Donoho. 2006

2,665 citations recorded by the source corpus.

Subfields: Computational Mechanics, Computational Theory and Mathematics, Statistics and Probability

How researchers see this paper

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

In Computational Mechanics

In Computational Theory and Mathematics

In Statistics and Probability

Citations in the corpus

Best Subset Selection via a Modern Optimization Lens (2015, background): “There has been a substantial amount of impressive work on Lasso [Bickel, Ritov and Tsybakov (2009), Candès and Plan (2009), Donoho (2006), Efron et al. (2004), Greenshtein and Ritov (2004), Knight and Fu (2000), Meinshausen and Bühlmann (2006), Wainwright (2009), Zhang and Huang (2008), Zhao and Yu…”
Joint covariate selection and joint subspace selection for multiple classification problems (2010, methodology): “Another approach treats the problem as a parameter estimation problem in which the shrinkage induced by a constraint on the 1 norm of the parameter vector yields estimates in which certain components are equal to zero (Tibshirani 1996; Fu and Knight 2000; Donoho 2004).”
Probing the Pareto Frontier for Basis Pursuit Solutions (2008, background): “There is now a significant body of work that addresses the conditions under which a solution of this problem yields a sparse approximation to a solution of the underdetermined system; see Candès, Romberg, and Tao [10], Donoho [23], Tropp [47], and references therein.”
Robust Recovery of Subspace Structures by Low-Rank Representation (2010, background): “Under the assumption that the data is clean and the subspaces are independent, [13] shows that solution produced by sparse representation (SR) [32] could achieve the so-called l1 Subspace Detection Property (l1-SDP): the within-class affinities are sparse and the between-class affinities are all zer”
Rank-Sparsity Incoherence for Matrix Decomposition (2009, background): “The `1 norm has been used as an effective surrogate for the number of nonzero entries of a vector, and a number of results provide conditions under which this heuristic recovers sparse solutions to illposed inverse problems [11].”
Extensions of compressed sensing (2006, background): “† Donoho [ 12 , 13, 14] considered the uniform Spherical ensemble.”
Blind motion deblurring from a single image using sparse approximation (2009, background): “More importantly, as Donoho pointed out in [14] that the minimal l1 norm solution is the sparsest solution for most large under-determined systems of linear equations, using tight frame system for representing images/kernels is very attractive because the tight frame coefficients of images/kernels a”
Sparsity and incoherence in compressive sampling (2006, background): “This work has shown that taking random measurements is in some sense an optimal strategy for acquiring sparse signals; it requires a near-minimal number of measurements [1, 6, 7, 10, 11]—m measurements can recover signals with sparsity S m/ log(n/m), and all of the constants appearing in the analysi”
Sparse coding based visual tracking: Review and experimental comparison (2013, methodology): “As the closest convex function to the ‘ 0 -norm minimization, the ‘ 1 -norm minimization is widely used to replace the ‘ 0 -norm minimization It was shown that the ‘ 0 -norm and ‘ 1 -norm minimizations are equivalent if the coefﬁcients are sufﬁciently sparse [23].”
Using Generalized Correlation to Effect Variable Selection in Very High Dimensional Problems (2009, background): “It includes, but is by no means restricted to, work on the nonnegative garotte (e.g., Breiman 1995; Gao 1998), on soft thresholding (e.g., Donoho et al. 1995), and related work (e.g., Donoho and Huo 2001; Fan and Li 2001; Donoho and Elad 2003; Tropp 2005; Donoho 2006a, 2006b).”
Invertibility of Convolutional Generative Networks from Partial Measurements (2018, background): “Our problem is also connected to compressive sensing [4, 3] which exploits the sparsity of natural signals to design acquisition schemes where the number of measurements scales linearly with the sparsity level.”
Transfer learning for image classification with sparse prototype representations (2008, background): “In the context of regression Donoho [7] has proven that the solution with smallest l1 norm is also the sparsest solution, i.”
Stable signal recovery from incomplete and inaccurate measurements (2005, background): “First, Ax ♯ is within 2 ǫ of the “noise free” observations Ax 0 thanks to the triangle inequality Geometrically, this says that x ♯ is known to be in a cylinder around the n -dimensional plane Ax 0 .”
Sharp Thresholds for High-Dimensional and Noisy Sparsity Recovery Using $\ell _{1}$ -Constrained Quadratic Programming (Lasso) (2009, background): “This problem, known variously as sparsity recovery, support recovery, or variable selection, arises in a broad variety of contexts, including subset selection in regression [28], compressed sensing [4], [9], structure estimation in graphical models [27], sparse approximation [8], and signal…”
THE ASYMPTOTIC DISTRIBUTION AND BERRY-ESSEEN BOUND OF A NEW TEST FOR INDEPENDENCE IN HIGH DIMENSION WITH AN APPLICATION TO STOCHASTIC OPTIMIZATION (2008, result): “standard normal random variables, the result is similar to that given in [5].”