Robust uncertainty principles: exact signal reconstruction from highly incomplete frequency information Export

@article{citeulike:1180971, 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)=\σ_{\τ\∈T}f(\τ)\δ(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 \&\#8467;₁ 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.}, author = {Candes, E. J. and Romberg, J. and Tao, T.}, booktitle = {Information Theory, IEEE Transactions on}, citeulike-article-id = {1180971}, citeulike-linkout-0 = {http://dx.doi.org/10.1109/TIT.2005.862083}, citeulike-linkout-1 = {http://ieeexplore.ieee.org/xpls/abs_all.jsp?arnumber=1580791}, doi = {10.1109/TIT.2005.862083}, journal = {Information Theory, IEEE Transactions on}, keywords = {approximation, convex, estimation, optimization, processing, signal, sparse}, number = {2}, pages = {489--509}, posted-at = {2008-08-27 10:41:03}, priority = {3}, title = {Robust uncertainty principles: exact signal reconstruction from highly incomplete frequency information}, url = {http://dx.doi.org/10.1109/TIT.2005.862083}, volume = {52}, year = {2006} }

TY - JOUR ID - citeulike:1180971 L3 - citeulike-article-id:1180971 N2 - 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. IS - 2 JF - Information Theory, IEEE Transactions on EP - 509 TI - Robust uncertainty principles: exact signal reconstruction from highly incomplete frequency information VL - 52 T2 - Information Theory, IEEE Transactions on SP - 489 KW - approximation KW - convex KW - estimation KW - optimization KW - processing KW - signal KW - sparse AU - Candes, EJ AU - Romberg, J AU - Tao, T PY - 2006/// UR - http://dx.doi.org/10.1109/TIT.2005.862083 ER -