Metadata
Abstract:
Suppose we are given a vector f in a class {\cal F} \subset{\BBR}^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 \epsilon in the Euclidean (\ell_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 \vert f\vert (or of its coefficients in a fixed basis) obeys \vert f\vert _{(n)} \le R \cdot n^{-1/p}, where R > 0 and p > 0. Suppose that we take measurements y_k = \langle f, X_k\rangle, k = 1, \ldots, K , where the X_k are N-dimensional Gaussian vectors with independent standard normal entries. Then for each...
Published in: IEEE Transactions on Information Theory ( Volume: 52, Issue: 12, December 2006)
