Robust uncertainty principles: exact signal reconstruction from highly incomplete frequency information

By E.J. Candes, Justin K. Romberg, Terence Tao. 2004

16,406 citations recorded by the source corpus.

This paper considers the model problem of reconstructing an object from incomplete frequency samples. Consider a discrete-time signal f/spl isin/C/sup N/ and a randomly chosen set of frequencies /spl Omega/. Is it possible to reconstruct f from the partial knowledge of its Fourier coefficients on the set /spl Omega/? A typical result of this paper is as follows. Suppose that f is a superposition of |T| spikes f(t)=/spl sigma//sub /spl tau//spl isin/T/f(/spl tau/)/spl delta/(t-/spl tau/) obeying |T|/spl les/C/sub M//spl middot/(log N)/sup -1/ /spl middot/ |/spl Omega/| for some constant C/sub M/>0. We do not know the locations of the spikes nor their amplitudes. Then with probability at least 1-O(N/sup -M/), f can be reconstructed exactly as the solution to the /spl lscr//sub 1/ minimization problem. In short, exact recovery may be obtained by solving a convex optimization problem. We give numerical values for C/sub M/ which depend on the desired probability of success. Our result may be interpreted as a novel kind of nonlinear sampling theorem. In effect, it says that any signal made out of |T| spikes may be recovered by convex programming from almost every set of frequencies of size O(|T|/spl middot/logN). Moreover, this is nearly optimal in the sense that any method succeeding with probability 1-O(N/sup -M/) would in general require a number of frequency samples at least proportional to |T|/spl middot/logN. The methodology extends to a variety of other situations and higher dimensions. For example, we show how one can reconstruct a piecewise constant (one- or two-dimensional) object from incomplete frequency samples - provided that the number of jumps (discontinuities) obeys the condition above - by minimizing other convex functionals such as the total variation of f.

Subfields: Computational Mechanics, Computer Vision and Pattern Recognition, Radiology, Nuclear Medicine and Imaging

How researchers see this paper

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

In Computational Mechanics

  1. E.J. Candes
  2. Richard Baraniuk
  3. Yonina C. Eldar
  4. Wotao Yin
  5. Francis R. Bach
  6. Marco F. Duarte
  7. Julien Mairal
  8. Martin J. Wainwright

In Computer Vision and Pattern Recognition

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

In Radiology, Nuclear Medicine and Imaging

  1. E.J. Candes
  2. David L. Donoho
  3. Chengbo Li
  4. Yonina C. Eldar
  5. Justin K. Romberg
  6. Richard Baraniuk
  7. Rick Chartrand
  8. Yin Zhang

Citations in the corpus