Robust uncertainty principles: exact signal reconstruction from highly incomplete frequency information. Candes, E., Romberg, J., & Tao, T. IEEE Transactions on Information Theory, 52(2):489–509, February, 2006. Conference Name: IEEE Transactions on Information Theory![Robust uncertainty principles: exact signal reconstruction from highly incomplete frequency information [link]](https://bibbase.org/img/filetypes/link.svg "link")
Paper doi abstract bibtex 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 \textbarT\textbar spikes f(t)=/spl sigma//sub /spl tau//spl isin/T/f(/spl tau/)/spl delta/(t-/spl tau/) obeying \textbarT\textbar/spl les/C/sub M//spl middot/(log N)/sup -1/ /spl middot/ \textbar/spl Omega/\textbar for some constant C/sub M/\textgreater0. 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 \textbarT\textbar spikes may be recovered by convex programming from almost every set of frequencies of size O(\textbarT\textbar/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 \textbarT\textbar/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.
@article{candes_robust_2006,
title = {Robust uncertainty principles: exact signal reconstruction from highly incomplete frequency information},
volume = {52},
issn = {1557-9654},
shorttitle = {Robust uncertainty principles},
url = {https://ieeexplore.ieee.org/abstract/document/1580791},
doi = {10.1109/TIT.2005.862083},
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 {\textbar}T{\textbar} spikes f(t)=/spl sigma//sub /spl tau//spl isin/T/f(/spl tau/)/spl delta/(t-/spl tau/) obeying {\textbar}T{\textbar}/spl les/C/sub M//spl middot/(log N)/sup -1/ /spl middot/ {\textbar}/spl Omega/{\textbar} for some constant C/sub M/{\textgreater}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 {\textbar}T{\textbar} spikes may be recovered by convex programming from almost every set of frequencies of size O({\textbar}T{\textbar}/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 {\textbar}T{\textbar}/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.},
language = {en},
number = {2},
urldate = {2024-03-19},
journal = {IEEE Transactions on Information Theory},
author = {Candes, E.J. and Romberg, J. and Tao, T.},
month = feb,
year = {2006},
note = {Conference Name: IEEE Transactions on Information Theory},
keywords = {/unread, Biomedical imaging, Convex optimization, Frequency, Image reconstruction, Linear programming, Mathematics, Robustness, Sampling methods, Signal processing, Signal reconstruction, Uncertainty, duality in optimization, free probability, image reconstruction, linear programming, random matrices, sparsity, total-variation minimization, trigonometric expansions, uncertainty principle},
pages = {489--509},
}
Downloads: 0
{"_id":"3mhi5vMfCKNFRmvRN","bibbaseid":"candes-romberg-tao-robustuncertaintyprinciplesexactsignalreconstructionfromhighlyincompletefrequencyinformation-2006","downloads":0,"creationDate":"2016-04-30T08:54:39.050Z","title":"Robust uncertainty principles: exact signal reconstruction from highly incomplete frequency information","author_short":["Candes, E.","Romberg, J.","Tao, T."],"year":2006,"bibtype":"article","biburl":"https://bibbase.org/zotero/zzhenry2012","bibdata":{"bibtype":"article","type":"article","title":"Robust uncertainty principles: exact signal reconstruction from highly incomplete frequency information","volume":"52","issn":"1557-9654","shorttitle":"Robust uncertainty principles","url":"https://ieeexplore.ieee.org/abstract/document/1580791","doi":"10.1109/TIT.2005.862083","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 \\textbarT\\textbar spikes f(t)=/spl sigma//sub /spl tau//spl isin/T/f(/spl tau/)/spl delta/(t-/spl tau/) obeying \\textbarT\\textbar/spl les/C/sub M//spl middot/(log N)/sup -1/ /spl middot/ \\textbar/spl Omega/\\textbar for some constant C/sub M/\\textgreater0. 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 \\textbarT\\textbar spikes may be recovered by convex programming from almost every set of frequencies of size O(\\textbarT\\textbar/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 \\textbarT\\textbar/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.","language":"en","number":"2","urldate":"2024-03-19","journal":"IEEE Transactions on Information Theory","author":[{"propositions":[],"lastnames":["Candes"],"firstnames":["E.J."],"suffixes":[]},{"propositions":[],"lastnames":["Romberg"],"firstnames":["J."],"suffixes":[]},{"propositions":[],"lastnames":["Tao"],"firstnames":["T."],"suffixes":[]}],"month":"February","year":"2006","note":"Conference Name: IEEE Transactions on Information Theory","keywords":"/unread, Biomedical imaging, Convex optimization, Frequency, Image reconstruction, Linear programming, Mathematics, Robustness, Sampling methods, Signal processing, Signal reconstruction, Uncertainty, duality in optimization, free probability, image reconstruction, linear programming, random matrices, sparsity, total-variation minimization, trigonometric expansions, uncertainty principle","pages":"489–509","bibtex":"@article{candes_robust_2006,\n\ttitle = {Robust uncertainty principles: exact signal reconstruction from highly incomplete frequency information},\n\tvolume = {52},\n\tissn = {1557-9654},\n\tshorttitle = {Robust uncertainty principles},\n\turl = {https://ieeexplore.ieee.org/abstract/document/1580791},\n\tdoi = {10.1109/TIT.2005.862083},\n\tabstract = {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 {\\textbar}T{\\textbar} spikes f(t)=/spl sigma//sub /spl tau//spl isin/T/f(/spl tau/)/spl delta/(t-/spl tau/) obeying {\\textbar}T{\\textbar}/spl les/C/sub M//spl middot/(log N)/sup -1/ /spl middot/ {\\textbar}/spl Omega/{\\textbar} for some constant C/sub M/{\\textgreater}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 {\\textbar}T{\\textbar} spikes may be recovered by convex programming from almost every set of frequencies of size O({\\textbar}T{\\textbar}/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 {\\textbar}T{\\textbar}/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.},\n\tlanguage = {en},\n\tnumber = {2},\n\turldate = {2024-03-19},\n\tjournal = {IEEE Transactions on Information Theory},\n\tauthor = {Candes, E.J. and Romberg, J. and Tao, T.},\n\tmonth = feb,\n\tyear = {2006},\n\tnote = {Conference Name: IEEE Transactions on Information Theory},\n\tkeywords = {/unread, Biomedical imaging, Convex optimization, Frequency, Image reconstruction, Linear programming, Mathematics, Robustness, Sampling methods, Signal processing, Signal reconstruction, Uncertainty, duality in optimization, free probability, image reconstruction, linear programming, random matrices, sparsity, total-variation minimization, trigonometric expansions, uncertainty principle},\n\tpages = {489--509},\n}\n\n\n\n\n\n\n\n","author_short":["Candes, E.","Romberg, J.","Tao, T."],"key":"candes_robust_2006","id":"candes_robust_2006","bibbaseid":"candes-romberg-tao-robustuncertaintyprinciplesexactsignalreconstructionfromhighlyincompletefrequencyinformation-2006","role":"author","urls":{"Paper":"https://ieeexplore.ieee.org/abstract/document/1580791"},"keyword":["/unread","Biomedical imaging","Convex optimization","Frequency","Image reconstruction","Linear programming","Mathematics","Robustness","Sampling methods","Signal processing","Signal reconstruction","Uncertainty","duality in optimization","free probability","image reconstruction","linear programming","random matrices","sparsity","total-variation minimization","trigonometric expansions","uncertainty principle"],"metadata":{"authorlinks":{}},"downloads":0,"html":""},"search_terms":["robust","uncertainty","principles","exact","signal","reconstruction","highly","incomplete","frequency","information","candes","romberg","tao"],"keywords":["/unread","biomedical imaging","convex optimization","frequency","image reconstruction","linear programming","mathematics","robustness","sampling methods","signal processing","signal reconstruction","uncertainty","duality in optimization","free probability","image reconstruction","linear programming","random matrices","sparsity","total-variation minimization","trigonometric expansions","uncertainty principle"],"authorIDs":[],"dataSources":["9cexBw6hrwgyZphZZ","vCGHbq7YMoL4xbgTv","nZHrFJKyxKKDaWYM8"]}