A necessary and sufficient condition for exact sparse recovery by \(\ell_1\) minimization

DOI10.1016/j.crma.2011.12.014zbMath1236.94028OpenAlexW2077197393MaRDI QIDQ664941

Charles Dossal

Publication date: 5 March 2012

Published in: Comptes Rendus. Mathématique. Académie des Sciences, Paris (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.crma.2011.12.014

zbMATH Keywords

\(\ell _{1}\)-penalized minimizationexact sparse recoverylinear measurement

Mathematics Subject Classification ID

Signal theory (characterization, reconstruction, filtering, etc.) (94A12)

Related Items

Sparsest representations and approximations of an underdetermined linear system ⋮ An LP empirical quadrature procedure for parametrized functions ⋮ Optimal dual certificates for noise robustness bounds in compressive sensing ⋮ Thresholding gradient methods in Hilbert spaces: support identification and linear convergence ⋮ A power analysis for Model-X knockoffs with \(\ell_p\)-regularized statistics ⋮ The Lasso problem and uniqueness ⋮ On the solution uniqueness characterization in the L1 norm and polyhedral gauge recovery ⋮ The generalized Lasso problem and uniqueness ⋮ Necessary and sufficient conditions of solution uniqueness in 1-norm minimization ⋮ In defense of the indefensible: a very naïve approach to high-dimensional inference

Cites Work

• Near-ideal model selection by \(\ell _{1}\) minimization
• A numerical exploration of compressed sampling recovery
• On Sparse Representations in Arbitrary Redundant Bases
• Just relax: convex programming methods for identifying sparse signals in noise
• Sharp Thresholds for High-Dimensional and Noisy Sparsity Recovery Using $\ell _{1}$-Constrained Quadratic Programming (Lasso)
• Neighborliness of randomly projected simplices in high dimensions