Near-optimal sampling strategies for multivariate function approximation on general domains

DOI10.1137/19M1279459zbMATH Open1484.41015arXiv1908.01249OpenAlexW3043414797MaRDI QIDQ5037568FDOQ5037568

Authors: Ben Adcock, Juan M. Cardenas 

Publication date: 1 March 2022

Published in: SIAM Journal on Mathematics of Data Science (Search for Journal in Brave)

Abstract: In this paper, we address the problem of approximating a multivariate function defined on a general domain in $d$ dimensions from sample points. We consider weighted least-squares approximation in an arbitrary finite-dimensional space $P$ from independent random samples taken according to a suitable measure. In general, least-squares approximations can be inaccurate and ill-conditioned when the number of sample points $M$ is close to $N=dim(P)$. To counteract this, we introduce a novel method for sampling in general domains which leads to provably accurate and well-conditioned approximations. The resulting sampling measure is discrete, and therefore straightforward to sample from. Our main result shows near-optimal sample complexity for this procedure; specifically, $M=mathcalO(Nlog(N))$ samples suffice for a well-conditioned and accurate approximation. Numerical experiments on polynomial approximation in general domains confirm the benefits of this method over standard sampling.

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

Recommendations

• APPROXIMATING SMOOTH, MULTIVARIATE FUNCTIONS ON IRREGULAR DOMAINS
• Optimal sampling and Christoffel functions on general domains
• An Adaptive Sampling and Domain Learning Strategy for Multivariate Function Approximation on Unknown Domains
• Multivariate approximation of functions on irregular domains by weighted least-squares methods
• Weighted approximate Fekete points: sampling for least-squares polynomial approximation

zbMATH Keywords

polynomial approximationoptimal samplingirregular domainshigh-dimensional approximation

Mathematics Subject Classification ID

Monte Carlo methods (65C05) Multidimensional problems (41A63) Approximation by polynomials (41A10) Inequalities in approximation (Bernstein, Jackson, Nikol'ski?-type inequalities) (41A17)

Cites Work

• Title not available (Why is that?)
• User-friendly tail bounds for sums of random matrices
• On the stability and accuracy of least squares approximations
• Analysis of discrete \(L^2\) projection on polynomial spaces with random evaluations
• A non-adapted sparse approximation of PDEs with stochastic inputs
• Géza Freud, orthogonal polynomials and Christoffel functions. A case study
• Stochastic collocation on unstructured multivariate meshes
• Compressive sampling of polynomial chaos expansions: convergence analysis and sampling strategies
• Sequential sampling for optimal weighted least squares approximations in hierarchical spaces
• Christoffel functions on convex and starlike domains in \(\mathbb R^d\)
• Orthogonal Polynomials and Cubature Formulae on Spheres and on Balls
• Multivariate Markov-type and Nikolskii-type inequalities for polynomials associated with downward closed multi-index sets
• Infinite-dimensional compressed sensing and function interpolation
• Optimal weighted least-squares methods
• Frames and numerical approximation
• Estimates of the asymptotic Nikolskii constants for spherical polynomials
• A Christoffel function weighted least squares algorithm for collocation approximations
• Polynomial approximation via compressed sensing of high-dimensional functions on lower sets
• APPROXIMATING SMOOTH, MULTIVARIATE FUNCTIONS ON IRREGULAR DOMAINS
• Christoffel functions on planar domains with piecewise smooth boundary
• Correcting for unknown errors in sparse high-dimensional function approximation
• Frames and numerical approximation. II: Generalized sampling
• Optimal sampling rates for approximating analytic functions from pointwise samples

Cited In (15)

• CAS4DL: Christoffel adaptive sampling for function approximation via deep learning
• Polynomial approximation via compressed sensing of high-dimensional functions on lower sets
• Optimal sampling and Christoffel functions on general domains
• Randomized least-squares with minimal oversampling and interpolation in general spaces
• Efficient Multidimensional Diracs Estimation With Linear Sample Complexity
• Towards optimal sampling for learning sparse approximation in high dimensions
• Random sampling and unisolvent interpolation by almost everywhere analytic functions
• Sampling for approximating $R$-limited functions
• An Adaptive Sampling and Domain Learning Strategy for Multivariate Function Approximation on Unknown Domains
• A randomized tensor quadrature method for high dimensional polynomial approximation
• On the fractional calculus of multivariate Mittag-Leffler functions
• Optimal pointwise sampling for \(L^2\) approximation
• A Stieltjes Algorithm for Generating Multivariate Orthogonal Polynomials
• Efficient function approximation on general bounded domains using splines on a Cartesian grid
• APPROXIMATING SMOOTH, MULTIVARIATE FUNCTIONS ON IRREGULAR DOMAINS

This page was built for publication: Near-optimal sampling strategies for multivariate function approximation on general domains

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