Robust Uncertainty Principles: Exact Signal Reconstruction from Highly Incomplete Frequency Information

Emmanuel Candes California Institute of Technology Applied and Computational Mathematics

We consider the model problem of reconstructing an object from incomplete frequency samples---a problem which arises in many important medical and/or astrophysical applications. We ask whether it is possible to reconstruct a discrete signal from partial knowledge of its Fourier coefficients, i.e. from 5 or 10% of randomly selected coefficients.

We prove that if the signal f may be synthesized out of relatively few spikes, so that the number of spikes is roughly of the order of the number of visible Fourier coefficients divided by log N (N is the size of the signal), then the signal can be reconstructed exactly as the solution of a minimization problem, which among all signals fitting the observed coefficients, finds that object with minimun $\ell_1$ norm. In short, exact recovery may be obtained by solving a convex optimization problem; except for the logarithmic factor, the condition on the size of the support is sharp.

The methodology extends to a variety of other setups 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.

Finally, we show that similar exact reconstruction phenomena hold for other synthesis/measurement pairs. Suppose one is given a pair of of bases $({\cal B}_1, {\cal B}_2)$ and randomly selected coefficients of an object $f$ in one basis, say ${\cal B}_2$. Then, $f$ can be recovered exactly provided that it may be synthesized as a sparse superposition of elements in ${\cal B}_1$. The relationship between the number of nonzero terms in ${\cal B}_1$ and the number of observed coefficients depends upon the {\em incoherence} between the two bases. The more incoherent, the fewer coefficients needed.

This is joint work with Justin Romberg and Terence Tao.