Robust uncertainty principles: exact signal reconstruction from highly incomplete frequency information¶
Why this mattered¶
This paper helped turn sparse recovery from a heuristic hope into a rigorous sampling principle. Classical intuition said that exact reconstruction required sampling at rates tied to ambient dimension or bandwidth; Candès, Romberg, and Tao showed that, for signals sparse in the time domain, randomly chosen Fourier measurements on the order of the sparsity times a logarithmic factor could be enough. Just as important, recovery did not require knowing the spike locations in advance: a tractable convex program, l1 minimization, could find the signal exactly with high probability. That made sparsity a mathematically actionable substitute for full information.
The paradigm shift was that incomplete, apparently underdetermined measurements could be not merely denoised or approximated, but exactly inverted under structural assumptions. The paper framed this as a nonlinear sampling theorem: the effective complexity of the object, not the nominal dimension of the measurement space, governed reconstruction. Its near-optimal lower-bound discussion also mattered, because it placed the result close to an information-theoretic limit rather than presenting it as a numerical coincidence.
Together with closely related work by Donoho and by Candès and Tao, this result became one of the foundations of compressed sensing. It helped justify new acquisition strategies in MRI, imaging, radar, astronomy, and sensor networks, where measuring fewer linear samples can reduce scan time, power, or hardware burden. Later breakthroughs in sparse approximation, matrix completion, total-variation recovery, phase retrieval, and high-dimensional statistics inherited the same central lesson: randomness plus convex optimization can make hidden low-complexity structure recoverable from dramatically incomplete data.
Abstract¶
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.
Related¶
- cite → Nonlinear total variation based noise removal algorithms — Compressed sensing cites total-variation denoising because sparse-gradient regularization underlies exact reconstruction from incomplete measurements.
- enables → Robust principal component analysis? — Compressed sensing's exact recovery guarantees enable robust PCA's convex-programming recovery of low-rank matrices from incomplete or corrupted data.
- cite ← Robust principal component analysis? — Robust PCA builds on compressed sensing uncertainty principles for exact recovery from incomplete or corrupted observations.
- cite ← A Singular Value Thresholding Algorithm for Matrix Completion — Singular value thresholding cites Candes, Romberg, and Tao's uncertainty principles as a compressed-sensing foundation for exact recovery from incomplete measurements.
- cite ← Compressed sensing — Candes and Tao's compressed sensing paper builds directly on their robust uncertainty principle showing exact recovery from incomplete Fourier samples.
- enables ← Nonlinear total variation based noise removal algorithms — Total variation minimization supplied the sparsity-promoting reconstruction principle used in compressed sensing recovery from incomplete frequency samples.