Sparse recovery algorithms

Given noisy compressive measurements $y=\Phi x+e$ of a signal $x$ , a core problem in compressive sensing (CS) is to recover a sparse signal $x$ from a set of measurements $y$ . Considerable efforts have been directed towards developing algorithms that perform fast, accurate, and stable reconstruction of $x$ from $y$ . As we have seen in previous chapters , a “good” CS matrix $\Phi$ typically satisfies certain geometric conditions, such as the restricted isometry property (RIP). Practical algorithms exploit this fact in various ways in order to drive down the number of measurements, enable faster reconstruction, and ensure robustness to both numerical and stochastic errors.

The design of sparse recovery algorithms are guided by various criteria. Some important ones are listed as follows.

• Minimal number of measurements.    Sparse recovery algorithms must require approximately the same number of measurements (up to a small constant) required for the stable embedding of $K$ -sparse signals.
• Robustness to measurement noise and model mismatch    Sparse recovery algorithms must be stable with regards to perturbations of the input signal, as well as noise added to the measurements; both types of errors arise naturally in practical systems.
• Speed.    Sparse recovery algorithms must strive towards expending minimal computational resources, Keeping in mind that a lot of applications in CS deal with very high-dimensional signals.
• Performance guarantees.    In previous chapters , we have already seen a range of performance guarantees that hold for sparse signal recovery using ${\ell }_1$ minimization. In evaluating other algorithms, we will have the same considerations. For example, we can choose to design algorithms that possess instance-optimal or probabilistic guarantees . We can also choose to focus on algorithm performance for the recovery of exactly $K$ -sparse signals $x$ , or consider performance for the recovery of general signals $x$ s. Alternately, we can also consider algorithms that are accompanied by performance guarantees in either the noise-free or noisy settings.

A multitude of algorithms satisfying some (or even all) of the above have been proposed in the literature. While it is impossible to describe all of them in this chapter, we refer the interested reader to the DSP resources webpage for a more complete list of recovery algorithms. Broadly speaking, recovery methods tend to fall under three categories: convex optimization-based approaches , greedy methods , and combinatorial techniques . The rest of the chapter discusses several properties and example algorithms of each flavor of CS reconstruction.