Skip to Main content Skip to Navigation
Book sections

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.
Complete list of metadata

https://hal.inria.fr/hal-00767069
Contributor : Rémi Gribonval Connect in order to contact the contributor
Submitted on : Wednesday, December 19, 2012 - 2:27:37 PM
Last modification on : Tuesday, December 8, 2020 - 9:51:12 AM

Links full text

Identifiers

Collections

ANR

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⟩

Share

Metrics

Record views

49