TY - JOUR

T1 - Multilevel weighted least squares polynomial approximation

AU - Haji-Ali, Abdul-Lateef

AU - Nobile, Fabio

AU - Tempone, Raul

AU - Wolfers, Sören

N1 - KAUST Repository Item: Exported on 2021-02-16
Acknowledged KAUST grant number(s): CRG3 Award Ref:2281, CRG4 Award Ref:2584
Acknowledgements: F. Nobile received support from the Center for ADvanced MOdeling Science (CADMOS). R. Tempone and S. Wolfers are members of the KAUST SRI Center for Uncertainty Quantification in Computational Science and Engineering. R. Tempone received support from the KAUST CRG3 Award Ref:2281, the KAUST CRG4 Award Ref:2584, and the Alexander von Humboldt foundation. We thank an anonymous referee for their help in improving
Proposition 3.3.

PY - 2020/3/3

Y1 - 2020/3/3

N2 - 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.

AB - 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.

UR - http://hdl.handle.net/10754/626523

UR - https://www.esaim-m2an.org/10.1051/m2an/2019045

U2 - 10.1051/m2an/2019045

DO - 10.1051/m2an/2019045

M3 - Article

VL - 54

SP - 649

EP - 677

JO - ESAIM: Mathematical Modelling and Numerical Analysis

JF - ESAIM: Mathematical Modelling and Numerical Analysis

SN - 0764-583X

IS - 2

ER -