Comptes Rendus
Theory of Signals
A necessary and sufficient condition for exact sparse recovery by 1 minimization
[Une condition nécessaire et suffisante dʼidentifiabilité parcimonieuse par minimisation 1]
Comptes Rendus. Mathématique, Volume 350 (2012) no. 1-2, pp. 117-120.

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.

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.

Reçu le :
Accepté le :
Publié le :
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

Cité par Sources :

Commentaires - Politique