{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,18]],"date-time":"2026-08-18T15:48:37Z","timestamp":1787068117374,"version":"build-2736575974"},"reference-count":46,"publisher":"Springer Science and Business Media LLC","issue":"3","license":[{"start":{"date-parts":[[2017,4,19]],"date-time":"2017-04-19T00:00:00Z","timestamp":1492560000000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Found Comput Math"],"published-print":{"date-parts":[[2018,6]]},"DOI":"10.1007\/s10208-017-9350-3","type":"journal-article","created":{"date-parts":[[2017,4,19]],"date-time":"2017-04-19T16:58:13Z","timestamp":1492621093000},"page":"661-701","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":34,"title":["Infinite-Dimensional Compressed Sensing and Function Interpolation"],"prefix":"10.1007","volume":"18","author":[{"given":"Ben","family":"Adcock","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[2017,4,19]]},"reference":[{"key":"9350_CR1","doi-asserted-by":"crossref","unstructured":"B.\u00a0Adcock. Infinite-dimensional $$\\ell ^1$$ \u2113 1 minimization and function approximation from pointwise data. Constr. Approx. (to appear), 2016.","DOI":"10.1007\/s00365-017-9369-3"},{"issue":"5","key":"9350_CR2","doi-asserted-by":"crossref","first-page":"1263","DOI":"10.1007\/s10208-015-9276-6","volume":"16","author":"B Adcock","year":"2016","unstructured":"B.\u00a0Adcock and A.\u00a0C. Hansen. Generalized sampling and infinite-dimensional compressed sensing. Found. Comput. Math., 16(5):1263\u20131323, 2016.","journal-title":"Found. Comput. Math."},{"key":"9350_CR3","unstructured":"B.\u00a0Adcock, R.\u00a0Platte, and A.\u00a0Shadrin. Optimal sampling rates for approximating analytic functions from pointwise samples. arXiv:1610.04769, 2016."},{"key":"9350_CR4","first-page":"163","volume":"13","author":"VA Antonov","year":"1981","unstructured":"V.\u00a0A. Antonov and K.\u00a0V. Hol\u0161hevnikov. An estimate of the remainder in the expansion of the generating function for the Legendre polynomials (generalization and improvement of Bernstein\u2019s inequality). Vestnik Leningrad. Univ. Mat., 13:163\u2013166, 1981.","journal-title":"Vestnik Leningrad. Univ. Mat."},{"key":"9350_CR5","unstructured":"B.\u00a0Bah and R.\u00a0Ward. The sample complexity of weighted sparse approximation. arxiv:1507.0673, 2015."},{"key":"9350_CR6","doi-asserted-by":"crossref","unstructured":"J.\u00a0Bigot, C.\u00a0Boyer, and P.\u00a0Weiss. An analysis of block sampling strategies in compressed sensing. IEEE Trans. Inform. Theory (to appear), 2016.","DOI":"10.1109\/TIT.2016.2524628"},{"issue":"12","key":"9350_CR7","doi-asserted-by":"crossref","first-page":"7928","DOI":"10.1109\/TIT.2014.2364403","volume":"60","author":"A Bourrier","year":"2014","unstructured":"A.\u00a0Bourrier, M.\u00a0E. Davies, T.\u00a0Peleg, P.\u00a0P\u00e9rez, and R.\u00a0Gribonval. Fundamental performance limits for ideal decoders in high-dimensional linear inverse problems. IEEE Trans. Inform. Theory, 60(12):7928\u20137946, 2014.","journal-title":"IEEE Trans. Inform. Theory"},{"issue":"11","key":"9350_CR8","doi-asserted-by":"crossref","first-page":"7235","DOI":"10.1109\/TIT.2011.2161794","volume":"57","author":"EJ Cand\u00e8s","year":"2011","unstructured":"E.\u00a0J. Cand\u00e8s and Y.\u00a0Plan. A probabilistic and RIPless theory of compressed sensing. IEEE Trans. Inform. Theory, 57(11):7235\u20137254, 2011.","journal-title":"IEEE Trans. Inform. Theory"},{"issue":"2","key":"9350_CR9","doi-asserted-by":"crossref","first-page":"489","DOI":"10.1109\/TIT.2005.862083","volume":"52","author":"EJ Cand\u00e8s","year":"2006","unstructured":"E.\u00a0J. Cand\u00e8s, J.\u00a0Romberg, and T.\u00a0Tao. Robust uncertainty principles: exact signal reconstruction from highly incomplete frequency information. IEEE Trans. Inform. Theory, 52(2):489\u2013509, 2006.","journal-title":"IEEE Trans. Inform. Theory"},{"key":"9350_CR10","doi-asserted-by":"crossref","first-page":"92","DOI":"10.1016\/j.jco.2015.09.001","volume":"32","author":"A Chernov","year":"2016","unstructured":"A.\u00a0Chernov and D.\u00a0D\u0169ng. New explicit-in-dimension estimates for the cardinality of high-dimensional hyperbolic crosses and approximation of functions having mixed smoothness. J. Complexity, 32:92\u2013121, 2016.","journal-title":"J. Complexity"},{"issue":"3","key":"9350_CR11","doi-asserted-by":"crossref","first-page":"815","DOI":"10.1051\/m2an\/2014050","volume":"49","author":"A Chkifa","year":"2015","unstructured":"A.\u00a0Chkifa, A.\u00a0Cohen, G.\u00a0Migliorati, F.\u00a0Nobile, and R.\u00a0Tempone. Discrete least squares polynomial approximation with random evaluations-application to parametric and stochastic elliptic PDEs. ESAIM Math. Model. Numer. Anal., 49(3):815\u2013837, 2015.","journal-title":"ESAIM Math. Model. Numer. Anal."},{"key":"9350_CR12","unstructured":"A.\u00a0Chkifa, N.\u00a0Dexter, H.\u00a0Tran, and C.\u00a0Webster. Polynomial approximation via compressed sensing of high-dimensional functions on lower sets. Technical Report ORNL\/TM-2015\/497, Oak Ridge National Laboratory (also available as arXiv:1602.05823 ), 2015."},{"key":"9350_CR13","unstructured":"I.-Y. Chun and B.\u00a0Adcock. Compressed sensing and parallel acquisition. arXiv:1601.06214, 2016."},{"key":"9350_CR14","doi-asserted-by":"crossref","first-page":"615","DOI":"10.1007\/s10208-010-9072-2","volume":"10","author":"A Cohen","year":"2010","unstructured":"A.\u00a0Cohen, R.\u00a0A. DeVore, and C.\u00a0Schwab. Convergence rates of best $$N$$ N -term Galerkin approximations for a class of elliptic sPDEs. Found. Comput. Math., 10:615\u2013646, 2010.","journal-title":"Found. Comput. Math."},{"key":"9350_CR15","doi-asserted-by":"crossref","first-page":"11","DOI":"10.1142\/S0219530511001728","volume":"9","author":"A Cohen","year":"2011","unstructured":"A.\u00a0Cohen, R.\u00a0A. DeVore, and C.\u00a0Schwab. Analytic regularity and polynomial approximation of parametric and stochastic elliptic PDE\u2019s. Analysis and Applications, 9:11\u201347, 2011.","journal-title":"Analysis and Applications"},{"issue":"4","key":"9350_CR16","doi-asserted-by":"crossref","first-page":"1289","DOI":"10.1109\/TIT.2006.871582","volume":"52","author":"DL Donoho","year":"2006","unstructured":"D.\u00a0L. Donoho. Compressed sensing. IEEE Trans. Inform. Theory, 52(4):1289\u20131306, 2006.","journal-title":"IEEE Trans. Inform. Theory"},{"issue":"8","key":"9350_CR17","doi-asserted-by":"crossref","first-page":"3015","DOI":"10.1016\/j.jcp.2011.01.002","volume":"230","author":"A Doostan","year":"2011","unstructured":"A.\u00a0Doostan and H.\u00a0Owhadi. A non-adapted sparse approximation of PDEs with stochastic inputs. J. Comput. Phys., 230(8):3015\u20133034, 2011.","journal-title":"J. Comput. Phys."},{"key":"9350_CR18","doi-asserted-by":"crossref","DOI":"10.1007\/978-0-8176-4948-7","volume-title":"A Mathematical Introduction to Compressive Sensing","author":"S Foucart","year":"2013","unstructured":"S.\u00a0Foucart and H.\u00a0Rauhut. A Mathematical Introduction to Compressive Sensing. Birkhauser, 2013."},{"issue":"2","key":"9350_CR19","doi-asserted-by":"crossref","first-page":"1122","DOI":"10.1109\/TIT.2011.2167214","volume":"58","author":"M Friedlander","year":"2012","unstructured":"M.\u00a0Friedlander, H.\u00a0Mansour, R.\u00a0Saab, and I.\u00a0Yilmaz. Recovering compressively sampled signals using partial support information. IEEE Trans. Inform. Theory, 58(2):1122\u20131134, 2012.","journal-title":"IEEE Trans. Inform. Theory"},{"key":"9350_CR20","first-page":"1","volume":"36","author":"W Gautschi","year":"2009","unstructured":"W.\u00a0Gautschi. How sharp is Bernstein\u2019s inequality for Jacobi polynomials? Electron. Trans. Numer. Anal., 36:1\u20138, 2009.","journal-title":"Electron. Trans. Numer. Anal."},{"issue":"3","key":"9350_CR21","doi-asserted-by":"crossref","first-page":"1548","DOI":"10.1109\/TIT.2011.2104999","volume":"57","author":"D Gross","year":"2011","unstructured":"D.\u00a0Gross. Recovering low-rank matrices from few coefficients in any basis. IEEE Trans. Inform. Theory, 57(3):1548\u20131566, 2011.","journal-title":"IEEE Trans. Inform. Theory"},{"issue":"2","key":"9350_CR22","doi-asserted-by":"crossref","first-page":"229","DOI":"10.1007\/s00041-014-9361-2","volume":"21","author":"D Gross","year":"2015","unstructured":"D.\u00a0Gross, F.\u00a0Krahmer, and R.\u00a0Kueng. A partial derandomization of phaselift using spherical designs. J. Fourier Anal. Appl., 21(2):229\u2013266, 2015.","journal-title":"J. Fourier Anal. Appl."},{"key":"9350_CR23","doi-asserted-by":"crossref","first-page":"363","DOI":"10.1016\/j.jcp.2014.09.019","volume":"280","author":"J Hampton","year":"2015","unstructured":"J.\u00a0Hampton and A.\u00a0Doostan. Compressive sampling of polynomial chaos expansions: Convergence analysis and sampling strategies. J. Comput. Phys., 280:363\u2013386, 2015.","journal-title":"J. Comput. Phys."},{"key":"9350_CR24","unstructured":"J.\u00a0D. Jakeman, A.\u00a0Narayan, and T.\u00a0Zhou. A generalized sampling and preconditioning scheme for sparse approximation of polynomial chaos expansions. arXiv:1602.06879, 2016."},{"issue":"3","key":"9350_CR25","doi-asserted-by":"crossref","first-page":"353","DOI":"10.1007\/s00365-015-9299-x","volume":"42","author":"T K\u00fchn","year":"2015","unstructured":"T.\u00a0K\u00fchn, W.\u00a0Sickel, and T.\u00a0Ullrich. Approximation of mixed order Sobolev functions on the $$d$$ d -torus: Asymptotics, preasymptotics, and $$d$$ d -dependence. Constr. Approx., 42(3):353\u2013398, 2015.","journal-title":"Constr. Approx."},{"key":"9350_CR26","doi-asserted-by":"crossref","unstructured":"L.\u00a0Lorch. Alternative proof of a sharpened form of Bernstein\u2019s inequality for legendre polynomials. Appl. Anal., 14:237\u2013240, 1982\/3.","DOI":"10.1080\/00036818308839426"},{"issue":"4","key":"9350_CR27","doi-asserted-by":"crossref","first-page":"919","DOI":"10.4208\/cicp.151110.090911a","volume":"12","author":"L Mathelin","year":"2012","unstructured":"L.\u00a0Mathelin and K.\u00a0A. Gallivan. A compressed sensing approach for partial differential equations with random input data. Commun. Comput. Phys., 12(4):919\u2013954, 2012.","journal-title":"Commun. Comput. Phys."},{"key":"9350_CR28","unstructured":"G.\u00a0Migliorati. Polynomial approximation by means of the random discrete $$L^2$$ L 2 projection and application to inverse problems for PDEs with stochastic data. PhD thesis, Politecnico di Milano, 2013."},{"key":"9350_CR29","doi-asserted-by":"crossref","first-page":"137","DOI":"10.1016\/j.jat.2014.10.010","volume":"189","author":"G Migliorati","year":"2015","unstructured":"G.\u00a0Migliorati. Multivariate Markov-type and Nikolskii-type inequalities for polynomials associated with downward closed multi-index sets. J. Approx. Theory, 189:137\u2013159, 2015.","journal-title":"J. Approx. Theory"},{"key":"9350_CR30","first-page":"419","volume":"14","author":"G Migliorati","year":"2014","unstructured":"G.\u00a0Migliorati, F.\u00a0Nobile, E.\u00a0von Schwerin, and R.\u00a0Tempone. Analysis of the discrete $$L^2$$ L 2 projection on polynomial spaces with random evaluations. Found. Comput. Math., 14:419\u2013456, 2014.","journal-title":"Found. Comput. Math."},{"key":"9350_CR31","unstructured":"A.\u00a0Narayan, J.\u00a0D. Jakeman, and T.\u00a0Zhou. A Christoffel function weighted least squares algorithm for collocation approximations. arXiv:1412.4305, 2014."},{"issue":"1","key":"9350_CR32","doi-asserted-by":"crossref","first-page":"1","DOI":"10.4208\/cicp.020215.070515a","volume":"18","author":"A Narayan","year":"2015","unstructured":"A.\u00a0Narayan and T.\u00a0Zhou. Stochastic collocation on unstructured multivariate meshes. Commun. Comput. Phys., 18(1):1\u201336, 2015.","journal-title":"Commun. Comput. Phys."},{"key":"9350_CR33","doi-asserted-by":"crossref","first-page":"92","DOI":"10.1016\/j.jcp.2014.02.024","volume":"267","author":"J Peng","year":"2014","unstructured":"J.\u00a0Peng, J.\u00a0Hampton, and A.\u00a0Doostan. A weighted $$\\ell _1$$ \u2113 1 -minimization approach for sparse polynomial chaos expansions. J. Comput. Phys., 267:92\u2013111, 2014.","journal-title":"J. Comput. Phys."},{"issue":"2","key":"9350_CR34","doi-asserted-by":"crossref","first-page":"308","DOI":"10.1137\/090774707","volume":"53","author":"R Platte","year":"2011","unstructured":"R.\u00a0Platte, L.\u00a0N. Trefethen, and A.\u00a0Kuijlaars. Impossibility of fast stable approximation of analytic functions from equispaced samples. SIAM Rev., 53(2):308\u2013318, 2011.","journal-title":"SIAM Rev."},{"key":"9350_CR35","unstructured":"H.\u00a0Rauhut and R.\u00a0Ward. Sparse recovery for spherical harmonic expansions. In Proceedings of the 9th International Conference on Sampling Theory and Applications, 2011."},{"issue":"5","key":"9350_CR36","doi-asserted-by":"crossref","first-page":"517","DOI":"10.1016\/j.jat.2012.01.008","volume":"164","author":"H Rauhut","year":"2012","unstructured":"H.\u00a0Rauhut and R.\u00a0Ward. Sparse Legendre expansions via l1-minimization. J. Approx. Theory, 164(5):517\u2013533, 2012.","journal-title":"J. Approx. Theory"},{"issue":"2","key":"9350_CR37","doi-asserted-by":"crossref","first-page":"321","DOI":"10.1016\/j.acha.2015.02.003","volume":"40","author":"H Rauhut","year":"2016","unstructured":"H.\u00a0Rauhut and R.\u00a0Ward. Interpolation via weighted $$\\ell _1$$ \u2113 1 minimization. Appl. Comput. Harmon. Anal., 40(2):321\u2013351, 2016.","journal-title":"Appl. Comput. Harmon. Anal."},{"key":"9350_CR38","volume-title":"Orthogonal Polynomials","author":"G Szeg\u00f6","year":"1975","unstructured":"G.\u00a0Szeg\u00f6. Orthogonal Polynomials. American Mathematical Society, Providence, RI, 1975."},{"issue":"1","key":"9350_CR39","doi-asserted-by":"crossref","first-page":"423","DOI":"10.1137\/130913511","volume":"2","author":"G Tang","year":"2014","unstructured":"G.\u00a0Tang and G.\u00a0Iaccarino. Subsampled Gauss quadrature nodes for estimating polynomial chaos expansions. SIAM\/ASA J. Uncertain. Quantif., 2(1):423\u2013443, 2014.","journal-title":"SIAM\/ASA J. Uncertain. Quantif."},{"key":"9350_CR40","unstructured":"H.\u00a0Tran, C.\u00a0Webster, and G.\u00a0Zhang. Analysis of quasi-optimal polynomial approximations for parameterized PDEs with deterministic and stochastic coefficients. ORNL\/TM-2014\/468, Oak Ridge National Laboratory (also available as arXiv:1508.01821 ), 2015."},{"key":"9350_CR41","unstructured":"E.\u00a0van\u00a0den Berg and M.\u00a0P. Friedlander. SPGL1: A solver for large-scale sparse reconstruction. http:\/\/www.cs.ubc.ca\/labs\/scl\/spgl1 , June 2007."},{"key":"9350_CR42","doi-asserted-by":"crossref","unstructured":"E.\u00a0van\u00a0den Berg and M.\u00a0P. Friedlander. Probing the Pareto frontier for basis pursuit solutions. SIAM J. Sci. Comput., 2(890\u2013912), 31.","DOI":"10.1137\/080714488"},{"issue":"4","key":"9350_CR43","doi-asserted-by":"crossref","first-page":"1752","DOI":"10.1137\/13094596X","volume":"36","author":"Z Xu","year":"2014","unstructured":"Z.\u00a0Xu and T.\u00a0Zhou. On sparse interpolation and the design of deterministic interpolation points. SIAM J. Sci. Comput., 36(4):1752\u20131769, 2014.","journal-title":"SIAM J. Sci. Comput."},{"issue":"3","key":"9350_CR44","doi-asserted-by":"crossref","first-page":"279","DOI":"10.1615\/Int.J.UncertaintyQuantification.2012003925","volume":"2","author":"L Yan","year":"2012","unstructured":"L.\u00a0Yan, L.\u00a0Guo, and D.\u00a0Xiu. Stochastic collocation algorithms using $$\\ell _1$$ \u2113 1 -minimization. Int. J. Uncertain. Quantif., 2(3):279\u2013293, 2012.","journal-title":"Int. J. Uncertain. Quantif."},{"key":"9350_CR45","doi-asserted-by":"crossref","first-page":"87","DOI":"10.1016\/j.jcp.2013.04.004","volume":"248","author":"X Yang","year":"2013","unstructured":"X.\u00a0Yang and G.\u00a0E. Karniadakis. Reweighted $$\\ell _1$$ \u2113 1 minimization method for stochastic elliptic differential equations. J. Comput. Phys., 248:87\u2013108, 2013.","journal-title":"J. Comput. Phys."},{"key":"9350_CR46","doi-asserted-by":"crossref","unstructured":"X.\u00a0Yu and S.\u00a0Baek. Sufficient conditions on stable recovery of sparse signals with partial support information. IEEE Signal Process. Letters, 20(5), 2013.","DOI":"10.1109\/LSP.2013.2254712"}],"container-title":["Foundations of Computational Mathematics"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s10208-017-9350-3\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10208-017-9350-3.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10208-017-9350-3.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,9,21]],"date-time":"2019-09-21T09:10:06Z","timestamp":1569057006000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s10208-017-9350-3"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2017,4,19]]},"references-count":46,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2018,6]]}},"alternative-id":["9350"],"URL":"https:\/\/doi.org\/10.1007\/s10208-017-9350-3","relation":{},"ISSN":["1615-3375","1615-3383"],"issn-type":[{"value":"1615-3375","type":"print"},{"value":"1615-3383","type":"electronic"}],"subject":[],"published":{"date-parts":[[2017,4,19]]}}}