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

By E.J. Candes, Terence Tao. 2004

7,131 citations recorded by the source corpus.

Suppose we are given a vector f in a class FsubeRopf<sup>N </sup>, 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 epsi in the Euclidean (lscr<sub>2</sub>) 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 |f| (or of its coefficients in a fixed basis) obeys |f|<sub>(n)</sub>lesRmiddotn<sup>-1</sup>p/, where R>0 and p>0. Suppose that we take measurements y<sub>k</sub>=langf<sup># </sup>,X<sub>k</sub>rang,k=1,...,K, where the X<sub>k</sub> 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<sup>t</sup>, defined as the solution to the constraints y<sub>k</sub>=langf<sup># </sup>,X<sub>k</sub>rang with minimal lscr<sub>1</sub> norm, obeys parf-f<sup>#</sup>par<sub>lscr2</sub>lesC<sub>p </sub>middotRmiddot(K/logN)<sup>-r</sup>, 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

Subfields: Applied Mathematics, Computational Mechanics, Computer Vision and Pattern Recognition

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Applied Mathematics

  1. Roman Vershynin
  2. Richard Baraniuk
  3. E.J. Candes
  4. Justin K. Romberg
  5. Yonina C. Eldar
  6. Marco F. Duarte
  7. Martin J. Wainwright
  8. Joel A. Tropp

In Computational Mechanics

  1. E.J. Candes
  2. Richard Baraniuk
  3. Wotao Yin
  4. Marco F. Duarte
  5. Yonina C. Eldar
  6. Justin K. Romberg
  7. Lei Zhang
  8. Francis R. Bach

In Computer Vision and Pattern Recognition

  1. Luc Van Gool
  2. Lei Zhang
  3. Ming-Hsuan Yang
  4. Dacheng Tao
  5. Xiaogang Wang
  6. Trevor Darrell
  7. Yi Yang
  8. Andrew Zisserman

Citations in the corpus