Introduction

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⋅log⁡(N/k)k \cdot \log(N/k) — suffice to recover the signal exactly, via a convex optimization called ℓ1\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, ℓ1\ell_1 minimization recovers the original signal from the compressed measurements.

Sample and Recover

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 ℓ1\ell_1 minimization.

<p class="hint">A <b>sparse signal</b> has only a few non-zero frequencies. Slide to control how many random measurements are taken, then click <b>Recover Signal</b> to reconstruct it from those measurements using basis pursuit (ℓ₁ minimization via ISTA).</p>
<div class="controls">
  <label>Measurements: <b id="mLabel">20</b> of 64
    <input type="range" id="mSlider" min="8" max="64" value="20">
  </label>
  <label>Sparsity (non-zero tones): <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">Original signal (frequency domain)</div>
    <canvas id="origCanvas" width="300" height="100"></canvas>
  </div>
  <div class="chart-box">
    <div class="chart-title">Recovered signal</div>
    <canvas id="recCanvas" width="300" height="100"></canvas>
  </div>
</div>
<div class="btns">
  <button id="newSignal" type="button">New random signal</button>
  <button id="recover" type="button">Recover Signal</button>
</div>
<div class="status" id="status">Click "Recover Signal" to reconstruct from measurements.</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; }

const fmt = (s, v) => s.replace(/%(\w+)%/g, (_, k) => String(v[k] ?? ''));
// Compressed Sensing demo
// Signal: sparse in the frequency domain (N=64 real DFT bins).
// Measurement: Phi is m x N random Gaussian matrix (normalized columns).
// Recovery: ISTA (Iterative Shrinkage-Thresholding) to solve
//   minimize ||x||_1  subject to  Phi*x ≈ y
// which is equivalent to basis pursuit for noiseless case.

const N = 64;
let origX = new Float64Array(N);    // sparse frequency coefficients
let mCount = 20;
let kCount = 4;

// --- Utility ---
function randn() {
  // Box-Muller
  let u = 0, v = 0;
  while (u === 0) u = Math.random();
  while (v === 0) v = Math.random();
  return Math.sqrt(-2 * Math.log(u)) * Math.cos(2 * Math.PI * v);
}

// Build m x N measurement matrix with iid N(0,1/m) entries
function buildPhi(m, n) {
  const phi = [];
  for (let i = 0; i < m; i++) {
    phi[i] = new Float64Array(n);
    for (let j = 0; j < n; j++) phi[i][j] = randn() / Math.sqrt(m);
  }
  return phi;
}

// Matrix-vector product: Phi * x  (returns Float64Array of length m)
function matvec(phi, x) {
  const m = phi.length, n = x.length;
  const y = new Float64Array(m);
  for (let i = 0; i < m; i++) {
    let s = 0;
    for (let j = 0; j < n; j++) s += phi[i][j] * x[j];
    y[i] = s;
  }
  return y;
}

// Matrix-vector product: Phi^T * r  (returns Float64Array of length n)
function matvecT(phi, r) {
  const m = phi.length, n = phi[0].length;
  const out = new Float64Array(n);
  for (let i = 0; i < m; i++) {
    for (let j = 0; j < n; j++) out[j] += phi[i][j] * r[i];
  }
  return out;
}

// Soft-threshold: sign(x) * max(|x|-lambda, 0)
function softThresh(x, lam) {
  const out = new Float64Array(x.length);
  for (let i = 0; i < x.length; i++) {
    const abs = Math.abs(x[i]);
    out[i] = abs > lam ? (x[i] > 0 ? 1 : -1) * (abs - lam) : 0;
  }
  return out;
}

// ISTA for basis pursuit: minimize ||x||_1 s.t. Phi*x = y
// Uses step size 1/L where L = largest eigenvalue estimate (power iteration)
function ista(phi, y, iters) {
  const n = phi[0].length;
  // Estimate spectral norm of Phi^T Phi via a few power iterations
  let v = new Float64Array(n).fill(1);
  for (let t = 0; t < 15; t++) {
    const tmp = matvecT(phi, matvec(phi, v));
    let norm = 0;
    for (let j = 0; j < n; j++) norm += tmp[j] * tmp[j];
    norm = Math.sqrt(norm);
    if (norm < 1e-12) break;
    for (let j = 0; j < n; j++) v[j] = tmp[j] / norm;
  }
  const tmp2 = matvecT(phi, matvec(phi, v));
  let L = 0;
  for (let j = 0; j < n; j++) L += tmp2[j] * v[j];
  if (L < 1e-12) L = 1;

  const step = 1 / L;
  // lambda starts high and decreases (continuation)
  const PhiTy = matvecT(phi, y);
  let maxPhiTy = 0;
  for (let j = 0; j < n; j++) if (Math.abs(PhiTy[j]) > maxPhiTy) maxPhiTy = Math.abs(PhiTy[j]);
  let lambda = maxPhiTy * 0.5;

  let x = new Float64Array(n);
  for (let stage = 0; stage < 6; stage++) {
    lambda *= 0.35;
    for (let t = 0; t < iters; t++) {
      const res = matvec(phi, x);
      for (let i = 0; i < res.length; i++) res[i] = y[i] - res[i];
      const grad = matvecT(phi, res);
      const xNew = new Float64Array(n);
      for (let j = 0; j < n; j++) xNew[j] = x[j] + step * grad[j];
      x = softThresh(xNew, lambda * step);
    }
  }
  return x;
}

// Generate a new sparse signal
function genSignal(k, n) {
  const x = new Float64Array(n);
  const indices = [];
  while (indices.length < k) {
    const idx = Math.floor(Math.random() * n);
    if (!indices.includes(idx)) indices.push(idx);
  }
  for (const idx of indices) {
    x[idx] = (Math.random() > 0.5 ? 1 : -1) * (0.5 + Math.random() * 0.5);
  }
  return x;
}

// Drawing
function drawBars(canvas, data, color, highlightColor) {
  const ctx = canvas.getContext('2d');
  const W = canvas.width, H = canvas.height;
  ctx.clearRect(0, 0, W, H);
  let maxVal = 0.01;
  for (let i = 0; i < data.length; i++) if (Math.abs(data[i]) > maxVal) maxVal = Math.abs(data[i]);
  const barW = W / data.length;
  const midY = H / 2;
  // zero line
  ctx.strokeStyle = '#ccc'; ctx.lineWidth = 1;
  ctx.beginPath(); ctx.moveTo(0, midY); ctx.lineTo(W, midY); ctx.stroke();
  for (let i = 0; i < data.length; i++) {
    const h = (Math.abs(data[i]) / maxVal) * (H / 2 - 4);
    const isNZ = Math.abs(data[i]) > 0.02;
    ctx.fillStyle = isNZ ? highlightColor : color;
    if (data[i] >= 0) {
      ctx.fillRect(i * barW + 1, midY - h, barW - 1, h);
    } else {
      ctx.fillRect(i * barW + 1, midY, barW - 1, h);
    }
  }
}

function l1norm(x) { let s=0; for(let i=0;i<x.length;i++) s+=Math.abs(x[i]); return s; }
function l2err(a, b) { let s=0; for(let i=0;i<a.length;i++) s+=(a[i]-b[i])**2; return Math.sqrt(s); }

function updateLabels() {
  document.getElementById('mLabel').textContent = mCount;
  document.getElementById('kLabel').textContent = kCount;
}

function doRecover() {
  const statusEl = document.getElementById('status');
  statusEl.textContent = 'Computing recovery...';
  statusEl.className = 'status info';
  // Give the browser a chance to repaint
  setTimeout(() => {
    const phi = buildPhi(mCount, N);
    const y = matvec(phi, origX);
    const recX = ista(phi, y, 80);
    drawBars(document.getElementById('recCanvas'), recX, '#93b4cc', '#1d6fa6');
    const err = l2err(origX, recX);
    const rel = err / (l1norm(origX) + 1e-12);
    if (rel < 0.05) {
      statusEl.textContent = fmt('✓ Perfect recovery! Error: %err% (%mCount% measurements of %N%)', { err: err.toFixed(4), mCount: mCount, N: N });
      statusEl.className = 'status ok';
    } else if (rel < 0.25) {
      statusEl.textContent = fmt('~ Approximate recovery. Error: %err% — try more measurements.', { err: err.toFixed(4) });
      statusEl.className = 'status bad';
    } else {
      statusEl.textContent = fmt('✗ Poor recovery. Error: %err% — too few measurements for this sparsity.', { err: err.toFixed(4) });
      statusEl.className = 'status bad';
    }
    console.log(fmt('CS demo | m=%mCount% k=%kCount% N=%N% err=%err%', { mCount: mCount, kCount: kCount, N: N, err: err.toFixed(6) }));
  }, 10);
}

function init() {
  origX = genSignal(kCount, N);
  drawBars(document.getElementById('origCanvas'), origX, '#a8c6dc', '#1d6fa6');
  drawBars(document.getElementById('recCanvas'), new Float64Array(N), '#dde3e8', '#999');
  document.getElementById('status').textContent = 'Click "Recover Signal" to reconstruct from measurements.';
  document.getElementById('status').className = 'status info';
}

document.getElementById('mSlider').addEventListener('input', e => { mCount = +e.target.value; updateLabels(); });
document.getElementById('kSlider').addEventListener('input', e => { kCount = +e.target.value; updateLabels(); });
document.getElementById('newSignal').addEventListener('click', init);
document.getElementById('recover').addEventListener('click', doRecover);

updateLabels();
init();
Result
Console

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 ℓ1\ell_1 minimization does in polynomial time — a lucky fact that makes compressed sensing practical.

The Real Complexity

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×Nm \times N, with m≪Nm \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 ±1\pm 1 Bernoulli entries satisfy RIP with high probability as long as m≳klog⁡(N/k)m \gtrsim k \log(N/k) — no special structure needed.
  • ℓ1\ell_1 minimization (basis pursuit). Given measurements y=Φxy = \Phi x, finding the sparsest x^\hat{x} consistent with yy is, in general, NP-hard (it's equivalent to finding the ℓ0\ell_0 solution). The revolutionary observation is that the ℓ1\ell_1 relaxation — minimize ∥x^∥1\|\hat{x}\|_1 subject to Φx^=y\Phi\hat{x} = y — gives the same answer as ℓ0\ell_0 when Φ\Phi satisfies RIP. ℓ1\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.

Where It Matters

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 ℓ1\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.

Conclusion

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 klog⁡(N/k)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.

Share this article

Pick a channel — or use your device's native share sheet.

Comments

Loading comments...

https://www.kipuhub.com/en/article/compressed-sensing/Content licensed under CC BY-NC 4.0.