Compressed Sensing

In 1928 Harry Nyquist proved what every engineer since has treated as gospel: to capture a signal perfectly you must sample it at at least twice its highest frequency. Miss that rate and information is lost forever — or so everyone believed.

Compressed sensing — developed independently by Emmanuel Candès, Justin Romberg & Terence Tao and by David Donoho in landmark 2006 papers — overturned that intuition. The key insight is sparsity: most real-world signals are sparse, meaning they contain only a few non-zero components when expressed in the right basis (frequency, wavelet, pixel-difference, etc.).

If a signal of length N has only k non-zero frequencies, and k is much smaller than N, then you do not need N samples. A small number of random linear measurements — roughly $k \cdot \log(N/k)$ — suffice to recover the signal exactly, via a convex optimization called $\ell_1$ minimization (basis pursuit). The recovery is provably exact (not approximate) when the measurement matrix satisfies a geometric condition called the Restricted Isometry Property (RIP), which random Gaussian and Bernoulli matrices satisfy with overwhelming probability.

The result is not approximate, not probabilistic in the sense of being wrong sometimes — it is a theorem: given RIP and sparsity, $\ell_1$ minimization recovers the original signal from the compressed measurements.

Below is a sparse signal: 64 values in the frequency domain, only a few of them non-zero. The demo takes a random subset of measurements (far fewer than 64) and then recovers the original signal using $\ell_1$ minimization.

<p class="hint">{{hint}}</p>
<div class="controls">
  <label>{{lbl_measurements}} <b id="mLabel">20</b> {{lbl_of_n}}
    <input type="range" id="mSlider" min="8" max="64" value="20">
  </label>
  <label>{{lbl_sparsity}} <b id="kLabel">4</b>
    <input type="range" id="kSlider" min="1" max="12" value="4">
  </label>
</div>
<div class="chart-row">
  <div class="chart-box">
    <div class="chart-title">{{chart_original}}</div>
    <canvas id="origCanvas" width="300" height="100"></canvas>
  </div>
  <div class="chart-box">
    <div class="chart-title">{{chart_recovered}}</div>
    <canvas id="recCanvas" width="300" height="100"></canvas>
  </div>
</div>
<div class="btns">
  <button id="newSignal" type="button">{{btn_new_signal}}</button>
  <button id="recover" type="button">{{btn_recover}}</button>
</div>
<div class="status" id="status">{{status_initial}}</div>

* { box-sizing: border-box; }
body { font-family: system-ui, sans-serif; color: #222; margin: 0; padding: 4px; }
.hint { font-size: .87rem; color: #444; margin: 0 0 .8rem; line-height: 1.5; }
.controls { display: flex; flex-direction: column; gap: .4rem; margin-bottom: .8rem; font-size: .88rem; }
label { display: flex; align-items: center; gap: .4rem; }
input[type=range] { flex: 1; max-width: 180px; }
.chart-row { display: flex; gap: 10px; flex-wrap: wrap; margin-bottom: .7rem; }
.chart-box { flex: 1 1 280px; }
.chart-title { font-size: .8rem; color: #555; margin-bottom: 3px; font-weight: 600; }
canvas { width: 100%; height: 100px; border: 1px solid #d0d7de; border-radius: 6px; background: #f8fafb; display: block; }
.btns { display: flex; gap: .5rem; flex-wrap: wrap; margin-bottom: .5rem; }
button { font: 600 13px system-ui; padding: .4rem .85rem; border: 1px solid #1d3557;
         background: #1d3557; color: #fff; border-radius: 8px; cursor: pointer; }
.status { font-size: .9rem; font-weight: 600; min-height: 1.3em; }
.status.ok { color: #0a7d33; }
.status.bad { color: #c92f3c; }
.status.info { color: #444; }

// Code not found

Slide the measurements control to see how many random samples are needed. With enough measurements the recovery is perfect — the reconstructed signal matches the original exactly. Drop below the threshold and the recovery degrades. Notice that checking whether a given solution is consistent with the measurements is instant, but finding the sparsest consistent solution is what $\ell_1$ minimization does in polynomial time — a lucky fact that makes compressed sensing practical.

The mathematics behind compressed sensing rests on three interlocking ideas:

• Sparsity. A signal x of length N is k-sparse if at most k of its entries are non-zero (in some basis). Natural images, audio, and medical scans are all sparse in suitable bases.
• The Restricted Isometry Property (RIP). A measurement matrix $\Phi$ (of size $m \times N$, with $m \ll N$) satisfies RIP of order k if it nearly preserves the Euclidean norm of every k-sparse vector. Candès & Tao proved in 2005 that RIP is sufficient for exact recovery. Random matrices with independent Gaussian or $\pm 1$ Bernoulli entries satisfy RIP with high probability as long as $m \gtrsim k \log(N/k)$ — no special structure needed.
• $\ell_1$ minimization (basis pursuit). Given measurements $y = \Phi x$, finding the sparsest $\hat{x}$ consistent with $y$ is, in general, NP-hard (it's equivalent to finding the $\ell_0$ solution). The revolutionary observation is that the $\ell_1$ relaxation — minimize $\|\hat{x}\|_1$ subject to $\Phi\hat{x} = y$ — gives the same answer as $\ell_0$ when $\Phi$ satisfies RIP. $\ell_1$ minimization is a linear program solvable in polynomial time.

The field is sometimes linked to dimensionality reduction: both ask how much a high-dimensional object can be compressed without losing its structure. The RIP matrix is a kind of random projection that preserves inner products among sparse vectors — a cousin of the Johnson–Lindenstrauss lemma.

Compressed sensing is a solved problem in the sense that the existence and polynomial-time computability of exact sparse recovery is proven. Open questions remain about the precise constants, the best algorithms in practice, and extensions to structured sparsity and noisy measurements.

Compressed sensing is not just a theorem — it reshaped entire engineering disciplines:

• MRI acceleration. MRI machines sample k-space (the Fourier domain). By taking fewer, random k-space lines and recovering via $\ell_1$ minimization, scan times have been cut by 4–10×. Patients spend less time in the scanner, and motion artifacts decrease. This was one of the earliest and most impactful real-world deployments.
• Single-pixel cameras. A camera that takes one measurement per random mask pattern — essentially one pixel at a time — can reconstruct a full image from far fewer shots than the image resolution. Rice University's single-pixel camera demonstrated this in 2006.
• Radar and sonar. Radar scenes are sparse in angle-range space. Compressed sensing allows shorter pulses and lower bandwidth while recovering the full scene.
• Genomics and medical testing. Group testing (pool many samples, test the pool) is a form of compressed sensing: if few samples are positive, the compressed measurements reveal which.
• Astronomy. Radio telescope arrays measure sparse sky images. Compressed sensing dramatically reduced the number of antennas needed for the same angular resolution.

Beyond hardware, compressed sensing influenced the broader understanding of dimensionality reduction and random projections in machine learning.

For a century, engineers knew they needed at least two samples per hertz. Compressed sensing proved that number was wildly pessimistic — if the signal is sparse.

The theorem is elegant: take $k \log(N/k)$ random measurements of a k-sparse signal of length N, solve a convex program, and recover the original exactly. Not approximately. Exactly. The proof, given by Candès, Romberg & Tao and independently by Donoho in 2006, reshaped signal processing, medical imaging, radar, and beyond.

Sparsity is the key assumption. It holds in a surprising breadth of nature — most signals in physics, biology, and engineering are compressible. The next time you have an MRI scan that takes minutes instead of hours, you're experiencing compressed sensing at work.