Near-optimal signal recovery from random projections: Universal encoding strategies?

Suppose we are given a vector f in a class F subset of R-N e.g., a class of digital signals or digital images. How many linear measurements do we need to make about f to be able to recover f to within precision is an element of in the Euclidean (l(2)) metric? This paper shows that if the objects of interest are sparse in a fixed basis or compressible, then it is possible to reconstruct f to within very high accuracy from a small number of random measurements by solving a simple linear program. More precisely, suppose that the,nth largest entry of the vector If I (or of its coefficients in a fixed basis) obeys vertical bar f vertical bar((n)) < R (.) n(-1/P), where R > 0 and p > 0. Suppose that we take measurements y(k) = < f, X-k >; k = 1..., K, where the X-k are N-dimensional Gaussian vectors with independent standard normal entries. Then for each f obeying the decay estimate above for some 0 < p < 1 and with overwhelming probability, our reconstruction f(#) defined as the solution to the constraints y(k) = < f(#), X-k > with minimal l(1) norm, obeys parallel to f - f(#)parallel to(l2) <= C-p (.) R (.) (K/log N)(-r), r = 1/p - 1/2 There is a sense in which this result is optimal; it is generally impossible to obtain a higher accuracy from any set of K measurements whatsoever. The methodology extends to various other random measurement ensembles; for example, we show that similar results hold if one observes a few randomly sampled Fourier coefficients of f. In fact, the results are quite general and require only two hypotheses on the measurement ensemble which are detailed.