Suppose we are given an n-dimensional vector S (signal). How many linear measurements do we need to make about this signal to be able to recover S to within a small error in the Euclidean metric? Or more exactly, suppose we are interested in a class of such objects---discrete digital signals, images, etc; how many linear measurements do we need to recover objects from this class to within
high accuracy? This talk shows that if the objects of interest are sparse or
compressible in the sense that the reordered entries of a signal S decay like a power-law (or if the coefficient sequence of S in a fixed basis decays like a power-law), then it is possible to
reconstruct S to within very high accuracy from a small number of random measurements. A typical result is as follows: suppose the rearranged (by decreasing order of magnitude) entries of S decay
like the power-law $k^{-1/p}$; we take measurements by correlating the signal with $K$ $N$-dimensional Gaussian vectors with
independent standard normal entries; then with overwhelming probability, one can reconstruct an object S* from the data of these $K$ random coefficients only with the property that the
reconstruction error is at most $O(K/log N)^{-r}$, $r = 1/p - 1/2$. Moreover, the reconstruction can be obtained by solving a linear program which searches among all candidates fitting the
observed data, for that with minimum l1-norm.
The methodology extends to various other random measurement ensembles; for example, we show that similar results hold if one observes few
randomly sampled Fourier coefficients of S. Indeed, our results are quite general and require only two hypotheses on the measurement
ensemble, which we call the uniform uncertainty principle property and the exact reconstruction property.
Alternatively, we can think of the random measurement process as some kind of universal encoder. The encoder essentially correlates
the signal with white-noise and the decoder upon receiving such quantized random measurements, reconstruct an approximate signal by
minimizing the l1-norm. There is a sense in which this encoder/decoder pair asymptotically achieves nearly optimal information theoretic limits.
This is joint work with Terence Tao (UCLA).
Copyright. All Rights Reserved.