{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,3]],"date-time":"2026-06-03T09:23:43Z","timestamp":1780478623291,"version":"3.54.1"},"reference-count":28,"publisher":"American Mathematical Society (AMS)","issue":"335","license":[{"start":{"date-parts":[[2023,1,5]],"date-time":"2023-01-05T00:00:00Z","timestamp":1672876800000},"content-version":"am","delay-in-days":365,"URL":"https:\/\/www.ams.org\/publications\/copyright-and-permissions"}],"funder":[{"DOI":"10.13039\/501100006489","name":"Commissariat \u00e0 l'\u00c9nergie Atomique et aux \u00c9nergies Alternatives","doi-asserted-by":"publisher","id":[{"id":"10.13039\/501100006489","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Math. Comp."],"abstract":"

\n This paper is concerned with the approximation of a function\n \n \n \n u<\/mml:mi>\n u<\/mml:annotation>\n <\/mml:semantics>\n <\/mml:math>\n <\/inline-formula>\n in a given subspace\n \n \n \n \n V<\/mml:mi>\n m<\/mml:mi>\n <\/mml:msub>\n V_m<\/mml:annotation>\n <\/mml:semantics>\n <\/mml:math>\n <\/inline-formula>\n of dimension\n \n \n \n m<\/mml:mi>\n m<\/mml:annotation>\n <\/mml:semantics>\n <\/mml:math>\n <\/inline-formula>\n from evaluations of the function at\n \n \n \n n<\/mml:mi>\n n<\/mml:annotation>\n <\/mml:semantics>\n <\/mml:math>\n <\/inline-formula>\n suitably chosen points. The aim is to construct an approximation of\n \n \n \n u<\/mml:mi>\n u<\/mml:annotation>\n <\/mml:semantics>\n <\/mml:math>\n <\/inline-formula>\n in\n \n \n \n \n V<\/mml:mi>\n m<\/mml:mi>\n <\/mml:msub>\n V_m<\/mml:annotation>\n <\/mml:semantics>\n <\/mml:math>\n <\/inline-formula>\n which yields an error close to the best approximation error in\n \n \n \n \n V<\/mml:mi>\n m<\/mml:mi>\n <\/mml:msub>\n V_m<\/mml:annotation>\n <\/mml:semantics>\n <\/mml:math>\n <\/inline-formula>\n and using as few evaluations as possible. Classical least-squares regression, which defines a projection in\n \n \n \n \n V<\/mml:mi>\n m<\/mml:mi>\n <\/mml:msub>\n V_m<\/mml:annotation>\n <\/mml:semantics>\n <\/mml:math>\n <\/inline-formula>\n from\n \n \n \n n<\/mml:mi>\n n<\/mml:annotation>\n <\/mml:semantics>\n <\/mml:math>\n <\/inline-formula>\n random points, usually requires a large\n \n \n \n n<\/mml:mi>\n n<\/mml:annotation>\n <\/mml:semantics>\n <\/mml:math>\n <\/inline-formula>\n to guarantee a stable approximation and an error close to the best approximation error. This is a major drawback for applications where\n \n \n \n u<\/mml:mi>\n u<\/mml:annotation>\n <\/mml:semantics>\n <\/mml:math>\n <\/inline-formula>\n is expensive to evaluate. One remedy is to use a weighted least-squares projection using\n \n \n \n n<\/mml:mi>\n n<\/mml:annotation>\n <\/mml:semantics>\n <\/mml:math>\n <\/inline-formula>\n samples drawn from a properly selected distribution. In this paper, we introduce a boosted weighted least-squares method which allows to ensure almost surely the stability of the weighted least-squares projection with a sample size close to the interpolation regime\n \n \n \n \n n<\/mml:mi>\n =<\/mml:mo>\n m<\/mml:mi>\n <\/mml:mrow>\n n=m<\/mml:annotation>\n <\/mml:semantics>\n <\/mml:math>\n <\/inline-formula>\n . It consists in sampling according to a measure associated with the optimization of a stability criterion over a collection of independent\n \n \n \n n<\/mml:mi>\n n<\/mml:annotation>\n <\/mml:semantics>\n <\/mml:math>\n <\/inline-formula>\n -samples, and resampling according to this measure until a stability condition is satisfied. A greedy method is then proposed to remove points from the obtained sample. Quasi-optimality properties in expectation are obtained for the weighted least-squares projection, with or without the greedy procedure. The proposed method is validated on numerical examples and compared to state-of-the-art interpolation and weighted least-squares methods.\n <\/p>","DOI":"10.1090\/mcom\/3710","type":"journal-article","created":{"date-parts":[[2021,11,4]],"date-time":"2021-11-04T09:58:56Z","timestamp":1636019936000},"page":"1281-1315","source":"Crossref","is-referenced-by-count":5,"title":["Boosted optimal weighted least-squares"],"prefix":"10.1090","volume":"91","author":[{"given":"C\u00e9cile","family":"Haberstich","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Anthony","family":"Nouy","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Guillaume","family":"Perrin","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"14","published-online":{"date-parts":[[2022,1,5]]},"reference":[{"issue":"1","key":"1","doi-asserted-by":"publisher","first-page":"189","DOI":"10.1137\/18M1189749","article-title":"Sequential sampling for optimal weighted least squares approximations in hierarchical spaces","volume":"1","author":"Arras, Benjamin","year":"2019","journal-title":"SIAM J. Math. Data Sci."},{"key":"2","first-page":"124","article-title":"Fast Leja points","volume":"7","author":"Baglama, J.","year":"1998","journal-title":"Electron. Trans. Numer. Anal."},{"issue":"5","key":"3","doi-asserted-by":"publisher","first-page":"565","DOI":"10.1080\/03081081003709827","article-title":"Lower bounds for the largest eigenvalue of a symmetric matrix under perturbations of rank one","volume":"59","author":"B\u00e9nass\u00e9ni, Jacques","year":"2011","journal-title":"Linear Multilinear Algebra","ISSN":"https:\/\/id.crossref.org\/issn\/0308-1087","issn-type":"print"},{"key":"4","doi-asserted-by":"crossref","unstructured":"B. Bohn. Error analysis of regularized and unregularized least-squares regression on discretized function spaces. PhD thesis, Universit\u00e4ts-und Landesbibliothek Bonn, 2017.","DOI":"10.1137\/15M1013973"},{"issue":"5","key":"5","doi-asserted-by":"publisher","first-page":"1984","DOI":"10.1137\/090779024","article-title":"Computing multivariate Fekete and Leja points by numerical linear algebra","volume":"48","author":"Bos, L.","year":"2010","journal-title":"SIAM J. Numer. Anal.","ISSN":"https:\/\/id.crossref.org\/issn\/0036-1429","issn-type":"print"},{"key":"6","doi-asserted-by":"crossref","unstructured":"L. Bos, S. De Marchi, A. Sommariva, and M. Vianello. Adaptive Leja sparse grid constructions for stochastic collocation and high-dimensional approximation, SIAM J. Sci. Comput. 36 (2014), no. 6, A2952\u2013A2983.","DOI":"10.1137\/140966368"},{"issue":"1","key":"7","doi-asserted-by":"publisher","first-page":"31","DOI":"10.1007\/BF01396012","article-title":"Rank-one modification of the symmetric eigenproblem","volume":"31","author":"Bunch, James R.","year":"1978","journal-title":"Numer. Math.","ISSN":"https:\/\/id.crossref.org\/issn\/0029-599X","issn-type":"print"},{"key":"8","doi-asserted-by":"publisher","first-page":"147","DOI":"10.1017\/S0962492904000182","article-title":"Sparse grids","volume":"13","author":"Bungartz, Hans-Joachim","year":"2004","journal-title":"Acta Numer.","ISSN":"https:\/\/id.crossref.org\/issn\/0962-4929","issn-type":"print"},{"issue":"5","key":"9","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"},{"issue":"1","key":"10","doi-asserted-by":"publisher","first-page":"239","DOI":"10.1007\/s10208-018-9397-9","article-title":"Correction to: On the stability and accuracy of least squares approximations [ MR3105946]","volume":"19","author":"Cohen, Albert","year":"2019","journal-title":"Found. Comput. Math.","ISSN":"https:\/\/id.crossref.org\/issn\/1615-3375","issn-type":"print"},{"key":"11","doi-asserted-by":"crossref","unstructured":"A. Cohen and M. Dolbeault. Optimal pointwise sampling for \ud835\udc59\u00b2 approximation, 2021.","DOI":"10.1016\/j.jco.2021.101602"},{"key":"12","doi-asserted-by":"publisher","first-page":"181","DOI":"10.5802\/smai-jcm.24","article-title":"Optimal weighted least-squares methods","volume":"3","author":"Cohen, Albert","year":"2017","journal-title":"SMAI J. Comput. Math."},{"key":"13","isbn-type":"print","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4613-8643-8","volume-title":"Nonuniform random variate generation","author":"Devroye, Luc","year":"1986","ISBN":"https:\/\/id.crossref.org\/isbn\/0387963057"},{"key":"14","doi-asserted-by":"publisher","first-page":"73","DOI":"10.1016\/j.cma.2015.02.006","article-title":"Coherence motivated sampling and convergence analysis of least squares polynomial Chaos regression","volume":"290","author":"Hampton, Jerrad","year":"2015","journal-title":"Comput. Methods Appl. Mech. Engrg.","ISSN":"https:\/\/id.crossref.org\/issn\/0045-7825","issn-type":"print"},{"key":"15","series-title":"Advanced Courses in Mathematics. CRM Barcelona","isbn-type":"print","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-92240-9","volume-title":"Hyperbolic cross approximation","author":"D\u0169ng, Dinh","year":"2018","ISBN":"https:\/\/id.crossref.org\/isbn\/9783319922393"},{"key":"16","doi-asserted-by":"publisher","first-page":"318","DOI":"10.1137\/1015032","article-title":"Some modified matrix eigenvalue problems","volume":"15","author":"Golub, Gene H.","year":"1973","journal-title":"SIAM Rev.","ISSN":"https:\/\/id.crossref.org\/issn\/1095-7200","issn-type":"print"},{"issue":"1","key":"17","doi-asserted-by":"publisher","first-page":"A366--A387","DOI":"10.1137\/17M1140960","article-title":"Weighted approximate Fekete points: sampling for least-squares polynomial approximation","volume":"40","author":"Guo, Ling","year":"2018","journal-title":"SIAM J. Sci. Comput.","ISSN":"https:\/\/id.crossref.org\/issn\/1064-8275","issn-type":"print"},{"issue":"1","key":"18","doi-asserted-by":"publisher","first-page":"40","DOI":"10.1137\/070682745","article-title":"Refined perturbation bounds for eigenvalues of Hermitian and non-Hermitian matrices","volume":"31","author":"Ipsen, I. C. F.","year":"2009","journal-title":"SIAM J. Matrix Anal. Appl.","ISSN":"https:\/\/id.crossref.org\/issn\/0895-4798","issn-type":"print"},{"key":"19","unstructured":"I. Limonova and V. Temlyakov, On sampling discretization in \ud835\udc3f\u2082, arXiv:math\/2009.10789v1, 2021."},{"issue":"1","key":"20","doi-asserted-by":"publisher","first-page":"383","DOI":"10.3934\/cpaa.2009.8.383","article-title":"A general multipurpose interpolation procedure: the magic points","volume":"8","author":"Maday, Yvon","year":"2009","journal-title":"Commun. Pure Appl. Anal.","ISSN":"https:\/\/id.crossref.org\/issn\/1534-0392","issn-type":"print"},{"key":"21","isbn-type":"print","first-page":"363","article-title":"Ramanujan graphs and the solution of the Kadison-Singer problem","author":"Marcus, Adam W.","year":"2014","ISBN":"https:\/\/id.crossref.org\/isbn\/9788961058063"},{"key":"22","doi-asserted-by":"publisher","first-page":"167","DOI":"10.1016\/j.jmva.2015.08.009","article-title":"Convergence estimates in probability and in expectation for discrete least squares with noisy evaluations at random points","volume":"142","author":"Migliorati, Giovanni","year":"2015","journal-title":"J. Multivariate Anal.","ISSN":"https:\/\/id.crossref.org\/issn\/0047-259X","issn-type":"print"},{"issue":"5","key":"23","doi-asserted-by":"publisher","first-page":"2217","DOI":"10.1137\/18M1198387","article-title":"Adaptive approximation by optimal weighted least-squares methods","volume":"57","author":"Migliorati, Giovanni","year":"2019","journal-title":"SIAM J. Numer. Anal.","ISSN":"https:\/\/id.crossref.org\/issn\/0036-1429","issn-type":"print"},{"key":"24","doi-asserted-by":"crossref","unstructured":"N. Nagel, M. Sch\u00e4fer, T. Ullrich. A New Upper Bound for Sampling Numbers. Foundations of Computational Mathematics, 2021, https:\/\/doi.org\/10.1007\/s10208-021-09504-0","DOI":"10.1007\/s10208-021-09504-0"},{"issue":"3","key":"25","doi-asserted-by":"publisher","first-page":"705","DOI":"10.1214\/aos\/1056562461","article-title":"Slice sampling","volume":"31","author":"Neal, Radford M.","year":"2003","journal-title":"Ann. Statist.","ISSN":"https:\/\/id.crossref.org\/issn\/0090-5364","issn-type":"print"},{"issue":"306","key":"26","doi-asserted-by":"publisher","first-page":"1913","DOI":"10.1090\/mcom\/3192","article-title":"A Christoffel function weighted least squares algorithm for collocation approximations","volume":"86","author":"Narayan, Akil","year":"2017","journal-title":"Math. Comp.","ISSN":"https:\/\/id.crossref.org\/issn\/0025-5718","issn-type":"print"},{"issue":"8","key":"27","doi-asserted-by":"publisher","first-page":"1324","DOI":"10.1016\/j.camwa.2008.11.011","article-title":"Computing approximate Fekete points by QR factorizations of Vandermonde matrices","volume":"57","author":"Sommariva, Alvise","year":"2009","journal-title":"Comput. Math. Appl.","ISSN":"https:\/\/id.crossref.org\/issn\/0898-1221","issn-type":"print"},{"issue":"4","key":"28","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"}],"container-title":["Mathematics of Computation"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.ams.org\/mcom\/2022-91-335\/S0025-5718-2022-03710-8\/mcom3710_AM.pdf","content-type":"application\/pdf","content-version":"am","intended-application":"syndication"},{"URL":"https:\/\/www.ams.org\/mcom\/2022-91-335\/S0025-5718-2022-03710-8\/S0025-5718-2022-03710-8.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,4,22]],"date-time":"2026-04-22T04:29:11Z","timestamp":1776832151000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.ams.org\/mcom\/2022-91-335\/S0025-5718-2022-03710-8\/"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,1,5]]},"references-count":28,"journal-issue":{"issue":"335","published-print":{"date-parts":[[2022,5]]}},"alternative-id":["S0025-5718-2022-03710-8"],"URL":"https:\/\/doi.org\/10.1090\/mcom\/3710","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":[[2022,1,5]]}}}