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

Keywords

Underdetermined system, Mathematics, Combinatorics, Norm (philosophy), Minification

References

• JUST RELAX: CONVEX PROGRAMMING METHODS FOR SUBSET SELECTION AND SPARSE APPROXIMATIONJoel A. Tropp — 2004
• Asymptotic Theory Of Finite Dimensional Normed SpacesVitali Milman, Gideon Schechtman — 1986
• The concentration of measure phenomenonMichel Ledoux — 2001
• Eigenvalues and condition numbers of random matricesAlan Edelman — 1988
• Atomic Decomposition by Basis PursuitScott Shaobing Chen, David L. Donoho, Michael A. Saunders — 1998
• Condition numbers of random matricesStanisław J. Szarek — 1991
• The dimension of almost spherical sections of convex bodiesT. Figiel, Joram Lindenstrauss, Vitali Milman — 1976
• Sparse Approximate Solutions to Linear SystemsB. K. Natarajan — 1995
• For most large underdetermined systems of linear equations the minimal 𝓁1‐norm solution is also the sparsest solutionDavid L. Donoho — 2006
• Stable recovery of sparse overcomplete representations in the presence of noiseDavid L. Donoho, Michael Elad, Vladimir Temlyakov — 2006
• Uncertainty principles and ideal atomic decompositionDavid L. Donoho, Xiaoming Huo — 2001
• Greed is good: algorithmic results for sparse approximationJoel A. Tropp — 2004
• Sparse representations in unions of basesRémi Gribonval, Morten Nielsen — 2003
• Robust uncertainty principles: exact signal reconstruction from highly incomplete frequency informationEmmanuel J. Candès, Justin Romberg, Terence Tao — 2004
• Matching pursuits with time-frequency dictionariesStéphane Mallat, Zhifeng Zhang — 1993
• On sparse representations in arbitrary redundant basesJ.-J. Fuchs — 2004
• A generalized uncertainty principle and sparse representation in pairs of basesMichael Elad, Alfred M. Bruckstein⋆ — 2002
• Spaces with large distance to l∞n and random matricesStanisław J. Szarek — 1990
• The Symmetric Eigenvalue ProblemJ. H. Wilkinson, Beresford Ν. Parlett — 1981
• Matrix computationsGene H. Golub — 1983

Cited by

• Sparse Signal Processing and Compressed Sensing RecoveryKumar Sahoo Sujit — 2015
• A Sparse Coding Based Similarity MeasureSebastian Klenk, Gunther Heidemann — 2009
• Deformable Segmentation via Sparse Shape RepresentationMercedes Fuertes López — 2011
• Novel Statistical Models for Complex Data StructuresJing Li, Shuai Huang — 2012
• Scalable and flexible network measurementHan Hee Song — 2006
• Compressive sensing with prior information applied to magnetic resonance imagingCristiano Jacques Miosso — 2010
• Feature Selection in Face Recognition: A Sparse Representation PerspectiveAllen Y. Yang, John Wright, Yi Ma — 2007
• A fast iterative shrinkage-thresholding algorithm for electrical resistance tomographyLingling Zhang, Wang Hua-xiang, Yanbin Xu — 2011
• Compressed Sensing Based 3D Tomographic Reconstruction for Rotational AngiographyHélène Langet, Cyril Riddell, Yves Trousset — 2011
• Accurate Telemonitoring of Parkinson's Disease Progression by Noninvasive Speech TestsAthanasios Tsanas, Max A. Little, Patrick McSharry — 2009
• Conception et caractérisation d'un système d'imagerie photoacoustique pour application biomédicaleSimon Archambault — 2010
• Under-Sampled Reconstruction Techniques for Accelerated Magnetic Resonance ImagingMohammad H. Kayvanrad — 2013
• New Methods for Network Traffic Anomaly DetectionT. Babaie — 2014
• Antipodal random sequences with prescribed second-order statistics: application to Compressive Sensing and UWB system based on DS-CDMAMauro Mangia — 2013
• Calculation of sensor redundancy degree for linear sensor systemsSanthosh Govindaraj — 2010
• Bayesian Experimental Design for Compressed SensingHannes Nickisch, Matthias Seeger — 2008
• Advances in correlation filters: vector features, structured prediction and shape alignmentB. V. K. Vijaya Kumar, Vishnu Naresh Boddeti — 2012
• Shrinkage Estimation in Partially Linear Models with Measurement ErrorYifang Li — 2010
• Sparse Representation Classification Beyond ℓ1 Minimization and the Subspace AssumptionCencheng Shen, Li Chen, Yuexiao Dong — 2015
• Different Wavelet-based Approaches for the Separation of Noisy and Blurred Mixtures of Components. Application to Astrophysical Data.Sandrine Anthoine — 2005

Related papers

• Introduction to sparse and compressive sensingPeter Gerstoft — 2016
• Identification of Coupled Map Lattice Based on Compressed SensingDong Xie, Lixiang Li, Xinxin Niu — 2016
• Underwater Acoustic Matched Field Imaging Based on Compressed SensingHuichen Yan, Jia Xu, Teng Long — 2015
• Performance bound of multiple hypotheses classification in compressed sensingJiuwen Cao, Zhiping Lin — 2015
• A User's Guide to Compressed Sensing for Communications SystemsKazunori Hayashi, Masaaki Nagahara, Toshiyuki Tanaka — 2013
• Electrical Capacitance Volume Tomography static imaging using Compressive Sensing with l1 sparse recoveryNur Afny Catur Andryani, Dodi Sudiana, Dadang Gunawan — 2017
• What is the p for some specific underdetermined matrices such that l_p-minimization is equivalent to l_0-minimizationChanglong Wang, Jigen Peng — 2017
• Approximate message passing-based compressed sensing reconstruction with generalized elastic net priorXing Wang, Jie Liang — 2013
• Spatial Compressive Sensing for Strain Data Reconstruction from Sparse SensorsMulugeta Haile — 2014
• GENERALIZED K-T BLAST AND K-T SENSE USING FOCUSSHong Jung, Jaeheung Yoo, Jong Ye — 2007