{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,20]],"date-time":"2026-05-20T10:30:19Z","timestamp":1779273019540,"version":"3.51.4"},"reference-count":21,"publisher":"Springer Science and Business Media LLC","issue":"3","license":[{"start":{"date-parts":[[2008,6,5]],"date-time":"2008-06-05T00:00:00Z","timestamp":1212624000000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Found Comput Math"],"published-print":{"date-parts":[[2009,6]]},"DOI":"10.1007\/s10208-008-9031-3","type":"journal-article","created":{"date-parts":[[2008,6,4]],"date-time":"2008-06-04T15:25:32Z","timestamp":1212593132000},"page":"317-334","source":"Crossref","is-referenced-by-count":693,"title":["Uniform Uncertainty Principle and Signal Recovery via\u00a0Regularized Orthogonal Matching Pursuit"],"prefix":"10.1007","volume":"9","author":[{"given":"Deanna","family":"Needell","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Roman","family":"Vershynin","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2008,6,5]]},"reference":[{"key":"9031_CR1","doi-asserted-by":"crossref","unstructured":"E. Cand\u00e8s, Compressive sampling, in Proceedings of International Congress of Mathematics, vol.\u00a03, Madrid, Spain, 2006, pp.\u00a01433\u20131452.","DOI":"10.4171\/022-3\/69"},{"key":"9031_CR2","doi-asserted-by":"crossref","first-page":"489","DOI":"10.1109\/TIT.2005.862083","volume":"52","author":"E. Cand\u00e8s","year":"2006","unstructured":"E. Cand\u00e8s, J. Romberg, T. Tao, Robust uncertainty principles: exact signal reconstruction from highly incomplete frequency information, IEEE Trans. Inf. Theory 52, 489\u2013509 (2006).","journal-title":"IEEE Trans. Inf. Theory"},{"key":"9031_CR3","doi-asserted-by":"crossref","first-page":"5406","DOI":"10.1109\/TIT.2006.885507","volume":"52","author":"E. Cand\u00e8s","year":"2004","unstructured":"E. Cand\u00e8s, T. Tao, Near-optimal signal recovery from random projections: universal encoding strategies, IEEE Trans. Inf. Theory 52, 5406\u20135425 (2004).","journal-title":"IEEE Trans. Inf. Theory"},{"key":"9031_CR4","doi-asserted-by":"crossref","first-page":"4203","DOI":"10.1109\/TIT.2005.858979","volume":"51","author":"E.J. Cand\u00e8s","year":"2005","unstructured":"E.J. Cand\u00e8s, T. Tao, Decoding by linear programming, IEEE Trans. Inf. Theory 51, 4203\u20134215 (2005).","journal-title":"IEEE Trans. Inf. Theory"},{"key":"9031_CR5","doi-asserted-by":"crossref","unstructured":"A. Cohen, W. Dahmen, R. DeVore, Compressed sensing and k-term approximation, Manuscript (2007).","DOI":"10.1117\/12.725193"},{"key":"9031_CR6","unstructured":"Compressed sensing, webpage, http:\/\/www.dsp.ece.rice.edu\/cs\/ ."},{"key":"9031_CR7","doi-asserted-by":"crossref","first-page":"1289","DOI":"10.1109\/TIT.2006.871582","volume":"52","author":"D. Donoho","year":"2006","unstructured":"D. Donoho, Compressed sensing, IEEE Trans. Inf. Theory 52, 1289\u20131306 (2006).","journal-title":"IEEE Trans. Inf. Theory"},{"key":"9031_CR8","doi-asserted-by":"crossref","first-page":"6","DOI":"10.1109\/TIT.2005.860430","volume":"52","author":"D. Donoho","year":"2006","unstructured":"D. Donoho, M. Elad, V. Temlyakov, Stable recovery of sparse overcomplete representations in the presence of noise, IEEE Trans. Inf. Theory 52, 6\u201318 (2006).","journal-title":"IEEE Trans. Inf. Theory"},{"key":"9031_CR9","doi-asserted-by":"crossref","first-page":"185","DOI":"10.1016\/j.jat.2007.01.004","volume":"147","author":"D. Donoho","year":"2007","unstructured":"D. Donoho, M. Elad, V. Temlyakov, On the Lebesgue type inequalities for greedy approximation, J.\u00a0Approx. Theory 147, 185\u2013195 (2007).","journal-title":"J.\u00a0Approx. Theory"},{"key":"9031_CR10","doi-asserted-by":"crossref","first-page":"906","DOI":"10.1137\/0149053","volume":"49","author":"D. Donoho","year":"1989","unstructured":"D. Donoho, P. Stark, Uncertainty principles and signal recovery, SIAM J. Appl. Math. 49, 906\u2013931 (1989).","journal-title":"SIAM J. Appl. Math."},{"key":"9031_CR11","unstructured":"A. Gilbert, S. Muthukrishnan, M. Strauss, Approximation of functions over redundant dictionaries using coherence, in The 14th Annual ACM\u2013SIAM Symposium on Discrete Algorithms (2003)."},{"key":"9031_CR12","unstructured":"A. Gilbert, M. Strauss, J. Tropp, R. Vershynin, Algorithmic linear dimension reduction in the L1 norm for sparse vectors, submitted. Conference version, in Algorithmic Linear Dimension Reduction in the L 1 Norm for Sparse Vectors, Allerton, 2006. 44th Annual Allerton Conference on Communication, Control, and Computing."},{"key":"9031_CR13","doi-asserted-by":"crossref","unstructured":"A. Gilbert, M. Strauss, J. Tropp, R. Vershynin, One sketch for all: fast algorithms for compressed sensing, in STOC 2007. 39th ACM Symposium on Theory of Computing, San Diego, 2007, to appear.","DOI":"10.1145\/1250790.1250824"},{"key":"9031_CR14","unstructured":"Y. Lyubarskii, R. Vershynin, Uncertainty principles and vector quantization, submitted."},{"key":"9031_CR15","doi-asserted-by":"crossref","unstructured":"S. Mendelson, A. Pajor, N. Tomczak-Jaegermann, Uniform uncertainty principle for Bernoulli and subgaussian ensembles, Constr. Approx., submitted.","DOI":"10.1007\/s00365-007-9005-8"},{"key":"9031_CR16","unstructured":"H. Rauhut, On the impossibility of uniform recovery using greedy methods, in Sample Theory Signal Image Process., to appear."},{"key":"9031_CR17","doi-asserted-by":"crossref","unstructured":"M. Rudelson, R. Vershynin, On sparse reconstruction from Fourier and Gaussian measurements, Commun. Pure Appl. Math., to appear. Conference version in CISS 2006. 40th Annual Conference on Information Sciences and Systems, Princeton.","DOI":"10.1109\/CISS.2006.286463"},{"key":"9031_CR18","doi-asserted-by":"crossref","first-page":"385","DOI":"10.1145\/990308.990310","volume":"51","author":"D. Spielman","year":"2004","unstructured":"D. Spielman, S.-H. Teng, Smoothed analysis of algorithms: why the simplex algorithm usually takes polynomial time, J. ACM 51, 385\u2013463 (2004).","journal-title":"J. ACM"},{"key":"9031_CR19","doi-asserted-by":"crossref","first-page":"33","DOI":"10.1007\/s102080010029","volume":"3","author":"V. Temlyakov","year":"2003","unstructured":"V. Temlyakov, Nonlinear methods of approximation, Found. Comput. Math. 3, 33\u2013107 (2003).","journal-title":"Found. Comput. Math."},{"issue":"12","key":"9031_CR20","doi-asserted-by":"crossref","first-page":"4655","DOI":"10.1109\/TIT.2007.909108","volume":"53","author":"J.A. Tropp","year":"2007","unstructured":"J.A. Tropp, A.C. Gilbert, Signal recovery from random measurements via orthogonal matching pursuit, IEEE Trans. Inf. Theory 53(12), 4655\u20134666 (2007).","journal-title":"IEEE Trans. Inf. Theory"},{"key":"9031_CR21","doi-asserted-by":"crossref","unstructured":"R. Vershynin, Beyond Hirsch Conjecture: walks on random polytopes and smoothed complexity of the simplex method, submitted. Conference version in FOCS 2006. 47th Annual Symposium on Foundations of Computer Science, Berkeley, pp.\u00a0133\u2013142.","DOI":"10.1109\/FOCS.2006.19"}],"container-title":["Foundations of Computational Mathematics"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10208-008-9031-3.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s10208-008-9031-3\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10208-008-9031-3","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,29]],"date-time":"2019-05-29T07:05:09Z","timestamp":1559113509000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s10208-008-9031-3"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2008,6,5]]},"references-count":21,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2009,6]]}},"alternative-id":["9031"],"URL":"https:\/\/doi.org\/10.1007\/s10208-008-9031-3","relation":{},"ISSN":["1615-3375","1615-3383"],"issn-type":[{"value":"1615-3375","type":"print"},{"value":"1615-3383","type":"electronic"}],"subject":[],"published":{"date-parts":[[2008,6,5]]}}}