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.