Sparsity and incoherence in compressive sampling

By E.J. Candes, Justin K. Romberg. 2006

2,190 citations recorded by the source corpus.

We consider the problem of reconstructing a sparse signal from a limited number of linear measurements. Given m randomly selected samples of Ux0, where U is an orthonormal matrix, we show that ℓ1 minimization recovers x0 exactly when the number of measurements exceeds where S is the number of nonzero components in x0 and μ is the largest entry in U properly normalized: . The smaller μ is, the fewer samples needed. The result holds for ‘most’ sparse signals x0 supported on a fixed (but arbitrary) set T. Given T, if the sign of x0 for each nonzero entry on T and the observed values of Ux0 are drawn at random, the signal is recovered with overwhelming probability. Moreover, there is a sense in which this is nearly optimal since any method succeeding with the same probability would require just about as many samples.

Subfields: Applied Mathematics, Biomedical Engineering, Computational Mechanics

View Paper: https://www.semanticscholar.org/paper/73f818adda65015f5cc2d48a18c7cf9169b62510

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. Richard Baraniuk
  2. Marco F. Duarte
  3. E.J. Candes
  4. Justin K. Romberg
  5. Yonina C. Eldar
  6. Joel A. Tropp
  7. Michael B. Wakin
  8. Robert D. Nowak

In Biomedical Engineering

  1. Marco F. Duarte
  2. Richard Baraniuk
  3. Yonina C. Eldar
  4. Justin K. Romberg
  5. E.J. Candes
  6. Holger Rauhut
  7. Wotao Yin
  8. Prateek Jain

In Computational Mechanics

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

Citations in the corpus