Sparse Recovery and Compressed Sensing

Sparse signals need far fewer measurements than their length suggests. With the right random design, $s$-sparse vectors recover exactly from about $s$ log $n$ linear measurements by $L_1$ minimisation.

Ten spikes in a length-1000 signal recover exactly from 150 random measurements while least squares on the same data fails

Why Does This Exist?

Nyquist says sample at twice the bandwidth, which for a length- $1000$ signal means $1{,}000$ measurements. But most real signals are sparse: only $s = 10$ coordinates carry content and the rest are zero. Measuring all $1{,}000$ coordinates to find $10$ spikes wastes $99$ percent of the effort in MRI, sensor networks and wideband receivers.

Compressed sensing breaks the Nyquist barrier for sparse inputs. Take $m$ random linear measurements $y = Ax$ with $m$ far below $n$ , then solve the convex program minimising $\lVert z \rVert_1$ (the sum of absolute values) subject to $Az = y$ . Under the right design that program returns the true sparse $x$ exactly. This page states when that miracle holds and counts the measurements; the restricted isometry property gives the geometric condition that certifies a given matrix.

Prerequisite in one paragraph. You need the $L_1$ norm $\lVert z \rVert_1 = \sum |z_i|$ , which favours sparsity, versus the $L_2$ norm, which spreads energy. A vector is $s$ -sparse when at most $s$ entries are nonzero. Background is in norms and linear systems and least squares.

Think of It Like This

Finding ten ringing phones in a hotel

A hotel has 1,000 rooms and 10 phones ringing. Knocking on every door takes all day. Instead you wire each corridor microphone to a random mix of rooms and record 150 mixed volumes. Each mix hears a different random subset, so the 10 ringing rooms imprint a unique signature across the 150 mixes while silent rooms contribute nothing.

$L_1$ minimisation is the detective that finds the smallest set of rooms explaining all 150 mixes. Least squares instead spreads blame across every room, producing a blurry non-answer. Sparsity is the assumption that makes the detective's answer unique.

Where the analogy stops: microphones add noise and hotel walls block sound unevenly. The theorem needs near-isometric random mixing; structured or correlated measurements break the guarantee the same way dead microphones would.

How It Actually Works

Fix sparsity $s$ and length $n$ . Draw $A$ as $m \times n$ with independent sub-Gaussian entries scaled by $1/\sqrt{m}$ . If $m \ge C s \log(n/s)$ for a modest constant $C$ near $2$ , then with high chance every $s$ -sparse $x$ is the unique $L_1$ minimiser consistent with $y = Ax$ . The proof shows $A$ preserves lengths of all sparse vectors at once via covering plus concentration, which is exactly the restricted isometry property at sparsity $2s$ .

Noisy measurements $y = Ax + w$ with $\lVert w \rVert_2 \le \eta$ degrade gracefully: the $L_1$ solution $\hat{x}$ satisfies $\lVert \hat{x} - x \rVert_2 \le C_0 \eta + C_1 \sigma_s(x)_1/\sqrt{s}$ , where $\sigma_s(x)_1$ is the $L_1$ error of the best $s$ -sparse approximation (zero for exactly sparse $x$ ).

Worked example

Take $n = 1000$ , $s = 10$ . Then $n/s = 100$ , $\ln 100 \approx 4.61$ , and $s\ln(n/s) \approx 46.1$ . With $C = 3$ the sufficient count is $m \approx 138$ , rounded to $150$ in the diagram. So $150$ random measurements, an $85$ percent saving over $1{,}000$ , recover any $10$ -sparse vector exactly with high chance.

Least squares on the same $150 \times 1000$ system returns the minimum- $L_2$ solution with all $1{,}000$ entries nonzero and typical error near $0.9$ relative, because the system is underdetermined and $L_2$ spreads energy. $L_1$ returns exactly $10$ nonzeros at error $0$ in the noiseless case. That contrast is the whole point: the norm, not the data, carries the sparsity assumption.

Watch Out For

Using a coherent or structured matrix as if random

Fourier samples at low frequencies only, or a sensor that repeats rows, have high coherence: sparse vectors in the wrong basis look identical through $A$ . $L_1$ then returns a plausible but wrong sparse answer with no warning, and increasing $m$ within the same bad design does not fix it.

Fix: check incoherence or RIP for your matrix and sparsity basis pair. Randomise the sampling pattern or change basis until the certificate holds.

Tuning the L1 solver tolerance to zero on noisy data

With noise $\eta > 0$ , demanding $Az = y$ exactly forces the solver to fit noise with fake spikes. The support explodes from $10$ to hundreds and the error grows past the graceful bound.

Fix: solve the relaxed form with $\lVert Az - y \rVert_2 \le \eta$ . Set the tolerance from a noise calibration, not from optimism.

The Quick Version

$s$ -sparse length- $n$ signals recover from about $s\log(n/s)$ random measurements, so 10 spikes in 1000 need about 150.
Recovery is $L_1$ minimisation, which seeks the sparsest consistent explanation; $L_2$ spreads and fails.
Noiseless exact recovery becomes stable error $C_0\eta$ plus best- $s$ -term error under noise.
The design must be incoherent or RIP-certified; structured sampling breaks the promise.
Set the solver tolerance to the noise level, never zero on real data.