Multilevel weighted least squares polynomial approximation
From MaRDI portal
Abstract: 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.
Recommendations
- Weighted discrete least-squares polynomial approximation using randomized quadratures
- Weighted approximate Fekete points: sampling for least-squares polynomial approximation
- Optimal weighted least-squares methods
- Adaptive approximation by optimal weighted least-squares methods
- Discrete least squares polynomial approximation with random evaluations - application to parametric and stochastic elliptic PDEs
Cites work
- A Christoffel function weighted least squares algorithm for collocation approximations
- Analytic regularity and polynomial approximation of parametric and stochastic elliptic PDE's
- Breaking the curse of dimensionality in sparse polynomial approximation of parametric PDEs
- Christoffel functions, orthogonal polynomials, and Nevai's conjecture for Freud weights
- Coherence motivated sampling and convergence analysis of least squares polynomial chaos regression
- Convergence estimates in probability and in expectation for discrete least squares with noisy evaluations at random points
- Dimension-adaptive tensor-product quadrature
- Discrete least squares polynomial approximation with random evaluations - application to parametric and stochastic elliptic PDEs
- Galerkin Finite Element Approximations of Stochastic Elliptic Partial Differential Equations
- Generalized Jacobi Weights, Christoffel Functions, and Jacobi Polynomials
- scientific article; zbMATH DE number 3477793 (Why is no real title available?)
- scientific article; zbMATH DE number 1215245 (Why is no real title available?)
- scientific article; zbMATH DE number 1942835 (Why is no real title available?)
- scientific article; zbMATH DE number 2000348 (Why is no real title available?)
- scientific article; zbMATH DE number 2232688 (Why is no real title available?)
- Hyperbolic cross approximation. Lecture notes given at the courses on constructive approximation and harmonic analysis, Barcelona, Spain, May 30 -- June 3, 2016
- Monte Carlo strategies in scientific computing.
- Multi-index stochastic collocation convergence rates for random PDEs with parametric regularity
- Multi-index stochastic collocation for random PDEs
- Multilevel accelerated quadrature for PDEs with log-normally distributed diffusion coefficient
- Multilevel Monte Carlo Path Simulation
- Multilevel Quasi-Monte Carlo methods for lognormal diffusion problems
- Multivariate simultaneous approximation
- On the stability and accuracy of least squares approximations
- Optimal weighted least-squares methods
- Reproducing kernel Hilbert spaces for parametric partial differential equations
- Sequential sampling for optimal weighted least squares approximations in hierarchical spaces
- Solution of stochastic partial differential equations using Galerkin finite element techniques
- Some results of bernstein and jackson type for polynomial approximation inL p-spaces
- Sparse approximation of multilinear problems with applications to kernel-based methods in UQ
- Spectral Methods for Uncertainty Quantification
- User-friendly tail bounds for sums of random matrices
- Weighted polynomial inequalities with doubling and \(A_\infty\) weights
Cited in
(9)- Weighted approximate Fekete points: sampling for least-squares polynomial approximation
- Effectively subsampled quadratures for least squares polynomial approximations
- Sequential sampling for optimal weighted least squares approximations in hierarchical spaces
- Multivariate approximation of functions on irregular domains by weighted least-squares methods
- Adaptive approximation by optimal weighted least-squares methods
- Least squares approximation of polynomial chaos expansions with optimized grid points
- Reconciling alternate methods for the determination of charge distributions: a probabilistic approach to high-dimensional least-squares approximations
- Measure transport via polynomial density surrogates
- Noise-robust multi-fidelity surrogate modelling for parametric partial differential equations
This page was built for publication: Multilevel weighted least squares polynomial approximation
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5110276)
