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

David L. Donoho

Type: Article

Publication Date: 2006-03-21

Citations: 642

DOI: https://doi.org/10.1002/cpa.20131

View Publication

Locations

Communications on Pure and Applied Mathematics - View

Similar Works

Action	Title	Year	Authors
+	For most large underdetermined systems of linear equations the minimal 𝓁<sub>1</sub>‐norm solution is also the sparsest solution	2006	David L. Donoho
+	Sparsest solutions of underdetermined linear systems via <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" altimg="si1.gif" overflow="scroll"><mml:msub><mml:mi>ℓ</mml:mi><mml:mi>q</mml:mi></mml:msub></mml:math>-minimization for <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" altimg="si2.gif" overflow="scroll"><mml:mn>0</mml:mn><mml:mo><</mml:mo><mml:mi>q</mml:mi><mml:mo>⩽</mml:mo><mml:mn>1</mml:mn></mml:math>	2008	Simon Foucart Ming‐Jun Lai
+	On the Error of Estimating the Sparsest Solution of Underdetermined Linear Systems	2011	Massoud Babaie‐Zadeh Christian Jutten Hosein Mohimani
+	Under-determined linear systems and ℓ q -optimization thresholds.	2013	Mihailo Stojnic
+	Under-determined linear systems and $\ell_q$-optimization thresholds	2013	Mihailo Stojnic
+	Minimum ℓ1, ℓ2, and ℓ∞ Norm Approximate Solutions to an Overdetermined System of Linear Equations	2002	J.A. Cadzow
+	Sparse nonnegative solution of underdetermined linear equations by linear programming	2005	David L. Donoho Jared Tanner
+	Does $\ell_p$-minimization outperform $\ell_1$-minimization?	2015	Le Zheng Arian Maleki Xiaodong Wang Teng Fei Long
+ PDF Chat	RSP-Based Analysis for Sparsest and Least $\ell_1$-Norm Solutions to Underdetermined Linear Systems	2013	Yun-Bin Zhao
+	Sparse Solutions of Underdetermined Linear Systems	2012
+	Sparse Solutions of Underdetermined Linear Systems	2013	Inna Kozlov Alexander Petukhov
+	Sparse Solutions of Underdetermined Linear Systems	2015	Inna Kozlov Alexander Petukhov
+	Sparse Solutions of Underdetermined Linear Systems	2010	Inna Kozlov Alexander Petukhov
+	Sparse solution of overdetermined linear systems when the columns of $A$ are orthogonal	2012	Phanindra Jampana Sastry Challa
+	A fast algorithm for computing minimal-norm solutions to underdetermined systems of linear equations	2009	Mark Tygert
+	Does $\ell _{p}$ -Minimization Outperform $\ell _{1}$ -Minimization?	2017	Le Zheng Arian Maleki Haolei Weng Xiaodong Wang Teng Long
+	Locating Sparse Solutions of Underdetermined Linear Systems via the Reweighted ` 1 -Method	2012	Yun-Bin Zhao Duan Li
+	Sparse Solutions of Underdetermined Systems	2013	Simon Foucart Holger Rauhut
+ PDF Chat	Augmented $\ell_1$ and Nuclear-Norm Models with a Globally Linearly Convergent Algorithm	2013	Ming‐Jun Lai Wotao Yin
+	An Unconstrained $\ell_q$ Minimization with $0q\leq1$ for Sparse Solution of Underdetermined Linear Systems	2011	Ming‐Jun Lai Jingyue Wang

Works That Cite This (178)

Action	Title	Year	Authors
+ PDF Chat	ϵ-subgradient algorithms for bilevel convex optimization	2017	Elias S. Helou Lucas E. A. Simões
+	Sharp Thresholds for High-Dimensional and Noisy Sparsity Recovery Using $\ell _{1}$-Constrained Quadratic Programming (Lasso)	2009	Martin J. Wainwright
+	Rodeo: Sparse Nonparametric Regression in High Dimensions	2005	Larry Wasserman John Lafferty
+ PDF Chat	Discussion: A tale of three cousins: Lasso, L2Boosting and Dantzig	2007	Nicolai Meinshausen Guilherme V. Rocha Bin Yu
+	Stable Signal Reconstruction via $\ell^1$-Minimization in Redundant, Non-Tight Frames	2012	Markus Haltmeier
+ PDF Chat	Screening Strategies in the Presence of Interactions	2013	Danel Draguljić David C. Woods Angela Dean S. M. Lewis Anna-Jane E. Vine
+	Rodeo: Sparse Nonparametric Regression in High Dimensions	2005	John Lafferty Larry Wasserman
+	Basic tail and concentration bounds	2019	Martin J. Wainwright
+	Compressive sensing: a paradigm shift in signal processing	2008	Olga Holtz
+	Multi-Stage Variable Selection: Screen and Clean	2007	Larry Wasserman Kathryn Roeder

Works Cited by This (20)

Action	Title	Year	Authors
+	Signal processing and compression with wavelet packets	1994	Ronald R. Coifman Yves Meyer Steven Quake Mladen Victor Wickerhauser
+ PDF Chat	Asymptotic Theory of Finite Dimensional Normed Spaces	1986	Vitali Milman Gideon Schechtman
+	The Volume of Convex Bodies and Banach Space Geometry	1989	Gilles Pisier
+ PDF Chat	The Concentration of Measure Phenomenon	2005	Michel Ledoux
+	Local Operator Theory, Random Matrices and Banach Spaces	2001	Kenneth R. Davidson Stanisław J. Szarek
+ PDF Chat	Eigenvalues and Condition Numbers of Random Matrices	1988	Alan Edelman
+	Condition numbers of random matrices	1991	Stanisław J. Szarek
+ PDF Chat	The dimension of almost spherical sections of convex bodies	1977	T. Figiel Joram Lindenstrauss Vitali Milman
+	Sparse Approximate Solutions to Linear Systems	1995	B. K. Natarajan
+	For most large underdetermined systems of linear equations the minimal 𝓁<sub>1</sub>‐norm solution is also the sparsest solution	2006	David L. Donoho