Compressed Sensing: Sparse Recovery Theory, Algorithms and Practical Applications

Abstract

Classical sampling theory fixes the rate at which a signal must be measured by its bandwidth alone. Compressed sensing replaces that criterion with one based on structure: a signal that is sparse in some known basis can be reconstructed exactly from a number of linear measurements proportional to its sparsity and only logarithmic in its ambient dimension. This paper reviews the conditions under which such recovery is possible, the algorithms that achieve it, and the settings in which the theory has been applied. Uniqueness requires that the measurement matrix act almost isometrically on sparse vectors, a property that random matrices possess with high probability but that is difficult to certify for any given matrix. Under that property the combinatorial search for the sparsest solution can be replaced by minimisation of the sum of absolute values, a convex program, and the reconstruction is stable when measurements are noisy and the signal is only approximately sparse. Two numerical experiments carried out for this review illustrate the sharp boundary between success and failure as sparsity and the number of measurements are varied. Applications in magnetic resonance imaging and radio astronomy are examined together with the limits of the approach.