{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,21]],"date-time":"2026-04-21T20:16:56Z","timestamp":1776802616582,"version":"3.51.2"},"reference-count":52,"publisher":"American Mathematical Society (AMS)","issue":"309","license":[{"start":{"date-parts":[[2018,5,11]],"date-time":"2018-05-11T00:00:00Z","timestamp":1525996800000},"content-version":"am","delay-in-days":365,"URL":"https:\/\/www.ams.org\/publications\/copyright-and-permissions"}],"funder":[{"DOI":"10.13039\/100009112","name":"Istituto Nazionale di Alta Matematica \"Francesco Severi\"","doi-asserted-by":"publisher","id":[{"id":"10.13039\/100009112","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100003407","name":"Ministero dell\u00e2\u0080\u0099Istruzione, dell\u00e2\u0080\u0099Universit\u00c3 e della Ricerca","doi-asserted-by":"publisher","id":[{"id":"10.13039\/501100003407","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100003407","name":"Ministero dell\u00e2\u0080\u0099Istruzione, dell\u00e2\u0080\u0099Universit\u00c3 e della Ricerca","doi-asserted-by":"publisher","id":[{"id":"10.13039\/501100003407","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Math. Comp."],"abstract":"

\n We present a theoretical analysis of the\n CORSING<\/sans-serif>\n (\n COmpRessed SolvING<\/sans-serif>\n ) method for the numerical approximation of partial differential equations based on compressed sensing. In particular, we show that the best\n \n \n \n s<\/mml:mi>\n s<\/mml:annotation>\n <\/mml:semantics>\n <\/mml:math>\n <\/inline-formula>\n -term approximation of the weak solution of a PDE with respect to a system of\n \n \n \n N<\/mml:mi>\n N<\/mml:annotation>\n <\/mml:semantics>\n <\/mml:math>\n <\/inline-formula>\n trial functions, can be recovered via a Petrov-Galerkin approach using\n \n \n \n \n m<\/mml:mi>\n \n \u226a\n \n <\/mml:mo>\n N<\/mml:mi>\n <\/mml:mrow>\n m \\ll N<\/mml:annotation>\n <\/mml:semantics>\n <\/mml:math>\n <\/inline-formula>\n test functions. This recovery is guaranteed if the local\n \n \n \n a<\/mml:mi>\n a<\/mml:annotation>\n <\/mml:semantics>\n <\/mml:math>\n <\/inline-formula>\n -coherence associated with the bilinear form and the selected trial and test bases fulfills suitable decay properties. The fundamental tool of this analysis is the restricted inf-sup property, i.e., a combination of the classical inf-sup condition and the well-known restricted isometry property of compressed sensing.\n <\/p>","DOI":"10.1090\/mcom\/3209","type":"journal-article","created":{"date-parts":[[2016,9,21]],"date-time":"2016-09-21T12:51:41Z","timestamp":1474462301000},"page":"1-38","source":"Crossref","is-referenced-by-count":13,"title":["A theoretical study of COmpRessed SolvING for advection-diffusion-reaction problems"],"prefix":"10.1090","volume":"87","author":[{"given":"Simone","family":"Brugiapaglia","sequence":"first","affiliation":[]},{"given":"Fabio","family":"Nobile","sequence":"additional","affiliation":[]},{"given":"Stefano","family":"Micheletti","sequence":"additional","affiliation":[]},{"given":"Simona","family":"Perotto","sequence":"additional","affiliation":[]}],"member":"14","published-online":{"date-parts":[[2017,5,11]]},"reference":[{"key":"1","unstructured":"B. Adcock, Infinite-dimensional compressed sensing and function interpolation, arXiv preprint arXiv:1509.06073 (2015)."},{"key":"2","unstructured":"B. Adcock, Infinite-dimensional \u2113\u00b9 minimization and function approximation from pointwise data, arXiv preprint arXiv:1503.02352 (2015)."},{"key":"3","doi-asserted-by":"crossref","unstructured":"B. Adcock and A.C. Hansen, Generalized Sampling and Infinite-Dimensional Compressed Sensing, Found. Comput. Math. (2015), 1\u201361 (English).","DOI":"10.1007\/s10208-015-9276-6"},{"key":"4","unstructured":"B. Adcock, A.C. Hansen, C. Poon, and B. Roman, Breaking the coherence barrier: A new theory for compressed sensing, arXiv preprint arXiv:1302.0561 (2013)."},{"issue":"3","key":"5","doi-asserted-by":"publisher","first-page":"569","DOI":"10.1109\/18.985947","article-title":"Strong converse for identification via quantum channels","volume":"48","author":"Ahlswede, Rudolf","year":"2002","journal-title":"IEEE Trans. Inform. Theory","ISSN":"https:\/\/id.crossref.org\/issn\/0018-9448","issn-type":"print"},{"key":"6","volume-title":"The mathematical foundations of the finite element method with applications to partial differential equations","year":"1972"},{"key":"7","doi-asserted-by":"crossref","unstructured":"J.-L. Bouchot, B. Bykowski, H. Rauhut, and C. Schwab, Compressed sensing Petrov-Galerkin approximations for parametric PDEs, Sampling Theory and Applications (SampTA), 2015 International Conference on, IEEE, 2015, pp. 528\u2013532.","DOI":"10.1109\/SAMPTA.2015.7148947"},{"issue":"2","key":"8","doi-asserted-by":"publisher","first-page":"412","DOI":"10.1016\/j.acha.2016.03.002","article-title":"Hard thresholding pursuit algorithms: number of iterations","volume":"41","author":"Bouchot, Jean-Luc","year":"2016","journal-title":"Appl. Comput. Harmon. Anal.","ISSN":"https:\/\/id.crossref.org\/issn\/1063-5203","issn-type":"print"},{"key":"9","series-title":"Springer Series in Computational Mathematics","isbn-type":"print","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4612-3172-1","volume-title":"Mixed and hybrid finite element methods","volume":"15","author":"Brezzi, Franco","year":"1991","ISBN":"https:\/\/id.crossref.org\/isbn\/0387975829"},{"key":"10","unstructured":"S. Brugiapaglia, COmpRessed SolvING: Sparse Approximation of PDEs Based on Compressed Sensing, Ph.D. thesis, MOX - Politecnico di Milano, 2016."},{"issue":"6","key":"11","doi-asserted-by":"publisher","first-page":"1306","DOI":"10.1016\/j.camwa.2015.07.015","article-title":"Compressed solving: a numerical approximation technique for elliptic PDEs based on compressed sensing","volume":"70","author":"Brugiapaglia, S.","year":"2015","journal-title":"Comput. Math. Appl.","ISSN":"https:\/\/id.crossref.org\/issn\/0898-1221","issn-type":"print"},{"issue":"2","key":"12","doi-asserted-by":"publisher","first-page":"489","DOI":"10.1109\/TIT.2005.862083","article-title":"Robust uncertainty principles: exact signal reconstruction from highly incomplete frequency information","volume":"52","author":"Cand\u00e8s, Emmanuel J.","year":"2006","journal-title":"IEEE Trans. Inform. Theory","ISSN":"https:\/\/id.crossref.org\/issn\/0018-9448","issn-type":"print"},{"issue":"1","key":"13","doi-asserted-by":"publisher","first-page":"33","DOI":"10.1137\/S1064827596304010","article-title":"Atomic decomposition by basis pursuit","volume":"20","author":"Chen, Scott Shaobing","year":"1998","journal-title":"SIAM J. Sci. Comput.","ISSN":"https:\/\/id.crossref.org\/issn\/1064-8275","issn-type":"print"},{"key":"14","doi-asserted-by":"publisher","first-page":"493","DOI":"10.1214\/aoms\/1177729330","article-title":"A measure of asymptotic efficiency for tests of a hypothesis based on the sum of observations","volume":"23","author":"Chernoff, Herman","year":"1952","journal-title":"Ann. Math. Statistics","ISSN":"https:\/\/id.crossref.org\/issn\/0003-4851","issn-type":"print"},{"issue":"3","key":"15","doi-asserted-by":"publisher","first-page":"815","DOI":"10.1051\/m2an\/2014050","article-title":"Discrete least squares polynomial approximation with random evaluations\u2014application to parametric and stochastic elliptic PDEs","volume":"49","author":"Chkifa, Abdellah","year":"2015","journal-title":"ESAIM Math. Model. Numer. Anal.","ISSN":"https:\/\/id.crossref.org\/issn\/2822-7840","issn-type":"print"},{"key":"16","series-title":"Applied and Numerical Harmonic Analysis","isbn-type":"print","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-25613-9","volume-title":"An introduction to frames and Riesz bases","author":"Christensen, Ole","year":"2016","ISBN":"https:\/\/id.crossref.org\/isbn\/9783319256115","edition":"2"},{"key":"17","doi-asserted-by":"crossref","unstructured":"A. Cohen, W. Dahmen, and R. DeVore, Orthogonal matching pursuit under the restricted isometry property, Constr. Approx. (2015), 1\u201315.","DOI":"10.1007\/s00365-016-9338-2"},{"issue":"5","key":"18","doi-asserted-by":"publisher","first-page":"819","DOI":"10.1007\/s10208-013-9142-3","article-title":"On the stability and accuracy of least squares approximations","volume":"13","author":"Cohen, Albert","year":"2013","journal-title":"Found. Comput. Math.","ISSN":"https:\/\/id.crossref.org\/issn\/1615-3375","issn-type":"print"},{"key":"19","isbn-type":"print","doi-asserted-by":"publisher","first-page":"55","DOI":"10.1017\/S0962492900002713","article-title":"Wavelet and multiscale methods for operator equations","author":"Dahmen, Wolfgang","year":"1997","ISBN":"https:\/\/id.crossref.org\/isbn\/0521591066"},{"issue":"5","key":"20","doi-asserted-by":"publisher","first-page":"2420","DOI":"10.1137\/110823158","article-title":"Adaptive Petrov-Galerkin methods for first order transport equations","volume":"50","author":"Dahmen, Wolfgang","year":"2012","journal-title":"SIAM J. Numer. Anal.","ISSN":"https:\/\/id.crossref.org\/issn\/0036-1429","issn-type":"print"},{"issue":"7","key":"21","doi-asserted-by":"publisher","first-page":"1245","DOI":"10.1016\/j.camwa.2013.07.022","article-title":"The fractional Laplacian operator on bounded domains as a special case of the nonlocal diffusion operator","volume":"66","author":"D\u2019Elia, Marta","year":"2013","journal-title":"Comput. Math. Appl.","ISSN":"https:\/\/id.crossref.org\/issn\/0898-1221","issn-type":"print"},{"key":"22","isbn-type":"print","doi-asserted-by":"publisher","first-page":"51","DOI":"10.1017\/S0962492900002816","article-title":"Nonlinear approximation","author":"DeVore, Ronald A.","year":"1998","ISBN":"https:\/\/id.crossref.org\/isbn\/0521643163"},{"issue":"4","key":"23","doi-asserted-by":"publisher","first-page":"1289","DOI":"10.1109\/TIT.2006.871582","article-title":"Compressed sensing","volume":"52","author":"Donoho, David L.","year":"2006","journal-title":"IEEE Trans. Inform. Theory","ISSN":"https:\/\/id.crossref.org\/issn\/0018-9448","issn-type":"print"},{"issue":"8","key":"24","doi-asserted-by":"publisher","first-page":"3015","DOI":"10.1016\/j.jcp.2011.01.002","article-title":"A non-adapted sparse approximation of PDEs with stochastic inputs","volume":"230","author":"Doostan, Alireza","year":"2011","journal-title":"J. Comput. Phys.","ISSN":"https:\/\/id.crossref.org\/issn\/0021-9991","issn-type":"print"},{"key":"25","series-title":"Applied Mathematical Sciences","isbn-type":"print","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4757-4355-5","volume-title":"Theory and practice of finite elements","volume":"159","author":"Ern, Alexandre","year":"2004","ISBN":"https:\/\/id.crossref.org\/isbn\/0387205748"},{"issue":"6","key":"26","doi-asserted-by":"publisher","first-page":"2543","DOI":"10.1137\/100806278","article-title":"Hard thresholding pursuit: an algorithm for compressive sensing","volume":"49","author":"Foucart, Simon","year":"2011","journal-title":"SIAM J. Numer. Anal.","ISSN":"https:\/\/id.crossref.org\/issn\/0036-1429","issn-type":"print"},{"key":"27","series-title":"Applied and Numerical Harmonic Analysis","isbn-type":"print","doi-asserted-by":"publisher","DOI":"10.1007\/978-0-8176-4948-7","volume-title":"A mathematical introduction to compressive sensing","author":"Foucart, Simon","year":"2013","ISBN":"https:\/\/id.crossref.org\/isbn\/9780817649470"},{"issue":"2","key":"28","doi-asserted-by":"publisher","first-page":"612","DOI":"10.1109\/TIP.2013.2288004","article-title":"Stable and robust sampling strategies for compressive imaging","volume":"23","author":"Krahmer, Felix","year":"2014","journal-title":"IEEE Trans. Image Process.","ISSN":"https:\/\/id.crossref.org\/issn\/1057-7149","issn-type":"print"},{"key":"29","doi-asserted-by":"crossref","unstructured":"S. Mallat and Z. Zhang, Matching pursuits with time-frequency dictionaries, IEEE Trans. Signal Process. 41 (1993), no. 12, 3397\u20133415.","DOI":"10.1109\/78.258082"},{"issue":"2","key":"30","doi-asserted-by":"publisher","first-page":"227","DOI":"10.1137\/S0097539792240406","article-title":"Sparse approximate solutions to linear systems","volume":"24","author":"Natarajan, B. K.","year":"1995","journal-title":"SIAM J. Comput.","ISSN":"https:\/\/id.crossref.org\/issn\/0097-5397","issn-type":"print"},{"issue":"3","key":"31","doi-asserted-by":"publisher","first-page":"301","DOI":"10.1016\/j.acha.2008.07.002","article-title":"CoSaMP: iterative signal recovery from incomplete and inaccurate samples","volume":"26","author":"Needell, D.","year":"2009","journal-title":"Appl. Comput. Harmon. Anal.","ISSN":"https:\/\/id.crossref.org\/issn\/1063-5203","issn-type":"print"},{"key":"32","first-page":"305","article-title":"Sur une m\u00e9thode pour r\u00e9soudre les \u00e9quations aux d\u00e9riv\u00e9es partielles du type elliptique, voisine de la variationnelle","volume":"16","author":"Ne\u010das, Jind\u0159ich","year":"1962","journal-title":"Ann. Scuola Norm. Sup. Pisa Cl. Sci. (3)","ISSN":"https:\/\/id.crossref.org\/issn\/0391-173X","issn-type":"print"},{"key":"33","isbn-type":"print","doi-asserted-by":"publisher","first-page":"409","DOI":"10.1007\/978-3-642-03413-8_12","article-title":"Theory of adaptive finite element methods: an introduction","author":"Nochetto, Ricardo H.","year":"2009","ISBN":"https:\/\/id.crossref.org\/isbn\/9783642034121"},{"key":"34","doi-asserted-by":"crossref","unstructured":"Y. C. Pati, R. Rezaiifar, and P. S. Krishnaprasad, Orthogonal matching pursuit: Recursive function approximation with applications to wavelet decomposition, Proceedings of the 27th Annual Asilomar Conference on Signals, Systems, and Computers, 1993, pp. 40\u201344.","DOI":"10.1109\/ACSSC.1993.342465"},{"key":"35","doi-asserted-by":"publisher","first-page":"92","DOI":"10.1016\/j.jcp.2014.02.024","article-title":"A weighted \u2113\u2081-minimization approach for sparse polynomial chaos expansions","volume":"267","author":"Peng, Ji","year":"2014","journal-title":"J. Comput. Phys.","ISSN":"https:\/\/id.crossref.org\/issn\/0021-9991","issn-type":"print"},{"issue":"8","key":"36","doi-asserted-by":"publisher","first-page":"3137","DOI":"10.1016\/j.jcp.2009.01.014","article-title":"Matrix approach to discrete fractional calculus. II. Partial fractional differential equations","volume":"228","author":"Podlubny, Igor","year":"2009","journal-title":"J. Comput. Phys.","ISSN":"https:\/\/id.crossref.org\/issn\/0021-9991","issn-type":"print"},{"key":"37","series-title":"Springer Series in Computational Mathematics","isbn-type":"print","doi-asserted-by":"crossref","DOI":"10.1007\/978-3-540-85268-1","volume-title":"Numerical approximation of partial differential equations","volume":"23","author":"Quarteroni, Alfio","year":"1994","ISBN":"https:\/\/id.crossref.org\/isbn\/3540571116"},{"key":"38","isbn-type":"print","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1515\/9783110226157.1","article-title":"Compressive sensing and structured random matrices","author":"Rauhut, Holger","year":"2010","ISBN":"https:\/\/id.crossref.org\/isbn\/9783110226140"},{"issue":"304","key":"39","doi-asserted-by":"publisher","first-page":"661","DOI":"10.1090\/mcom\/3113","article-title":"Compressive sensing Petrov-Galerkin approximation of high-dimensional parametric operator equations","volume":"86","author":"Rauhut, Holger","year":"2017","journal-title":"Math. Comp.","ISSN":"https:\/\/id.crossref.org\/issn\/0025-5718","issn-type":"print"},{"issue":"5","key":"40","doi-asserted-by":"publisher","first-page":"517","DOI":"10.1016\/j.jat.2012.01.008","article-title":"Sparse Legendre expansions via \u2113\u2081-minimization","volume":"164","author":"Rauhut, Holger","year":"2012","journal-title":"J. Approx. Theory","ISSN":"https:\/\/id.crossref.org\/issn\/0021-9045","issn-type":"print"},{"issue":"2","key":"41","doi-asserted-by":"publisher","first-page":"321","DOI":"10.1016\/j.acha.2015.02.003","article-title":"Interpolation via weighted \u2113\u2081 minimization","volume":"40","author":"Rauhut, Holger","year":"2016","journal-title":"Appl. Comput. Harmon. Anal.","ISSN":"https:\/\/id.crossref.org\/issn\/1063-5203","issn-type":"print"},{"key":"42","unstructured":"B. Roman, A. Bastounis, B. Adcock, and A.C. Hansen, On fundamentals of models and sampling in compressed sensing, Preprint (2015)."},{"key":"43","unstructured":"R. Rubinstein, Omp-Box v10, \\url{http:\/\/www.cs.technion.ac.il\/~ronrubin\/software.html}, 2009."},{"key":"44","unstructured":"R. Rubinstein, M. Zibulevsky, and M. Elad, Efficient implementation of the k-SVD algorithm using batch orthogonal matching pursuit, Tech. Report CS-2008-08, Technion, Computer Science Department, 2008."},{"issue":"1","key":"45","doi-asserted-by":"publisher","first-page":"63","DOI":"10.1615\/Int.J.UncertaintyQuantification.2013006821","article-title":"Dimensionality reduction for complex models via Bayesian compressive sensing","volume":"4","author":"Sargsyan, Khachik","year":"2014","journal-title":"Int. J. Uncertain. Quantif.","ISSN":"https:\/\/id.crossref.org\/issn\/2152-5080","issn-type":"print"},{"issue":"1","key":"46","doi-asserted-by":"publisher","first-page":"33","DOI":"10.1007\/s102080010029","article-title":"Nonlinear methods of approximation","volume":"3","author":"Temlyakov, V. N.","year":"2003","journal-title":"Found. Comput. Math.","ISSN":"https:\/\/id.crossref.org\/issn\/1615-3375","issn-type":"print"},{"issue":"10","key":"47","doi-asserted-by":"publisher","first-page":"2231","DOI":"10.1109\/TIT.2004.834793","article-title":"Greed is good: algorithmic results for sparse approximation","volume":"50","author":"Tropp, Joel A.","year":"2004","journal-title":"IEEE Trans. Inform. Theory","ISSN":"https:\/\/id.crossref.org\/issn\/0018-9448","issn-type":"print"},{"issue":"4","key":"48","doi-asserted-by":"publisher","first-page":"389","DOI":"10.1007\/s10208-011-9099-z","article-title":"User-friendly tail bounds for sums of random matrices","volume":"12","author":"Tropp, Joel A.","year":"2012","journal-title":"Found. Comput. Math.","ISSN":"https:\/\/id.crossref.org\/issn\/1615-3375","issn-type":"print"},{"key":"49","isbn-type":"print","volume-title":"Multigrid","author":"Trottenberg, U.","year":"2001","ISBN":"https:\/\/id.crossref.org\/isbn\/012701070X"},{"key":"50","doi-asserted-by":"crossref","unstructured":"X. Yang and G.E. Karniadakis, Reweighted \u2113\u2081-minimization method for stochastic elliptic differential equations, J. Comput. Phys. 248 (2013), 87\u2013108.","DOI":"10.1016\/j.jcp.2013.04.004"},{"issue":"4","key":"51","doi-asserted-by":"publisher","first-page":"379","DOI":"10.1007\/BF01389538","article-title":"On the multilevel splitting of finite element spaces","volume":"49","author":"Yserentant, Harry","year":"1986","journal-title":"Numer. Math.","ISSN":"https:\/\/id.crossref.org\/issn\/0029-599X","issn-type":"print"},{"issue":"9","key":"52","doi-asserted-by":"publisher","first-page":"6215","DOI":"10.1109\/TIT.2011.2162263","article-title":"Sparse recovery with orthogonal matching pursuit under RIP","volume":"57","author":"Zhang, Tong","year":"2011","journal-title":"IEEE Trans. Inform. Theory","ISSN":"https:\/\/id.crossref.org\/issn\/0018-9448","issn-type":"print"}],"container-title":["Mathematics of Computation"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.ams.org\/mcom\/2018-87-309\/S0025-5718-2017-03209-9\/mcom3209_AM.pdf","content-type":"application\/pdf","content-version":"am","intended-application":"syndication"},{"URL":"http:\/\/www.ams.org\/mcom\/2018-87-309\/S0025-5718-2017-03209-9\/S0025-5718-2017-03209-9.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"},{"URL":"https:\/\/www.ams.org\/mcom\/2018-87-309\/S0025-5718-2017-03209-9\/S0025-5718-2017-03209-9.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,4,21]],"date-time":"2026-04-21T19:27:25Z","timestamp":1776799645000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.ams.org\/mcom\/2018-87-309\/S0025-5718-2017-03209-9\/"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2017,5,11]]},"references-count":52,"journal-issue":{"issue":"309","published-print":{"date-parts":[[2018,1]]}},"alternative-id":["S0025-5718-2017-03209-9"],"URL":"https:\/\/doi.org\/10.1090\/mcom\/3209","archive":["CLOCKSS","Portico"],"relation":{},"ISSN":["1088-6842","0025-5718"],"issn-type":[{"value":"1088-6842","type":"electronic"},{"value":"0025-5718","type":"print"}],"subject":[],"published":{"date-parts":[[2017,5,11]]}}}