Weighted least squares polynomial approximation uses random samples to determine projections of functions onto spaces of polynomials. It has been shown that, using an optimal distribution of sample locations, the number of samples required to achieve quasi-optimal approximation in a given polynomial subspace scales, up to a logarithmic factor, linearly in the dimension of this space. However, in many applications, the computation of samples includes a numerical discretization error. Thus, obtaining polynomial approximations with a single level method can become prohibitively expensive, as it requires a sufficiently large number of samples, each computed with a sufficiently small discretization error. As a solution to this problem, we propose a multilevel method that utilizes samples computed with different accuracies and is able to match the accuracy of single-level approximations with reduced computational cost. We derive complexity bounds under certain assumptions about polynomial approximability and sample work. Furthermore, we propose an adaptive algorithm for situations where such assumptions cannot be verified a priori. Finally, we provide an efficient algorithm for the sampling from optimal distributions and an analysis of computationally favorable alternative distributions. Numerical experiments underscore the practical applicability of our method.
Mots-clés : Multilevel methods, least squares approximation, multivariate approximation, polynomial approximation, convergence rates, error analysis
@article{M2AN_2020__54_2_649_0,
author = {Haji-Ali, Abdul-Lateef and Nobile, Fabio and Tempone, Ra\'ul and Wolfers, S\"oren},
title = {Multilevel weighted least squares polynomial approximation},
journal = {ESAIM: Mathematical Modelling and Numerical Analysis },
pages = {649--677},
publisher = {EDP-Sciences},
volume = {54},
number = {2},
year = {2020},
doi = {10.1051/m2an/2019045},
mrnumber = {4071315},
zbl = {1439.41011},
language = {en},
url = {http://www.numdam.org/articles/10.1051/m2an/2019045/}
}
TY - JOUR AU - Haji-Ali, Abdul-Lateef AU - Nobile, Fabio AU - Tempone, Raúl AU - Wolfers, Sören TI - Multilevel weighted least squares polynomial approximation JO - ESAIM: Mathematical Modelling and Numerical Analysis PY - 2020 SP - 649 EP - 677 VL - 54 IS - 2 PB - EDP-Sciences UR - http://www.numdam.org/articles/10.1051/m2an/2019045/ DO - 10.1051/m2an/2019045 LA - en ID - M2AN_2020__54_2_649_0 ER -
%0 Journal Article %A Haji-Ali, Abdul-Lateef %A Nobile, Fabio %A Tempone, Raúl %A Wolfers, Sören %T Multilevel weighted least squares polynomial approximation %J ESAIM: Mathematical Modelling and Numerical Analysis %D 2020 %P 649-677 %V 54 %N 2 %I EDP-Sciences %U http://www.numdam.org/articles/10.1051/m2an/2019045/ %R 10.1051/m2an/2019045 %G en %F M2AN_2020__54_2_649_0
Haji-Ali, Abdul-Lateef; Nobile, Fabio; Tempone, Raúl; Wolfers, Sören. Multilevel weighted least squares polynomial approximation. ESAIM: Mathematical Modelling and Numerical Analysis , Tome 54 (2020) no. 2, pp. 649-677. doi : 10.1051/m2an/2019045. http://www.numdam.org/articles/10.1051/m2an/2019045/
[1] , and , Sequential sampling for optimal weighted least squares approximations in hierarchical spaces. Preprint (2018). | arXiv | MR | Zbl
[2] , and , Galerkin finite element approximations of stochastic elliptic partial differential equations. SIAM J. Numer. Anal. 42 (2004) 800–825. | DOI | MR | Zbl
[3] , and , Multivariate simultaneous approximation. Constr. Approx. 18 (2002) 569. | DOI | MR | Zbl
[4] , , , and , Discrete least squares polynomial approximation with random evaluations – application to parametric and stochastic elliptic PDEs. ESAIM: M2AN 49 (2015) 815–837. | DOI | Numdam | MR | Zbl
[5] , and , Breaking the curse of dimensionality in sparse polynomial approximation of parametric PDEs. J. Math. Pures Appl. 103 (2015) 400–428. | DOI | MR | Zbl
[6] and , Optimal weighted least-squares methods. Preprint (2016). | arXiv | MR | Zbl
[7] , and , Analytic regularity and polynomial approximation of parametric and stochastic elliptic PDEs. Anal. App. 9 (2011) 11–47. | DOI | MR | Zbl
[8] , and , On the stability and accuracy of least squares approximations. Found. Comput. Math. 13 (2013) 819–834. | DOI | MR | Zbl
[9] , and , Solution of stochastic partial differential equations using Galerkin finite element techniques. Comput. Methods Appl. Mech. Eng. 190 (2001) 6359–6372. | DOI | MR | Zbl
[10] , Nonlinear approximation. Acta Numer. 7 (1998) 51–150. | DOI | MR | Zbl
[11] , and , Hyperbolic cross approximation. Preprint (2016). | arXiv | MR | Zbl
[12] , Random number generation and Monte Carlo methods, 2nd edition. In: Statistics and Computing. Springer, New York (2003). | MR | Zbl
[13] and , Dimension–adaptive tensor–product quadrature. Computing 71 (2003) 65–87. | DOI | MR | Zbl
[14] , Multilevel monte carlo path simulation. Oper. Res. 56 (2008) 607–617. | DOI | MR | Zbl
[15] and , Reproducing kernel Hilbert spaces for parametric partial differential equations. SIAM/ASA J. Uncertainty Quant. 5 (2017) 111–137. | DOI | MR | Zbl
[16] , , and , Multi-index stochastic collocation convergence rates for random PDEs with parametric regularity. Found. Comput. Math. 16 (2016) 1555–1605. | DOI | MR | Zbl
[17] , , and , Multi-index stochastic collocation for random PDEs. Comput. Methods Appl. Mech. Eng. 306 (2016) 95–122. | DOI | MR | Zbl
[18] and , Coherence motivated sampling and convergence analysis of least squares polynomial chaos regression. Comput. Methods Appl. Mech. Eng. 290 (2015) 73–97. | DOI | MR | Zbl
[19] , and , Multilevel accelerated quadrature for PDEs with log-normally distributed diffusion coefficient. SIAM/ASA J. Uncertainty Quant. 4 (2016) 520–551. | DOI | MR | Zbl
[20] , Adaptive sparse grids. ANZIAM J. 44 (2003) 335–353. | DOI | MR | Zbl
[21] , Multilevel Monte Carlo methods. In: International Conference on Large-Scale Scientific Computing. Springer (2001) 58–67. | DOI | Zbl
[22] , , , and , Multilevel quasi-Monte Carlo methods for lognormal diffusion problems. Math. Comput. 86 (2017) 2827–2860. | DOI | MR | Zbl
[23] and , Spectral Methods for Uncertainty Quantification. Springer (2010). | DOI | MR | Zbl
[24] and , Christoffel functions, orthogonal polynomials, and Nevai’s conjecture for Freud weights. Constr. Approx. 8 (1992) 463–535. | DOI | MR | Zbl
[25] , Metropolized independent sampling with comparisons to rejection sampling and importance sampling. Stat. Comput. 6 (1996) 113–119. | DOI
[26] , Monte Carlo Strategies in Scientific Computing. Springer Science & Business Media (2008). | MR | Zbl
[27] and , Weighted polynomial inequalities with doubling and weights. Constr. Approx. 16 (2000) 37–71. | DOI | MR | Zbl
[28] , and , Convergence estimates in probability and in expectation for discrete least squares with noisy evaluations at random points. J. Multivariate Anal. 142 (2015) 167–182. | DOI | MR | Zbl
[29] , and , A Christoffel function weighted least squares algorithm for collocation approximations. Math. Comput. 86 (2017) 1913–1947. | DOI | MR | Zbl
[30] , and , Generalized Jacobi weights, Christoffel functions, and Jacobi polynomials. SIAM J. Math. Anal. 25 (1994) 602–614. | DOI | MR | Zbl
[31] , and , Sparse approximation of multilinear problems with applications to kernel-based methods in UQ. Numer. Math. 139 (2018) 247–280. | DOI | MR | Zbl
[32] , Some results of Bernstein and Jackson type for polynomial approximation in -spaces. Jpn J. Appl. Math. 1 (1984) 173–181. | DOI | MR | Zbl
[33] , Orthogonal polynomials, 4th edition. In: Vol. XXIII of American Mathematical Society, Colloquium Publications. American Mathematical Society, Providence, RI (1975). | MR | Zbl
[34] , User-friendly tail bounds for sums of random matrices. Found. Comput. Math. 12 (2012) 389–434. | DOI | MR | Zbl
Cité par Sources :
