Compressed sensing

What Is Compressed Sensing?

Compressed sensing is a signal acquisition and reconstruction framework that exploits the inherent sparsity of many real-world signals to recover them accurately from far fewer measurements than classical sampling theory requires. The Nyquist-Shannon sampling theorem mandates that a signal be sampled at twice its highest frequency component to avoid aliasing; compressed sensing replaces this rate requirement with a structural condition: if a signal is sparse in some known domain, a small number of incoherent measurements is sufficient for exact or near-exact reconstruction. The approach was placed on rigorous mathematical footing around 2004 through work by Emmanuel Candès, Justin Romberg, Terence Tao, and David Donoho, whose proofs established when and how recovery from undersampled data is possible.

The practical motivation is compelling. Many signals encountered in medical imaging, communications, and remote sensing are sparse, meaning only a small fraction of their coefficients in a transform domain such as the Fourier or wavelet domain are large while the rest are negligible. Conventional analog-to-digital converters sample at the full Nyquist rate and then discard most of the acquired data through subsequent compression. Compressed sensing relocates this efficiency gain from the digital stage to the measurement stage itself. The Rice University Digital Signal Processing group's compressive sensing resource collection catalogs the foundational papers and the research threads that emerged from this insight.

Sparsity and Incoherence

Two mathematical conditions underpin the compressed sensing guarantee. The first is sparsity: the signal of interest must be representable as a linear combination of a small number of elements from some basis or frame. A signal with at most k nonzero coefficients in a known dictionary of N atoms is called k-sparse. The second condition is incoherence between the measurement basis and the sparsity basis, which ensures that no sparse signal can appear dense in the measurement domain and thereby evade detection.

A sufficient formal condition combining both requirements is the Restricted Isometry Property (RIP), introduced by Candès and Tao. A measurement matrix satisfies the RIP of order k if it approximately preserves the norms of all k-sparse vectors, guaranteeing that distinct sparse signals produce distinguishable measurements. Gaussian random matrices and Fourier-based partial random matrices satisfy the RIP with high probability using on the order of k log(N/k) measurements, a number that is sub-linear in N. The IEEE Xplore paper on sparse signal representation, sampling, and recovery in compressive sensing frameworks provides a contemporary treatment of these conditions and their relationship to practical measurement designs.

Recovery Algorithms

Given a measurement vector and the measurement matrix, recovery of the original sparse signal is cast as an optimization problem. The theoretically ideal formulation minimizes the zero-norm (count of nonzero coefficients) subject to the measurement constraint, but this is a combinatorial problem and computationally intractable for large dimensions. The key insight from Candès, Romberg, and Tao, and independently Donoho, is that under the RIP condition, minimizing the convex one-norm (sum of absolute values) yields the same sparse solution. This convex relaxation, known as Basis Pursuit, can be solved with standard linear programming tools.

Greedy algorithms such as Orthogonal Matching Pursuit (OMP) and CoSaMP offer faster runtimes by iteratively selecting and updating the active support of the signal. Message-passing algorithms including Approximate Message Passing (AMP) scale to very large problems and connect compressed sensing recovery to belief propagation in graphical models. A systematic review of sparse recovery algorithms published in IEEE Access surveys this algorithmic landscape and benchmarks convergence behavior across signal types.

Applications

Compressed sensing has applications in a range of fields, including: