Reconstruct a sparse signal from far fewer measurements than Nyquist using ℓ₁ minimization (LASSO).
128
8
40
0.02
0.010
Compressed Sensing (Candès-Romberg-Tao 2006, Donoho 2006): An s-sparse signal x ∈ ℝᴺ can be recovered from m = O(s log(N/s)) random measurements y = Ax ∈ ℝᵐ (m ≪ N) by solving:
min ‖x̂‖₁ subject to ‖Ax̂ − y‖₂ ≤ ε (LASSO: min ½‖Ax−y‖² + λ‖x‖₁).
RIP condition: A satisfies RIP of order 2s if (1−δ)‖x‖² ≤ ‖Ax‖² ≤ (1+δ)‖x‖² for all 2s-sparse x.
If δ_{2s} < √2−1 ≈ 0.414, exact recovery guaranteed. Gaussian random matrices satisfy RIP with m = O(s log(N/s)).
Phase transition: sharp boundary in (m/N, s/m) plane between recovery success and failure.