◄ WORLD V · SONNY 5DART 303 · a helldive at the net

COMPRESSED SENSING recover a big sparse signal from far fewer measurements than its length

Classical sampling says you need as many measurements as unknowns. Compressed sensing breaks that when the signal is sparse — mostly zeros in some basis. Then a handful of random linear measurements, far fewer than the signal's length, suffice to reconstruct it exactly — by finding the sparsest signal consistent with the measurements (an L₁ minimization). It is why an MRI can scan in a quarter of the time and a single-pixel camera can image at all. The recovery is caused by sparsity: it is that structure — few nonzeros — that makes an underdetermined system have a unique answer. Remove the sparsity and the same few measurements determine nothing.

THE TECHNIQUE sparse signal + few random measurements → unique reconstruction

A 1-sparse signal (one nonzero in a long vector). The demo recovers both its value and position from just two measurements: live demo







  
HISTORY & CREDIT Candès-Romberg-Tao · Donoho, 2006

  
“You need as many measurements as unknowns.” — not for a sparse signal: a few random projections plus the assumption of sparsity pin it down uniquely. The structure buys back the missing measurements. cited

  
2006 · Emmanuel Candès, Justin Romberg & Terence Tao and, independently, David Donoho — exact recovery of sparse signals from few measurements via L₁ minimization (the restricted isometry property).
now · rapid MRI, the single-pixel camera, radar, genomics.

  
Few random measurements, plus “the answer is sparse,” and the underdetermined system has one solution. Sparsity is the structure that makes recovery possible at all. Candès-Tao / Donoho 2006






  
RECOMMEND FOR I-13 1-sparse signal recovered from 2 measurements, computed

  
On the canonical compiler, a 1-sparse signal (value 7 at position 3) is recovered from two measurements — a sum m₂=7 gives the value, a position-weighted sum m₁=21 gives the position 21/7=3:

  
$ i13 run rec_compressed.i13   # recover a 1-sparse signal from 2 measurements
m1 = 21              -- position-weighted measurement
m2 = 7               -- plain sum
recovered_val = 7    -- the value = m2
recovered_pos = 3    -- the position = m1/m2

  
Recommend: compressed sensing is reconstruction where sparsity is the load-bearing structure, and i13 enacts the recovery arithmetic. From two measurements — a sum 7 and a position-weighted sum 21 — it recovers a 1-sparse signal's value 7 and position 3, fewer numbers than the signal is long. This is impossible in general: two measurements cannot determine a long vector. It is possible only because the signal is 1-sparse — the structure that collapses the underdetermined system to one answer. Change the sparsity assumption and the same two measurements determine nothing; the recovery is caused by the structure, exactly the batch's axis.