%0 Journal Article %1 1580791 %A Candès, Emmanuel J. %A Romberg, Justin %A Tao, Terence %D 2006 %J Information Theory, IEEE Transactions on %K compressed.sensing uncertainty %N 2 %P 489--509 %R 10.1109/TIT.2005.862083 %T Robust Uncertainty Principles: Exact Signal Reconstruction from Highly Incomplete Frequency Information %V 52 %X This paper considers the model problem of reconstructing an object from incomplete frequency samples. Consider a discrete-time signal f∈C^N and a randomly chosen set of frequencies Ω. Is it possible to reconstruct f from the partial knowledge of its Fourier coefficients on the set Ω? A typical result of this paper is as follows. Suppose that f is a superposition of |T| spikes f(t)=σ_τ∈Tf(τ)δ(t-τ) obeying |T|≤C_M·(log N)^-1 · |Ω| 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 ℓ₁ minimization problem. In short, exact recovery may be obtained by solving a convex optimization problem. We give numerical values for C_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|·logN). 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 |T|·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.

@article{1580791, abstract = {This paper considers the model problem of reconstructing an object from incomplete frequency samples. Consider a discrete-time signal f∈C^N and a randomly chosen set of frequencies Ω. Is it possible to reconstruct f from the partial knowledge of its Fourier coefficients on the set Ω? A typical result of this paper is as follows. Suppose that f is a superposition of |T| spikes f(t)=σ_τ∈Tf(τ)δ(t-τ) obeying |T|≤C_M·(log N)^-1 · |Ω| 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 ℓ₁ minimization problem. In short, exact recovery may be obtained by solving a convex optimization problem. We give numerical values for C_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|·logN). 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 |T|·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.}, added-at = {2013-05-30T04:20:11.000+0200}, author = {Cand{\`e}s, Emmanuel J. and Romberg, Justin and Tao, Terence}, biburl = {https://www.bibsonomy.org/bibtex/2f3e63909ebf5bdfdb7e841179e704c93/ytyoun}, doi = {10.1109/TIT.2005.862083}, interhash = {ff0f531efa2260488be3523d4e72a99d}, intrahash = {f3e63909ebf5bdfdb7e841179e704c93}, issn = {0018-9448}, journal = {Information Theory, IEEE Transactions on}, keywords = {compressed.sensing uncertainty}, number = 2, pages = {489--509}, timestamp = {2015-12-10T09:45:43.000+0100}, title = {Robust Uncertainty Principles: Exact Signal Reconstruction from Highly Incomplete Frequency Information}, volume = 52, year = 2006 }