Compressive Sensing and Sparse Recovery

Core Idea

Compressive sensing (CS) reconstructs sparse signals from far fewer measurements than traditional Nyquist sampling requires. Instead of sampling at the signal's Nyquist rate and compressing, CS acquires only M random projections of the signal (where M ≪ N, the signal length), then solves a convex optimization to recover the original signal. Recovery is guaranteed if the signal is sparse (few nonzero coefficients) in some basis and the measurement matrix satisfies the Restricted Isometry Property (RIP): random matrices (Gaussian, binary, or structured) satisfy RIP with high probability. Algorithms include Basis Pursuit (convex), Greedy methods (OMP, CoSaMP), and approximate message passing (AMP).

How It's Best Learned

Generate a sparse signal (few nonzero coefficients in a Fourier or wavelet basis). Acquire M random linear measurements (dot products with random vectors), where M is much smaller than the signal length. Solve the basis pursuit problem (minimize ℓ₁ norm of coefficients subject to measurement constraints) using a convex solver (CVX, CVXPY). Observe perfect or near-perfect reconstruction. Vary M and sparsity to find the transition where recovery fails, confirming the phase diagram: recovery succeeds if M/N > C·K·log(N/K) where K is sparsity.

Common Misconceptions

• Compressive sensing violates the Nyquist theorem; it does not — CS acquires information at a different rate (projection rate) than Nyquist sampling, and reconstructs by exploiting sparsity, which is additional structure the Nyquist theorem does not assume.
• Any random measurement matrix guarantees recovery; structured matrices (Fourier subsampled, circulant) work but are suboptimal compared to unstructured (Gaussian) matrices, which satisfy RIP more reliably.
• Basis pursuit (convex ℓ₁ minimization) always recovers the sparse signal; it recovers the *sparsest* solution consistent with measurements, which is the true signal if RIP holds and noise is small.

Explainer

The Nyquist sampling theorem says you must sample a signal at twice its bandwidth to recover it. If a signal occupies a bandwidth of 100 MHz, you need 200 million samples per second. But many real signals are sparse: an audio recording might have 1000 frequency components spread across a spectrum of 1 million points; an image might have 90% of its pixels below noise threshold after wavelet transform. Compressive sensing exploits this sparsity to dramatically reduce the number of measurements needed.

The core idea: instead of sampling the signal and then compressing (discarding most values), measure and compress simultaneously. Take M random linear projections (random dot products) of the signal, where M is much smaller than N (the signal length): y = Φx, where Φ is M × N with M ≪ N. Since we have fewer equations than unknowns, the system is underdetermined. But if x is sparse (most coefficients zero in some basis), we can solve for x by finding the sparsest solution consistent with y — the unique solution is the sparse vector.

The sparsity model is crucial. The signal x may not be sparse in the time domain, but it is sparse in some basis Ψ: x = Ψs where s is sparse (K nonzero coefficients). Measuring y = Φx = ΦΨs reveals s (up to a change of variables). You then recover s by solving: minimize ||s||₀ (count of nonzero entries) subject to ΦΨs = y. This is combinatorial (NP-hard), but a convex relaxation works: minimize ||s||₁ (sum of absolute values) subject to ΦΨs = y. This Basis Pursuit problem is a linear program, solvable in polynomial time. Remarkably, under conditions on Φ and s's sparsity, the ℓ₁ solution is identical to the ℓ₀ solution — you can solve a hard problem by convex optimization.

The Restricted Isometry Property (RIP) is the condition that makes this work. A matrix Φ satisfies RIP of order K with constant δ_K if all K-sparse vectors are approximately preserved: (1−δ_K)||s||² ≤ ||Φs||² ≤ (1+δ_K)||s||² for all K-sparse s. Intuitively, Φ acts like an approximate isometry (distance-preserving) on sparse vectors. Random matrices (Gaussian entries, binary ±1) satisfy RIP with high probability when M > C·K·log(N/K). This is why randomness is beneficial: a worst-case adversarial matrix would map multiple distinct K-sparse signals to the same measurement, making recovery impossible, but random matrices almost never do this.

Practical algorithms beyond basis pursuit include greedy methods like Orthogonal Matching Pursuit (OMP): iteratively identify the nonzero support one coordinate at a time by finding which dictionary atom best explains the measurement residual. OMP is faster than basis pursuit (no NLP solver needed) but slightly suboptimal — it doesn't account for measurement noise as elegantly. Approximate Message Passing (AMP) is a newer iterative algorithm inspired by statistical physics, giving near-optimal reconstruction with lower computational cost.

Applications span MRI (acquire fewer k-space samples, reconstruct with sparsity in wavelet domain), radar (reconstruct target echoes from compressed pulse returns), astronomy (reconstruct images from telescope data), and machine learning (recover sparse feature vectors). The catch: you must be in a regime where M ≤ N but M is close to the information-theoretic limit K·log(N/K), which requires K ≪ N (signals genuinely sparse). For nearly-random signals or signals sparse only in learned, data-dependent bases, CS gains diminish. Modern extensions combine CS with deep learning: train a neural network to map compressed measurements directly to signal reconstructions, achieving better performance than model-based approaches for complex, learned sparsity structures.