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.
Copyright. All Rights Reserved.