Compressed sensing

Summary

Compressed sensing is the recovery of a sparse vector from far fewer linear measurements than its length. Let $x \in \R^N$ have at most $s$ nonzero entries, and let $y = Ax$ for a suitable $m \times N$ matrix $A$ with $m$ much smaller than $N$. Then $x$ can be found from $y$ by solving a convex problem. The key sufficient condition on $A$ is the restricted isometry property, which random matrices satisfy with high probability when $m$ is of order $s \log(N/s)$. It was developed by Candès, Romberg, Tao and Donoho in the mid-2000s and is used in medical imaging and signal processing.