Sparse Recovery Algorithms: Sufficient Conditions in Terms of Restricted Isometry Constants

Abstract : We review three recovery algorithms used in Compressive Sensing for the reconstruction s-sparse vectors x ∈ CN from the mere knowledge of linear measure- ments y = Ax ∈ Cm, m < N. For each of the algorithms, we derive improved con- ditions on the restricted isometry constants of the measurement matrix A that guar- antee the success of the reconstruction. These conditions are δ2s < 0.4652 for basis pursuit, δ3s < 0.5 and δ2s < 0.25 for iterative hard thresholding, and δ4s < 0.3843 for compressive sampling matching pursuit. The arguments also applies to almost sparse vectors and corrupted measurements. The analysis of iterative hard thresh- olding is surprisingly simple. The analysis of basis pursuit features a new inequality that encompasses several inequalities encountered in Compressive Sensing.
Type de document :
Chapitre d'ouvrage
Neamtu, Marian and Schumaker, Larry. Proceedings of Approximation Theory XIII: San Antonio 2010, 13, Springer New York, pp.65-77, 2012, 978-1-4614-0771-3. 〈10.1007/978-1-4614-0772-0_5〉
Liste complète des métadonnées

https://hal.inria.fr/hal-00767069
Contributeur : Rémi Gribonval <>
Soumis le : mercredi 19 décembre 2012 - 14:27:37
Dernière modification le : mercredi 19 décembre 2012 - 14:33:42

Lien texte intégral

Identifiants

Citation

Simon Foucart. Sparse Recovery Algorithms: Sufficient Conditions in Terms of Restricted Isometry Constants. Neamtu, Marian and Schumaker, Larry. Proceedings of Approximation Theory XIII: San Antonio 2010, 13, Springer New York, pp.65-77, 2012, 978-1-4614-0771-3. 〈10.1007/978-1-4614-0772-0_5〉. 〈hal-00767069〉

Partager

Métriques

Consultations de la notice

36