Near Optimal Signal Recovery From Random Projections: Universal Encoding Strategies?

Suppose we are given a vector f in N. How many linear measurements do we need to make about f to be able to recover f to within precision ε in the Euclidean (₂) metric? Or more exactly, suppose we are interested in a class 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 ε? This paper shows that if the objects of interest are sparse or compressible in the sense that the reordered entries of a signal f 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.