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

David L. Donoho

Type: Article

Publication Date: 2006-03-23

Citations: 2530

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

View Publication

Locations

Communications on Pure and Applied Mathematics - View

Similar Works

Action	Title	Year	Authors
+	For most large underdetermined systems of equations, the minimal 𝓁<sub>1</sub>‐norm near‐solution approximates the sparsest near‐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
+	A fast algorithm for computing minimal-norm solutions to underdetermined systems of linear equations	2009	Mark Tygert
+	On the Error of Estimating the Sparsest Solution of Underdetermined Linear Systems	2011	Massoud Babaie‐Zadeh Christian Jutten Hosein Mohimani
+ PDF Chat	Iteratively reweighted least squares minimization for sparse recovery	2009	Ingrid Daubechies Ronald DeVore Massimo Fornasier C. Sınan Güntürk
+	Algorithms for solving overdetermined systems of linear equations in the lp-metric, 0 < p < 1	1978	Robert W. Owens V. P. Sreedharan
+	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
+ PDF Chat	L1 Norm Solution of Overdetermined System of Linear Equations	2019	Bijan Bidabad
+	Sparse recovery under matrix uncertainty	2010	Mathieu Rosenbaum Alexandre B. Tsybakov
+	Minimum ℓ1, ℓ2, and ℓ∞ Norm Approximate Solutions to an Overdetermined System of Linear Equations	2002	J.A. Cadzow
+ PDF Chat	RSP-Based Analysis for Sparsest and Least $\ell_1$-Norm Solutions to Underdetermined Linear Systems	2013	Yun-Bin Zhao
+	Sparse solution of overdetermined linear systems when the columns of $A$ are orthogonal	2012	Phanindra Jampana Sastry Challa
+ PDF Chat	Solutions of underdetermined systems of linear equations	1991	W. R. Madych
+	Locating Sparse Solutions of Underdetermined Linear Systems via the Reweighted ` 1 -Method	2012	Yun-Bin Zhao Duan Li
+	Sparse estimation via $\ell_q$ optimization method in high-dimensional linear regression	2019	Xin Li Yaohua Hu Chong Li Xiaoqi Yang Tianzi Jiang
+	Under-determined linear systems and ℓ q -optimization thresholds.	2013	Mihailo Stojnic
+ PDF Chat	Uniqueness Conditions for A Class of ℓ<sub>0</sub>-Minimization Problems	2015	Chunlei Xu Yun-Bin Zhao

Works That Cite This (670)

Action	Title	Year	Authors
+	Gaussian averages of interpolated bodies and applications to approximate reconstruction	2007	Y. Gordon Alexander E. Litvak Shahar Mendelson Alain Pajor
+ PDF Chat	Learning Semidefinite Regularizers	2018	Yong Sheng Soh Venkat Chandrasekaran
+ PDF Chat	Sparse estimation via lower-order penalty optimization methods in high-dimensional linear regression	2022	Xin Li Yaohua Hu Chong Li Xiaoqi Yang Tianzi Jiang
+	An efficient method of calculating composition-dependent inter-diffusion coefficients based on compressed sensing method	2020	Yi Qin Akil Narayan Kaiming Cheng Peng Wang
+ 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
+ PDF Chat	Statistical challenges of high-dimensional data	2009	Iain M. Johnstone D. M. Titterington
+ PDF Chat	Detecting transient signals in geodetic time series using sparse estimation techniques	2014	Bryan Riel M. Simons P. S. Agram Zhongwen Zhan
+ PDF Chat	Privacy-Preserving Data Sharing in High Dimensional Regression and Classification Settings	2012	Stephen E. Fienberg Jiashun Jin
+	An Iterative Support Shrinking Algorithm for Non-Lipschitz Optimization in Image Restoration	2018	Chao Zeng Rui Jia Chunlin Wu

Works Cited by This (19)

Action	Title	Year	Authors
+	Empirical Processes: Theory and Applications	1990	David Pollard
+	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
+ 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
+ PDF Chat	On Projection Algorithms for Solving Convex Feasibility Problems	1996	Heinz H. Bauschke Jonathan M. Borwein