Skip to main content

Raul Tempone: Multilevel weighted least squares polynomial approximation

Time: Mon 2018-08-06 14.15 - 15.00

Location: KTH Mathematics, Lindstedtsvägen 25, floor 4, room 3418

Participating: Raul Tempone, King Abdullah University (KAUST)

Export to calendar

Abstract:

We propose and analyze a multilevel weighted least squares polynomial approximation method. Weighted least squares polynomial approximation uses random samples to determine projections of functions onto spaces of polynomials. 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 reasonably small discretization error. As a solution to this problem, we propose a multilevel method that utilizes samples computed with different accuracies and can 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 illustrate the applicability of our method.

References:

 "Multilevel weighted least squares polynomial approximation", by A.-L. Haji-Ali, F. Nobile, R. Tempone and S. Wolfers. arXiv:1707.00026, June 2017.