{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,29]],"date-time":"2025-10-29T02:50:33Z","timestamp":1761706233363},"reference-count":46,"publisher":"Springer Science and Business Media LLC","issue":"6","license":[{"start":{"date-parts":[[2007,8,10]],"date-time":"2007-08-10T00:00:00Z","timestamp":1186704000000},"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":[[2008,12]]},"DOI":"10.1007\/s10208-007-9005-x","type":"journal-article","created":{"date-parts":[[2007,8,9]],"date-time":"2007-08-09T11:05:15Z","timestamp":1186657515000},"page":"737-763","source":"Crossref","is-referenced-by-count":102,"title":["Random Sampling of Sparse Trigonometric Polynomials, II.\u00a0Orthogonal\u00a0Matching Pursuit versus\u00a0Basis Pursuit"],"prefix":"10.1007","volume":"8","author":[{"given":"Stefan","family":"Kunis","sequence":"first","affiliation":[]},{"given":"Holger","family":"Rauhut","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2007,8,10]]},"reference":[{"key":"9005_CR1","doi-asserted-by":"crossref","unstructured":"R. Baraniuk, M. Davenport, R. DeVore, and M. Wakin, A simple proof of the restricted isometry property for random matrices, Constr. Approx. (2007), to appear.","DOI":"10.1007\/s00365-007-9003-x"},{"key":"9005_CR2","doi-asserted-by":"crossref","first-page":"773","DOI":"10.1137\/S0036141003432316","volume":"36","author":"R. F. Bass","year":"2004","unstructured":"R. F. Bass and K. Gr\u00f6chenig, Random sampling of multivariate trigonometric polynomials, SIAM J. Math. Anal.\u00a036 (2004), 773\u2013795.","journal-title":"SIAM J. Math. Anal."},{"key":"9005_CR3","doi-asserted-by":"crossref","first-page":"33","DOI":"10.1080\/01621459.1962.10482149","volume":"57","author":"G. Bennett","year":"1962","unstructured":"G. Bennett, Probability inequalities for the sum of independent random variables, J. Amer. Statist. Assoc. 57 (1962), 33\u201345.","journal-title":"J. Amer. Statist. Assoc."},{"key":"9005_CR4","doi-asserted-by":"crossref","DOI":"10.1137\/1.9781611971484","volume-title":"Numerical Methods for Least Squares Problems","author":"\u00c5. Bj\u00f6rck","year":"1996","unstructured":"\u00c5. Bj\u00f6rck, Numerical Methods for Least Squares Problems, SIAM, Philadelphia, 1996."},{"key":"9005_CR5","first-page":"178","volume":"26","author":"A. B\u00f6ttcher","year":"2007","unstructured":"A. B\u00f6ttcher and D. Potts, Probability against condition number and sampling of multivariate trigonometric random polynomials, Electron. Trans. Numer. Anal. 26 (2007), 178\u2013189.","journal-title":"Electron. Trans. Numer. Anal."},{"key":"9005_CR6","doi-asserted-by":"crossref","DOI":"10.1017\/CBO9780511804441","volume-title":"Convex Optimization","author":"S. Boyd","year":"2004","unstructured":"S. Boyd and L. Vandenberghe, Convex Optimization, Cambridge University Press, Cambridge, 2004."},{"issue":"2","key":"9005_CR7","doi-asserted-by":"crossref","first-page":"227","DOI":"10.1007\/s10208-004-0162-x","volume":"6","author":"E. Cand\u00e8s","year":"2006","unstructured":"E. Cand\u00e8s and J. Romberg, Quantitative robust uncertainty principles and optimally sparse decompositions, Found. Comput. Math. 6(2) (2006), 227\u2013254.","journal-title":"Found. Comput. Math."},{"issue":"2","key":"9005_CR8","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, and T. Tao, Robust uncertainty principles: Exact signal reconstruction from highly incomplete frequency information, IEEE Trans. Inform. Theory 52(2) (2006), 489\u2013509.","journal-title":"IEEE Trans. Inform. Theory"},{"issue":"8","key":"9005_CR9","doi-asserted-by":"crossref","first-page":"1207","DOI":"10.1002\/cpa.20124","volume":"59","author":"E. Cand\u00e8s","year":"2006","unstructured":"E. Cand\u00e8s, J. Romberg, and T. Tao, Stable signal recovery from incomplete and inaccurate measurements, Comm. Pure Appl. Math. 59(8) (2006), 1207\u20131223.","journal-title":"Comm. Pure Appl. Math."},{"key":"9005_CR10","doi-asserted-by":"crossref","first-page":"5406","DOI":"10.1109\/TIT.2006.885507","volume":"52","author":"E. Cand\u00e8s","year":"2006","unstructured":"E. Cand\u00e8s and T. Tao, Near optimal signal recovery from random projections: Universal encoding strategies?, IEEE Trans. Inform. Theory 52 (2006), 5406\u20135425.","journal-title":"IEEE Trans. Inform. Theory"},{"key":"9005_CR11","doi-asserted-by":"crossref","first-page":"4203","DOI":"10.1109\/TIT.2005.858979","volume":"51","author":"E. Cand\u00e8s","year":"2005","unstructured":"E. Cand\u00e8s and T. Tao, Decoding by linear programming, IEEE Trans. Inform. Theory 51 (2005), 4203\u20134215.","journal-title":"IEEE Trans. Inform. Theory"},{"issue":"1","key":"9005_CR12","doi-asserted-by":"crossref","first-page":"33","DOI":"10.1137\/S1064827596304010","volume":"20","author":"S. S. Chen","year":"1999","unstructured":"S. S. Chen, D. L. Donoho, and M. A. Saunders, Atomic decomposition by basis pursuit, SIAM J. Sci. Comput. 20(1) (1999), 33\u201361.","journal-title":"SIAM J. Sci. Comput."},{"key":"9005_CR13","doi-asserted-by":"crossref","first-page":"1289","DOI":"10.1109\/TIT.2006.871582","volume":"52","author":"D. L. Donoho","year":"2006","unstructured":"D. L. Donoho, Compressed sensing, IEEE Trans. Inform. Theory 52 (2006), 1289\u20131306.","journal-title":"IEEE Trans. Inform. Theory"},{"key":"9005_CR14","doi-asserted-by":"crossref","first-page":"797","DOI":"10.1002\/cpa.20132","volume":"59","author":"D. L. Donoho","year":"2006","unstructured":"D. L. Donoho, For most large underdetermined systems of linear equations the minimal \u2113 1-norm solution is also the sparsest solution, Comm. Pure Appl. Math. 59 (2006), 797\u2013892.","journal-title":"Comm. Pure Appl. Math."},{"key":"9005_CR15","doi-asserted-by":"crossref","first-page":"9446","DOI":"10.1073\/pnas.0502269102","volume":"102","author":"D. L. Donoho","year":"2005","unstructured":"D. L. Donoho and J. Tanner, Sparse nonnegative solutions of underdetermined linear equations, Proc. Natl. Acad. Sci. USA 102 (2005), 9446\u20139451.","journal-title":"Proc. Natl. Acad. Sci. USA"},{"issue":"3","key":"9005_CR16","doi-asserted-by":"crossref","first-page":"549","DOI":"10.1016\/j.sigpro.2005.05.027","volume":"86","author":"D. L. Donoho","year":"2006","unstructured":"D. L. Donoho and Y. Tsaig, Extensions of compressed sensing, Signal Process\u00a086(3) (2006), 549\u2013571.","journal-title":"Signal Process"},{"key":"9005_CR17","doi-asserted-by":"crossref","unstructured":"A. Gilbert, S. Guha, P. Indyk, S. Muthukrishnan, and M. Strauss, Near-optimal sparse Fourier representations via sampling, in Proc. STOC, 2002.","DOI":"10.1145\/509907.509933"},{"key":"9005_CR18","doi-asserted-by":"crossref","unstructured":"A. Gilbert, S. Muthukrishnan, and M. Strauss, Improved time bounds for near-optimal sparse Fourier representation via sampling, in Proc. SPIE, 2005 (Wavelets XI), 2005.","DOI":"10.1117\/12.615931"},{"key":"9005_CR19","unstructured":"A. Gilbert and J. Tropp, Signal recovery from random measurements via orthogonal matching pursuit, IEEE Trans. Inform. Theory, to appear."},{"key":"9005_CR20","unstructured":"M. Grant, S. Boyd, and Y. Ye, CVX: Matlab software for disciplined convex programming, Version 1.0RC3, http:\/\/www.stanford.edu\/~boyd\/cvx , 2007."},{"key":"9005_CR21","doi-asserted-by":"crossref","unstructured":"R. Gribonval, B. Mailhe, H. Rauhut, K. Schnass, and P. Vandergheynst, Average case analysis of multichannel thresholding, in Proc. ICASSP 2007, 2007.","DOI":"10.1109\/ICASSP.2007.366370"},{"key":"9005_CR22","doi-asserted-by":"crossref","first-page":"255","DOI":"10.1109\/TIT.2005.860474","volume":"52","author":"R. Gribonval","year":"2006","unstructured":"R. Gribonval and P. Vandergheynst, On the exponential convergence of matching pursuits in quasi-incoherent dictionaries, IEEE Trans. Inform. Theory 52 (2006), 255\u2013261.","journal-title":"IEEE Trans. Inform. Theory"},{"key":"9005_CR23","unstructured":"K. Gr\u00f6chenig, H. Rauhut, and B. P\u00f6tscher, Learning trigonometric polynomials from random samples and exponential inequalities for eigenvalues of random matrices, Preprint, 2007."},{"key":"9005_CR24","unstructured":"J. Keiner, S. Kunis, and D. Potts, NFFT Software package, C subroutine library, http:\/\/www.tu-chemnitz.de\/~potts\/nfft , 2002\u20132006."},{"key":"9005_CR25","unstructured":"S. Kunis and H. Rauhut, OMP-NFFT, MatLab-toolbox for orthogonal matching pursuit on sparse trigonometric polynomials, http:\/\/www.tu-chemnitz.de\/~skunis\/software.php , 2006."},{"key":"9005_CR26","doi-asserted-by":"crossref","first-page":"3397","DOI":"10.1109\/78.258082","volume":"41","author":"S. Mallat","year":"1993","unstructured":"S. Mallat and Z. Zhang, Matching pursuit with time-frequency dictionaries, IEEE Trans. Signal Process. 41 (1993), 3397\u20133415.","journal-title":"IEEE Trans. Signal Process"},{"key":"9005_CR27","doi-asserted-by":"crossref","first-page":"357","DOI":"10.1137\/S0097539792239291","volume":"24","author":"Y. Mansour","year":"1995","unstructured":"Y. Mansour, Randomized interpolation and approximation of sparse polynomials, SIAM J. Comput.\u00a024 (1995), 357\u2013368.","journal-title":"SIAM J. Comput."},{"key":"9005_CR28","unstructured":"mosek ApS, MOSEK optimization software, http:\/\/www.mosek.com ."},{"key":"9005_CR29","doi-asserted-by":"crossref","first-page":"43","DOI":"10.1145\/355984.355989","volume":"8","author":"C. Paige","year":"1982","unstructured":"C. Paige and M. A. Saunders, LSQR: An algorithm for sparse linear equations and sparse least squares, ACM Trans. Math. Software 8 (1982), 43\u201371.","journal-title":"ACM Trans. Math. Software"},{"key":"9005_CR30","doi-asserted-by":"crossref","first-page":"3101","DOI":"10.1090\/S0002-9939-1995-1283561-0","volume":"123","author":"G. Peskir","year":"1993","unstructured":"G. Peskir, Best constants in Kahane\u2013Khintchine inequalities for complex Steinhaus functions, Proc. Amer. Math. Soc.\u00a0123 (1993), 3101\u20133111.","journal-title":"Proc. Amer. Math. Soc."},{"key":"9005_CR31","first-page":"249","volume-title":"Modern Sampling Theory: Mathematics and Applications","author":"D. Potts","year":"2001","unstructured":"D. Potts, G. Steidl, and M. Tasche, Fast Fourier transforms for nonequispaced data: A tutorial, in Modern Sampling Theory: Mathematics and Applications (J. J. Benedetto and P. Ferreira, Eds.), Chap.\u00a012, pp. 249\u2013274, Birkh\u00e4user, Boston, 2001."},{"key":"9005_CR32","doi-asserted-by":"crossref","first-page":"16","DOI":"10.1016\/j.acha.2006.05.002","volume":"22","author":"H. Rauhut","year":"2007","unstructured":"H. Rauhut, Random sampling of sparse trigonometric polynomials, Appl. Comput. Harmon. Anal.\u00a022 (2007), 16\u201342.","journal-title":"Appl. Comput. Harmon. Anal."},{"key":"9005_CR33","unstructured":"H. Rauhut, Stability results for random sampling of sparse trigonometric polynomials, Preprint, 2006."},{"key":"9005_CR34","unstructured":"H. Rauhut, On the impossibility of uniform recovery using greedy methods, Preprint, 2007."},{"key":"9005_CR35","unstructured":"J. Romberg and E. Candes, L1MAGIC, MatLab toolbox for basis pursuit, http:\/\/www.acm.caltech.edu\/l1magic , 2006."},{"key":"9005_CR36","doi-asserted-by":"crossref","first-page":"4019","DOI":"10.1155\/IMRN.2005.4019","volume":"64","author":"M. Rudelson","year":"2005","unstructured":"M. Rudelson and R. Vershynin, Geometric approach to error correcting codes and reconstruction of signals, Int. Math. Res. Not. 64 (2005), 4019\u20134041.","journal-title":"Int. Math. Res. Not."},{"key":"9005_CR37","doi-asserted-by":"crossref","unstructured":"M. Rudelson and R. Vershynin, Sparse reconstruction by convex relaxation: Fourier and Gaussian measurements, in Proc. CISS 2006 (40th Annual Conference on Information Sciences and Systems), 2006.","DOI":"10.1109\/CISS.2006.286463"},{"key":"9005_CR38","doi-asserted-by":"crossref","unstructured":"M. Rudelson and R. Vershynin, On sparse reconstruction from Fourier and Gaussian measurements, Comm. Pure Appl. Math., to appear.","DOI":"10.1002\/cpa.20227"},{"key":"9005_CR39","doi-asserted-by":"crossref","first-page":"625","DOI":"10.1080\/10556789908805766","volume":"11\u201312","author":"J. F. Sturm","year":"1999","unstructured":"J. F. Sturm, Using SeDuMi, a Matlab toolbox for optimization over symmetric cones, Optim. Methods Softw. 11\u201312 (1999), 625\u2013653, now at http:\/\/sedumi.mcmaster.ca\/ .","journal-title":"Optim. Methods Softw."},{"key":"9005_CR40","doi-asserted-by":"crossref","first-page":"2231","DOI":"10.1109\/TIT.2004.834793","volume":"50","author":"J. Tropp","year":"2004","unstructured":"J. Tropp, Greed is good: Algorithmic results for sparse approximation, IEEE Trans. Inform. Theory 50 (2004), 2231\u20132242.","journal-title":"IEEE Trans. Inform. Theory"},{"key":"9005_CR41","unstructured":"J. Tropp, Topics in Sparse Approximation, PhD Thesis, UT-Austin, 2004."},{"key":"9005_CR42","unstructured":"J. Tropp, Random subdictionaries of general dictionaries, Appl. Comput. Harmon. Anal., to appear."},{"key":"9005_CR43","doi-asserted-by":"crossref","DOI":"10.1007\/978-1-4757-2545-2","volume-title":"Weak Convergence and Empirical Processes","author":"A. der Vaart Van","year":"1996","unstructured":"A. Van der Vaart and J. Wellner, Weak Convergence and Empirical Processes, Springer, New York, 1996."},{"key":"9005_CR44","doi-asserted-by":"crossref","first-page":"167","DOI":"10.1016\/j.acha.2004.12.001","volume":"18","author":"R. Vershynin","year":"2005","unstructured":"R. Vershynin, Frame expansions with erasures: an approach through the noncommutative operator theory, Appl. Comput. Harmon. Anal. 18 (2005), 167\u2013176.","journal-title":"Appl. Comput. Harmon. Anal."},{"key":"9005_CR45","doi-asserted-by":"crossref","first-page":"61","DOI":"10.1016\/j.acha.2006.04.003","volume":"22","author":"J. Zou","year":"2007","unstructured":"J. Zou, A\u00a0sublinear algorithm for the recovery of signals with sparse Fourier transform when many samples are missing, Appl. Comput. Harmon. Anal.\u00a022 (2007), 61\u201377.","journal-title":"Appl. Comput. Harmon. Anal."},{"key":"9005_CR46","doi-asserted-by":"crossref","first-page":"572","DOI":"10.1016\/j.jcp.2005.06.005","volume":"211","author":"J. Zou","year":"2005","unstructured":"J. Zou, A. Gilbert, M. Strauss, and I. Daubechies, Theoretical and experimental analysis of a randomized algorithm for sparse Fourier transform analysis, J. Comput. Phys.\u00a0211 (2005), 572\u2013595.","journal-title":"J. Comput. Phys."}],"container-title":["Foundations of Computational Mathematics"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10208-007-9005-x.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s10208-007-9005-x\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10208-007-9005-x","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-007-9005-x"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2007,8,10]]},"references-count":46,"journal-issue":{"issue":"6","published-print":{"date-parts":[[2008,12]]}},"alternative-id":["9005"],"URL":"https:\/\/doi.org\/10.1007\/s10208-007-9005-x","relation":{},"ISSN":["1615-3375","1615-3383"],"issn-type":[{"value":"1615-3375","type":"print"},{"value":"1615-3383","type":"electronic"}],"subject":[],"published":{"date-parts":[[2007,8,10]]}}}