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

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=\mathcal{O}(N\log (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.

References in corpus (8)

• A non-adapted sparse approximation of PDEs with stochastic inputs
• Compressive Sampling of Polynomial Chaos Expansions: Convergence Analysis and Sampling Strategies
• Polynomial approximation via compressed sensing of high-dimensional functions on lower sets
• A Christoffel function weighted least squares algorithm for collocation approximations
• Stochastic collocation on unstructured multivariate meshes
• Frames and numerical approximation II: generalized sampling
• Estimates of the asymptotic Nikolskii constants for spherical polynomials
• Adaptive approximation by optimal weighted least squares methods