## Boosted optimal weighted least-squares

HTML articles powered by AMS MathViewer

- by
Cécile Haberstich, Anthony Nouy and Guillaume Perrin
**HTML**| PDF - Math. Comp.
**91**(2022), 1281-1315 Request permission

## Abstract:

This paper is concerned with the approximation of a function $u$ in a given subspace $V_m$ of dimension $m$ from evaluations of the function at $n$ suitably chosen points. The aim is to construct an approximation of $u$ in $V_m$ which yields an error close to the best approximation error in $V_m$ and using as few evaluations as possible. Classical least-squares regression, which defines a projection in $V_m$ from $n$ random points, usually requires a large $n$ to guarantee a stable approximation and an error close to the best approximation error. This is a major drawback for applications where $u$ is expensive to evaluate. One remedy is to use a weighted least-squares projection using $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=m$. It consists in sampling according to a measure associated with the optimization of a stability criterion over a collection of independent $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.## References

- Benjamin Arras, Markus Bachmayr, and Albert Cohen,
*Sequential sampling for optimal weighted least squares approximations in hierarchical spaces*, SIAM J. Math. Data Sci.**1**(2019), no. 1, 189–207. MR**3949706**, DOI 10.1137/18M1189749 - J. Baglama, D. Calvetti, and L. Reichel,
*Fast Leja points*, Electron. Trans. Numer. Anal.**7**(1998), 124–140. Large scale eigenvalue problems (Argonne, IL, 1997). MR**1667643** - Jacques Bénasséni,
*Lower bounds for the largest eigenvalue of a symmetric matrix under perturbations of rank one*, Linear Multilinear Algebra**59**(2011), no. 5, 565–569. MR**2801370**, DOI 10.1080/03081081003709827 - B. Bohn.
*Error analysis of regularized and unregularized least-squares regression on discretized function spaces*. PhD thesis, Universitäts-und Landesbibliothek Bonn, 2017. - L. Bos, S. De Marchi, A. Sommariva, and M. Vianello,
*Computing multivariate Fekete and Leja points by numerical linear algebra*, SIAM J. Numer. Anal.**48**(2010), no. 5, 1984–1999. MR**2745270**, DOI 10.1137/090779024 - 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–A2983. - James R. Bunch, Christopher P. Nielsen, and Danny C. Sorensen,
*Rank-one modification of the symmetric eigenproblem*, Numer. Math.**31**(1978/79), no. 1, 31–48. MR**508586**, DOI 10.1007/BF01396012 - Hans-Joachim Bungartz and Michael Griebel,
*Sparse grids*, Acta Numer.**13**(2004), 147–269. MR**2249147**, DOI 10.1017/S0962492904000182 - Albert Cohen, Mark A. Davenport, and Dany Leviatan,
*On the stability and accuracy of least squares approximations*, Found. Comput. Math.**13**(2013), no. 5, 819–834. MR**3105946**, DOI 10.1007/s10208-013-9142-3 - Albert Cohen, Mark A. Davenport, and Dany Leviatan,
*Correction to: On the stability and accuracy of least squares approximations [ MR3105946]*, Found. Comput. Math.**19**(2019), no. 1, 239. MR**3913878**, DOI 10.1007/s10208-018-9397-9 - A. Cohen and M. Dolbeault. Optimal pointwise sampling for $l^2$ approximation, 2021.
- Albert Cohen and Giovanni Migliorati,
*Optimal weighted least-squares methods*, SMAI J. Comput. Math.**3**(2017), 181–203. MR**3716755**, DOI 10.5802/smai-jcm.24 - Luc Devroye,
*Nonuniform random variate generation*, Springer-Verlag, New York, 1986. MR**836973**, DOI 10.1007/978-1-4613-8643-8 - Jerrad Hampton and Alireza Doostan,
*Coherence motivated sampling and convergence analysis of least squares polynomial Chaos regression*, Comput. Methods Appl. Mech. Engrg.**290**(2015), 73–97. MR**3340149**, DOI 10.1016/j.cma.2015.02.006 - Dinh Dũng, Vladimir Temlyakov, and Tino Ullrich,
*Hyperbolic cross approximation*, Advanced Courses in Mathematics. CRM Barcelona, Birkhäuser/Springer, Cham, 2018. Edited and with a foreword by Sergey Tikhonov. MR**3887571**, DOI 10.1007/978-3-319-92240-9 - Gene H. Golub,
*Some modified matrix eigenvalue problems*, SIAM Rev.**15**(1973), 318–334. MR**329227**, DOI 10.1137/1015032 - Ling Guo, Akil Narayan, Liang Yan, and Tao Zhou,
*Weighted approximate Fekete points: sampling for least-squares polynomial approximation*, SIAM J. Sci. Comput.**40**(2018), no. 1, A366–A387. MR**3763095**, DOI 10.1137/17M1140960 - I. C. F. Ipsen and B. Nadler,
*Refined perturbation bounds for eigenvalues of Hermitian and non-Hermitian matrices*, SIAM J. Matrix Anal. Appl.**31**(2009), no. 1, 40–53. MR**2487048**, DOI 10.1137/070682745 - I. Limonova and V. Temlyakov,
*On sampling discretization in $L_2$*, arXiv:math/2009.10789v1, 2021. - Yvon Maday, Ngoc Cuong Nguyen, Anthony T. Patera, and George S. H. Pau,
*A general multipurpose interpolation procedure: the magic points*, Commun. Pure Appl. Anal.**8**(2009), no. 1, 383–404. MR**2449115**, DOI 10.3934/cpaa.2009.8.383 - Adam W. Marcus, Daniel A. Spielman, and Nikhil Srivastava,
*Ramanujan graphs and the solution of the Kadison-Singer problem*, Proceedings of the International Congress of Mathematicians—Seoul 2014. Vol. III, Kyung Moon Sa, Seoul, 2014, pp. 363–386. MR**3729033** - Giovanni Migliorati, Fabio Nobile, and Raúl Tempone,
*Convergence estimates in probability and in expectation for discrete least squares with noisy evaluations at random points*, J. Multivariate Anal.**142**(2015), 167–182. MR**3412746**, DOI 10.1016/j.jmva.2015.08.009 - Giovanni Migliorati,
*Adaptive approximation by optimal weighted least-squares methods*, SIAM J. Numer. Anal.**57**(2019), no. 5, 2217–2245. MR**4002726**, DOI 10.1137/18M1198387 - N. Nagel, M. Schäfer, T. Ullrich. A New Upper Bound for Sampling Numbers.
*Foundations of Computational Mathematics*, 2021, https://doi.org/10.1007/s10208-021-09504-0 - Radford M. Neal,
*Slice sampling*, Ann. Statist.**31**(2003), no. 3, 705–767. With discussions and a rejoinder by the author. MR**1994729**, DOI 10.1214/aos/1056562461 - Akil Narayan, John D. Jakeman, and Tao Zhou,
*A Christoffel function weighted least squares algorithm for collocation approximations*, Math. Comp.**86**(2017), no. 306, 1913–1947. MR**3626543**, DOI 10.1090/mcom/3192 - Alvise Sommariva and Marco Vianello,
*Computing approximate Fekete points by QR factorizations of Vandermonde matrices*, Comput. Math. Appl.**57**(2009), no. 8, 1324–1336. MR**2512231**, DOI 10.1016/j.camwa.2008.11.011 - Joel A. Tropp,
*User-friendly tail bounds for sums of random matrices*, Found. Comput. Math.**12**(2012), no. 4, 389–434. MR**2946459**, DOI 10.1007/s10208-011-9099-z

## Additional Information

**Cécile Haberstich**- Affiliation: CEA, DAM, DIF, F-91297 Arpajon, France
- ORCID: 0000-0003-4088-3912
- Email: cecile.haberstich@cea.fr
**Anthony Nouy**- Affiliation: Centrale Nantes, LMJL UMR CNRS 6629, France
- MR Author ID: 702952
- Email: anthony.nouy@ec-nantes.fr
**Guillaume Perrin**- Affiliation: CEA, DAM, DIF, F-91297 Arpajon, France
- Address at time of publication: COSYS, Université Gustave Eiffel, 77420 Champs-sur-Marne, France
- MR Author ID: 1009710
- ORCID: 0000-0002-0592-6094
- Email: guillaume.perrin@univ-eiffel.fr
- Received by editor(s): July 4, 2020
- Received by editor(s) in revised form: June 28, 2021, and October 11, 2021
- Published electronically: January 5, 2022
- © Copyright 2022 American Mathematical Society
- Journal: Math. Comp.
**91**(2022), 1281-1315 - MSC (2020): Primary 41A10, 41A65, 93E24, 65D05, 65D15
- DOI: https://doi.org/10.1090/mcom/3710
- MathSciNet review: 4405496