no. 1-2
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]

Présenté par : Yves Meyer

Dossal, Charles1
1 IMB, Université Bordeaux 1, 351, Cours de la Libération, 33405 Talence cedex, France
Comptes Rendus. Mathématique, Tome 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
Dossal, Charles 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 = {Dossal, Charles},
     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},
     url = {http://www.numdam.org/articles/10.1016/j.crma.2011.12.014/}
}
TY  - JOUR
AU  - Dossal, Charles
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
UR  - http://www.numdam.org/articles/10.1016/j.crma.2011.12.014/
DO  - 10.1016/j.crma.2011.12.014
LA  - en
ID  - CRMATH_2012__350_1-2_117_0
ER  - 
%0 Journal Article
%A Dossal, Charles
%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
%U http://www.numdam.org/articles/10.1016/j.crma.2011.12.014/
%R 10.1016/j.crma.2011.12.014
%G en
%F CRMATH_2012__350_1-2_117_0
Dossal, Charles. A necessary and sufficient condition for exact sparse recovery by $ {\ell }_{1}$ minimization. Comptes Rendus. Mathématique, Tome 350 (2012) no. 1-2, pp. 117-120. doi : 10.1016/j.crma.2011.12.014. http://www.numdam.org/articles/10.1016/j.crma.2011.12.014/

[1] Candès, E.J.; Plan, Y. 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] Dossal, Ch.; Peyré, G.; Fadili, J. A numerical exploration of compressed sampling recovery, Linear Algebra Appl., Volume 432 (2010), pp. 1663-1679

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

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

[7] Tropp, J.A. 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 :