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

This paper considers the model problem of reconstructing an object from incomplete frequency samples. Consider a discrete-time signal f is an element of C-N and a randomly chosen set of frequencies Q. Is it possible to reconstruct f from the partial knowledge of its Fourier coefficients on the set Q? A typical result of this paper is as follows. Suppose that f is a superposition of vertical bar T vertical bar spikes f(t) = E-tau is an element of T f(tau)delta(t - tau) obeying vertical bar T vertical bar <= C-M (.) (logN)(-1 .) vertical bar ohm vertical bar for some constant C-M > 0. We do not know the locations of the spikes nor their amplitudes. Then with probability at least 1 - O(N-m), f can be reconstructed exactly as the solution to the l(1) minimization problem min/g Sigma(N-1)/t=0 vertical bar g(t)vertical bar, s.t. (g) over cap(omega) = (f) over cap(omega) for al omega is an element of ohm In short, exact recovery may be obtained by solving a convex optimization problem. We give numerical values for Cm 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 vertical bar T vertical bar spikes may be recovered by convex programming from almost every set of frequencies of size O(vertical bar T vertical bar (.) log N). Moreover, this is nearly optimal in the sense that any method succeeding with probability 1 - O(N-M) would in general require a number of frequency samples at least proportional to vertical bar T vertical bar (.) log N. 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.