Comptes Rendus
no. 1-2
Theory of Signals
A necessary and sufficient condition for exact sparse recovery by ℓ1 minimization

Presented by: Yves Meyer

Charles Dossal1
1 IMB, Université Bordeaux 1, 351, Cours de la Libération, 33405 Talence cedex, France
Comptes Rendus. Mathématique, Volume 350 (2012) no. 1-2, pp. 117-120.

In this Note, a new sharp sufficient condition for exact sparse recovery by ℓ1-penalized minimization from linear measurements is proposed. The main contribution of this paper is to show that, for most matrices, this condition is also necessary. Moreover, when the ℓ1 minimizer is unique, we investigate its sensitivity to the measurements and we establish that the application associating the measurements to this minimizer is Lipschitz-continuous.

Dans cette Note, une nouvelle condition suffisante pour lʼidentifiabilité parcimonieuse par minimisation ℓ1 pénalisée à partir de mesures linéaires est proposée. La contribution majeure de ce travail est de prouver que pour la plupart des matrices, cette condition est aussi nécessaire. Par ailleurs, lorsque le minimiseur du problème ℓ1 est unique, sa sensibilité aux mesures est étudiée et il est montré que lʼapplication qui envoie les mesures sur ce minimiseur est Lipschitz-continue.

Received:
Accepted:
Published online:
DOI: 10.1016/j.crma.2011.12.014

Charles Dossal 1

1 IMB, Université Bordeaux 1, 351, Cours de la Libération, 33405 Talence cedex, France 
@article{CRMATH_2012__350_1-2_117_0,
     author = {Charles Dossal},
     title = {A necessary and sufficient condition for exact sparse recovery by $ {\ell }_{1}$ minimization},
     journal = {Comptes Rendus. Math\'ematique},
     pages = {117--120},
     publisher = {Elsevier},
     volume = {350},
     number = {1-2},
     year = {2012},
     doi = {10.1016/j.crma.2011.12.014},
     language = {en},
}
TY  - JOUR
AU  - Charles Dossal
TI  - A necessary and sufficient condition for exact sparse recovery by $ {\ell }_{1}$ minimization
JO  - Comptes Rendus. Mathématique
PY  - 2012
SP  - 117
EP  - 120
VL  - 350
IS  - 1-2
PB  - Elsevier
DO  - 10.1016/j.crma.2011.12.014
LA  - en
ID  - CRMATH_2012__350_1-2_117_0
ER  - 
%0 Journal Article
%A Charles Dossal
%T A necessary and sufficient condition for exact sparse recovery by $ {\ell }_{1}$ minimization
%J Comptes Rendus. Mathématique
%D 2012
%P 117-120
%V 350
%N 1-2
%I Elsevier
%R 10.1016/j.crma.2011.12.014
%G en
%F CRMATH_2012__350_1-2_117_0
Charles Dossal. A necessary and sufficient condition for exact sparse recovery by $ {\ell }_{1}$ minimization. Comptes Rendus. Mathématique, Volume 350 (2012) no. 1-2, pp. 117-120. doi : 10.1016/j.crma.2011.12.014. https://comptes-rendus.academie-sciences.fr/mathematique/articles/10.1016/j.crma.2011.12.014/

[1] E.J. Candès; Y. Plan Near ideal model selection by ℓ1 minimization, Ann. Statist., Volume 37 (2009), pp. 2145-2177

[2] D. Donoho, Neighborly polytopes and sparse solution of underdetermined linear equations, Preprint, 2004.

[3] D. Donoho, J. Tanner, Neighborliness of randomly-projected simplices in high dimensions, Preprint, 2005.

[4] Ch. Dossal; G. Peyré; J. Fadili A numerical exploration of compressed sampling recovery, Linear Algebra Appl., Volume 432 (2010), pp. 1663-1679

[5] Ch. Dossal; M.L. Chabanol; G. Peyré; J. Fadili Sharp support recovery from noisy random measurements by ℓ1 minimization, Appl. Comput. Harmon. Anal. (2011) | DOI

[6] J.J. Fuchs On sparse representations in arbitrary redundant bases, IEEE Trans. Inform. Theory, Volume 50 (2004), pp. 1341-1344

[7] J.A. Tropp Just relax: convex programming methods for identifying sparse signals in noise, IEEE Trans. Inform. Theory, Volume 52 (2006), pp. 1030-1051

[8] Wainwright Sharp thresholds for high-dimensional and noisy sparsity recovery using ℓ1-constrained quadratic programming (lasso), IEEE Trans. Inform. Theory, Volume 55 (2009) no. 5, pp. 2183-2202

Cited by Sources:

Comments - Policy