Robust uncertainty principles: exact signal reconstruction from highly incomplete frequency information
Emmanuel J. Candès, Justin K. Romberg, Terence Tao
IEEE Transactions on Information Theory · 2006 · 15,628 citationsOpen access
No retraction on record in OpenAlex.Check Crossref now
Cite this paper
Candès, E. J., Romberg, J. K., & Tao, T. (2006). Robust uncertainty principles: exact signal reconstruction from highly incomplete frequency information. IEEE Transactions on Information Theory, 52(2), 489–509. https://doi.org/10.1109/tit.2005.862083
In text: (Candès et al., 2006)
Ask a question about this research
One question, free, no account. Anchorcite finds the papers, checks each against Crossref and links every sentence of the answer to the passage it comes from.
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 papers
- Compressed sensing2006
- Distributed Optimization and Statistical Learning via the Alternating Direction Method of Multipliers2011
- A Fast Iterative Shrinkage-Thresholding Algorithm for Linear Inverse Problems2009
- An Introduction To Compressive Sampling2008
- Signal Recovery From Random Measurements Via Orthogonal Matching Pursuit2007
Metadata from OpenAlex (CC0). Citations are generated from the published record.