The encyclopedia · R&D & Science · Technical decision · 2004–2006
Compressed sensing recovered sparse signals from far fewer samples
Candès, Romberg and Tao showed ℓ1 minimization can reconstruct a sparse signal from measurements far below Nyquist.
California Institute of Technology
The solution
Classical sampling theory says you must sample a signal at twice its bandwidth. Candès, Romberg and Tao asked whether a signal that is sparse — mostly zeros — can be recovered from far fewer, randomly chosen measurements.
Their answer, published in 2004–2006, was yes, via convex optimization: find the solution with the smallest ℓ1 norm consistent with the measurements. They proved that under a uniform uncertainty principle, ℓ1 minimization recovers the exact sparse signal, with error proportional to measurement noise.
The results covered both Gaussian random matrices and random Fourier samples, and extended to images and higher dimensions. The theory turned 'underdetermined' from a barrier into a design opportunity: measure less, reconstruct more.
Why it worked
- Sparsity plus randomness carries enough information
- ℓ1 minimization favors sparse solutions, ℓ2 does not
- Recovery error stays bounded by the noise level
- Random Fourier samples work for imaging
What can be applied
The bottleneck is often the recovery rule, not the data. Exploit known structure, switch the objective — ℓ1 instead of ℓ2 — and extract signals from far too few samples.
Aftermath
Compressed sensing grew into a research field with applications in MRI, single-pixel cameras, radar and astronomy, where acquiring every sample is expensive; the Wikipedia survey lists those applications.
Sources
- Stable Signal Recovery from Incomplete and Inaccurate Measurements
- Robust Uncertainty Principles: Exact Signal Reconstruction from Highly Incomplete Frequency Information
- Compressed sensing
spotted an error? The archive wants to know.