Adaptive approximation by optimal weighted least-squares methods

DOI10.1137/18M1198387MaRDI QIDQ5233118zbMATH OpenOpenAlexWikidataFDO

Authors Giovanni Migliorati

Publication date 16 September 2019

Published in SIAM Journal on Numerical Analysis (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1807.00402

zbMATH Keywords

adaptive approximationapproximation theoryconvergence rateshigh dimensional approximationmultivariate polynomialswaveletsweighted least squares

Mathematics Subject Classification ID

Approximation by polynomials (41A10) Rate of convergence, degree of approximation (41A25) Abstract approximation theory (approximation in normed linear spaces and other abstract spaces) (41A65) Numerical methods for wavelets (65T60)

Abstract: Given any domain $Xsubseteqmathbb{R}^d$ and a probability measure $ho$ on $X$, we study the problem of approximating in $L^2(X,ho)$ a given function $u:XomathbbR$, using its noiseless pointwise evaluations at random samples. For any given linear space $Vsubset{L}^2(X,ho)$ with dimension $n$, previous works have shown that stable and optimally converging Weighted Least-Squares (WLS) estimators can be constructed using $m$ random samples distributed according to an auxiliary probability measure $mu$ that depends on $V$, with $m$ being linearly proportional to $n$ up to a logarithmic term. As a first contribution, we present novel results on the stability and accuracy of WLS estimators with a given approximation space, using random samples that are more structured than those used in the previous analysis. As a second contribution, we study approximation by WLS estimators in the adaptive setting. For any sequence of nested spaces $(V_k{)}_{k}subset{L}^2(X,ho)$, we show that a sequence of WLS estimators of $u$, one for each space $V_k$, can be sequentially constructed such that: i) the estimators remain provably stable with high probability and optimally converging in expectation, simultaneously for all iterations from one to $k$, and ii) the overall number of samples necessary to construct all the first $k$ estimators remains linearly proportional to the dimension of $V_k$. We propose two sampling algorithms that achieve this goal. The first one is a purely random algorithm that recycles most of the samples from the previous iterations. The second algorithm recycles all the samples from all the previous iterations. Such an achievement is made possible by crucially exploiting the structure of the random samples. Finally we develop numerical methods for the adaptive approximation of functions in high dimension.

Recommendations

• Sequential sampling for optimal weighted least squares approximations in hierarchical spaces
• Optimal weighted least-squares methods
• Multivariate approximation of functions on irregular domains by weighted least-squares methods
• Adaptive polynomial approximation by means of random discrete least squares
• Multilevel weighted least squares polynomial approximation

Cites work

• A Christoffel function weighted least squares algorithm for collocation approximations
• A distribution-free theory of nonparametric regression
• A mathematical introduction to compressive sensing
• Adaptive polynomial approximation by means of random discrete least squares
• Analysis of discrete L^2 projection on polynomial spaces with random evaluations
• Approximation by superpositions of a sigmoidal function
• Approximation of high-dimensional parametric PDEs
• 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
• scientific article; zbMATH DE number 3516003 (Why is no real title available?)
• Multivariate approximation in downward closed polynomial spaces
• On the stability and accuracy of least squares approximations
• Optimal weighted least-squares methods
• Sequential sampling for optimal weighted least squares approximations in hierarchical spaces
• Some remarks on greedy algorithms
• Sparse grids
• Strong converse for identification via quantum channels
• User-friendly tail bounds for sums of random matrices

Cited in

(24)

• Adaptive Lanczos methods for recursive condition estimation
• Adaptive algorithm for constrained least-squares problems
• Optimal pointwise sampling for \(L^2\) approximation
• Stable high-order randomized cubature formulae in arbitrary dimension
• CAS4DL: Christoffel adaptive sampling for function approximation via deep learning
• Optimal sampling and Christoffel functions on general domains
• Adaptive weighted least-squares polynomial chaos expansion with basis adaptivity and sequential adaptive sampling
• Variance-based adaptive sequential sampling for polynomial chaos expansion
• scientific article; zbMATH DE number 19013 (Why is no real title available?)
• An Adaptive Weighted Bisection Method For Finding Roots Of Non-Linear Equations
• Optimal weighted least-squares methods
• Feedback and Weighting Mechanisms for Improving Jacobian Estimates in the Adaptive Simultaneous Perturbation Algorithm
• Sequential sampling for optimal weighted least squares approximations in hierarchical spaces
• Boosted optimal weighted least-squares
• Multilevel weighted least squares polynomial approximation
• APPROXIMATING SMOOTH, MULTIVARIATE FUNCTIONS ON IRREGULAR DOMAINS
• An Adaptive Sampling and Domain Learning Strategy for Multivariate Function Approximation on Unknown Domains
• Error guarantees for least squares approximation with noisy samples in domain adaptation
• Towards optimal sampling for learning sparse approximation in high dimensions
• Randomized least-squares with minimal oversampling and interpolation in general spaces
• On the representation and learning of monotone triangular transport maps
• Optimal sampling for least-squares approximation
• Stability of least squares approximation under random sampling
• Physics-informed deep learning and compressive collocation for high-dimensional diffusion-reaction equations: practical existence theory and numerics

This page was built for publication: Adaptive approximation by optimal weighted least-squares methods

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5233118)