Compressed Sensing

Compressed sensing — also called compressive sampling — is a signal processing paradigm that reconstructs a sparse signal from far fewer samples than the Nyquist-Shannon theorem would seem to require. The theorem states that perfect reconstruction requires sampling at twice the maximum frequency; compressed sensing shows that if the signal is sparse in some known basis, it can be recovered from a number of samples proportional to its information content (its sparsity level) rather than its bandwidth.

The mathematical foundation rests on two conditions: sparsity — the signal must have a concise representation in some transform domain — and the restricted isometry property (RIP) — the measurement matrix must approximately preserve the distances between sparse vectors. When these conditions hold, reconstruction becomes a convex optimization problem: minimize the L1 norm subject to the measurement constraints. The LASSO algorithm and basis pursuit are standard solvers.

Compressed sensing has transformed MRI (where fewer samples mean shorter scan times), single-pixel cameras (where a spatial light modulator replaces the sensor array), and aperture synthesis in radio astronomy (where sparse baseline arrays sample the Fourier domain non-uniformly). In each domain, the technique trades measurement hardware for computational reconstruction.

The philosophical significance is easy to miss. Compressed sensing demonstrates that the information content of a signal is not equivalent to its raw data volume. A 10-megapixel image of a blank wall contains less information than a 1-kilobyte text file — and compressed sensing is the formal machinery that makes this intuition rigorous. It is a mathematical theory of relevance: how to measure only what matters.