Compressed Sensing

Sparse signals rebuild from far fewer random measurements than Nyquist demands, because $\ell_1$ minimization finds the sparsest fit.

Few random measurements constrain the signal to a plane that touches the sparsity diamond at exactly the true sparse point

Why Does This Exist?

Nyquist samples every signal at twice its top frequency, yet most real signals are sparse somewhere: MRI images in wavelets, audio in tones, genomic markers among millions. Sampling fully then discarding $95\%$ of coefficients wastes the scarcest resource (scan time, sensor power). Compressed sensing (Candès, Romberg, Tao; Donoho, 2006) samples compressed: $m \ll n$ random linear measurements suffice when the signal has $K$ nonzero entries in a known basis, and tractable $\ell_1$ minimization recovers it exactly. Sampling limits are sampling theory; sparse penalties in models are regularization derivations.

The one idea you need first

A signal $x$ is $K$ -sparse when at most $K$ entries are nonzero (in some basis). The $\ell_0$ count is NP-hard to minimize; the $\ell_1$ norm $\sum |x_i|$ is its closest convex friend, and minimizing it promotes sparsity because its unit ball is pointy along axes.

Think of It Like This

Finding a few lit windows from street totals

A tower has $1{,}000$ windows, $5$ lit. Reading every window takes all night. Instead you meter $30$ random street-facing totals (each a random weighted sum of windows). The lit set is the unique $5$ -window explanation matching all $30$ totals, because any wrong $5$ fails some meter.

$\ell_1$ minimization is the search for that explanation: among all window patterns matching the meters, prefer the one with the smallest total brightness. The pointy geometry (diamond, not ball) lands on sparse corners. Dense towers (half lit) defeat every meter layout: sparsity is the premise, not the trick.

How It Actually Works

Measure $y = Ax$ with $m \times n$ random $A$ (Gaussian, partial Fourier). Recover via $\min \lVert z \rVert_1$ subject to $Az = y$ . The restricted isometry property (RIP): $A$ nearly preserves lengths of all $K$ -sparse vectors ( $(1-\delta)\lVert x \rVert^2 \le \lVert Ax \rVert^2 \le (1+\delta)\lVert x \rVert^2$ ). RIP with small $\delta$ certifies exact recovery. Measurement count: $m \ge C K \log(n/K)$ (constant $C$ near $4$ for Gaussian designs).

Worked example

MRI slice $n = 65{,}536$ pixels, wavelet-sparse with $K = 2{,}000$ significant coefficients. Nyquist needs $65{,}536$ samples. Compressed sensing: $m \ge 4 \times 2{,}000 \times \ln(65{,}536/2{,}000) = 8{,}000 \times \ln(32.8) \approx 8{,}000 \times 3.49 \approx 27{,}900$ measurements: $43\%$ of Nyquist, scan time nearly halved in practice (clinical factors reach $4$ to $8$ times with tuned bases). Toy check: $n = 100$ , $K = 3$ spikes at positions $(10, 40, 70)$ with values $(5, -3, 2)$ : $m = 20$ Gaussian measurements recover all positions and values within $10^{-6}$ via $\ell_1$ ; least squares ( $\ell_2$ ) instead smears energy over all $100$ entries with MSE above $1$ .

Code

1def l1_shrink(vals: list[float], lam: float) -> list[float]:2    out = []3    for v in vals:  # soft threshold: kill small, shrink rest toward zero4        if v > lam:5            out.append(round(v - lam, 3))6        elif v < -lam:7            out.append(round(v + lam, 3))8        else:9            out.append(0.0)10    return out11
12
13print(l1_shrink([5.0, 0.3, -3.0, 0.1, 2.0], 0.5))  # -> [4.5, 0.0, -2.5, 0.0, 1.5]

Threshold $0.5$ zeroes the two small entries and shrinks the three spikes: one shrinkage step of the recovery loop that converges to the sparse fit.

Watch Out For

Assuming sparsity in the wrong basis

Random measurements preserve information only when the signal is sparse in the assumed basis; natural images are not pixel-sparse (recovery fails), though wavelet-sparse (it succeeds). Verify compressibility (sorted-coefficient decay) in your basis before designing any measurement matrix.

Coherent measurements silently voiding RIP

Measurements aligned with the sparsity basis (sampling low Fourier modes of a Fourier-sparse signal) correlate instead of spreading information: RIP fails and $\ell_1$ returns aliasing artifacts. Randomize across an incoherent basis (noiselets vs wavelets) and check mutual coherence numbers first.

The Quick Version

$K$ -sparse signals recover from $m \ge 4K\ln(n/K)$ random measurements via $\ell_1$ .
The MRI example cuts $65{,}536$ samples to about $27{,}900$ at $K = 2{,}000$ .
RIP certifies the measurement matrix; incoherence guides its design.
$\ell_2$ smears while $\ell_1$ sparsifies: pointy balls land on sparse corners.
Verify basis sparsity and measurement incoherence before trusting recovery.
Threshold $0.5$ zeroes small entries and shrinks spikes per the code.