  Suppose we are given a vector $f$ in $\R^N$. How many linear measurements do
we need to make about $f$ to be able to recover $f$ to within precision
$\epsilon$ in the Euclidean ($\ell_2$) metric? Or more exactly, suppose we are
interested in a class ${\cal F}$ of such objects--discrete digital signals,
images, etc; how many linear measurements do we need to recover objects from
this class to within accuracy $\epsilon$? This paper shows that if the objects
of interest are sparse or compressible in the sense that the reordered entries
of a signal $f \in {\cal F}$ decay like a power-law (or if the coefficient
sequence of $f$ in a fixed basis decays like a power-law), then it is possible
to reconstruct $f$ to within very high accuracy from a small number of random
measurements.
