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

DOI10.1137/19M1279459MaRDI QIDQ5037568zbMATH OpenOpenAlexFDO

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)

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

zbMATH Keywords

high-dimensional approximationirregular domainsoptimal samplingpolynomial approximation

Mathematics Subject Classification ID

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

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.

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

Cites work

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

Cited in

(20)

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

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)