Sparse recovery (ECE 592 Module 46)

This module discusses sparse signal recovery. Before compressed sensing, many practitioners used ell2 recovery. In compressed sensing, we have more unknowns than measurements, hence we have infinitely many solutions that satisfy the measurements, and the ell2 solution is the one with the lowest energy. However the ell2 solution is often non-sparse. Instead, we want a sparse solution. Ideally, we could find the sparsest solution that satisfies the measurements, which minimizes an ell0 norm. However, ell0 minimization is not robust to noisy measurements, and requires combinatorial computation. Instead, ell1 minimization offers perfect reconstruction using a mild number of measurements, while being somewhat robust to noise and computationally tractable. From ell1 recovery, we transition to LASSO, which can account for measurement noise. Finally, the compressive sampling matching pursuit (Cosamp) algorithm by Needell and Tropp provides geometric decay of the signal recovery error, until we reach some noise floor.