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