Optimal sampling rates for approximating analytic functions from pointwise samples

DOI10.1093/IMANUM/DRY024MaRDI QIDQ5854358zbMATH OpenOpenAlexFDO

Authors Ben Adcock, Rodrigo B. Platte, A. Shadrin

Publication date 16 March 2021

Published in IMA Journal of Numerical Analysis (Search for Journal in Brave)

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

zbMATH Keywords

discrete approximationexponential convergenceleast-squarespolynomial approximation

Mathematics Subject Classification ID

Approximation by polynomials (41A10) Algorithms for approximation of functions (65D15)

Abstract: We consider the problem of approximating an analytic function on a compact interval from its values at $M+1$ distinct points. When the points are equispaced, a recent result (the so-called impossibility theorem) has shown that the best possible convergence rate of a stable method is root-exponential in $M$, and that any method with faster exponential convergence must also be exponentially ill-conditioned at a certain rate. This result hinges on a classical theorem of Coppersmith & Rivlin concerning the maximal behaviour of polynomials bounded on an equispaced grid. In this paper, we first generalize this theorem to arbitrary point distributions. We then present an extension of the impossibility theorem valid for general nonequispaced points, and apply it to the case of points that are equidistributed with respect to (modified) Jacobi weight functions. This leads to a necessary sampling rate for stable approximation from such points. We prove that this rate is also sufficient, and therefore exactly quantify (up to constants) the precise sampling rate for approximating analytic functions from such node distributions with stable methods. Numerical results -- based on computing the maximal polynomial via a variant of the classical Remez algorithm -- confirm our main theorems. Finally, we discuss the implications of our results for polynomial least-squares approximations. In particular, we theoretically confirm the well-known heuristic that stable least-squares approximation using polynomials of degree $N<M$ is possible only once $M$ is sufficiently large for there to be a subset of $N$ of the nodes that mimic the behaviour of the $N$th set of Chebyshev nodes.

Recommendations

• Impossibility of fast stable approximation of analytic functions from equispaced samples
• Constructing least-squares polynomial approximations
• On the stability and accuracy of least squares approximations
• Stable extrapolation of analytic functions
• Uniform approximation by discrete least squares polynomials

Cited in

(20)

• CAS4DL: Christoffel adaptive sampling for function approximation via deep learning
• Optimal convergence rates of high order Parzen windows with unbounded sampling
• Optimal sampling of holomorphic functions. II
• The Fourier extension method and discrete orthogonal polynomials on an arc of the circle
• Infinite-dimensional \(\ell ^1\) minimization and function approximation from pointwise data
• Computing a quantity of interest from observational data
• Exponential tractability of \(L_2\)-approximation with function values
• Fast and stable approximation of analytic functions from equispaced samples via polynomial frames
• Impossibility of fast stable approximation of analytic functions from equispaced samples
• Optimal Sampling of Holomorphic Functions
• Sampling for approximating R-limited functions
• scientific article; zbMATH DE number 5564091 (Why is no real title available?)
• A fast algorithm for the convolution of functions with compact support using Fourier extensions
• Near-optimal sampling strategies for multivariate function approximation on general domains
• APPROXIMATING SMOOTH, MULTIVARIATE FUNCTIONS ON IRREGULAR DOMAINS
• Full recovery from point values: an optimal algorithm for Chebyshev approximability prior
• Oversampled collocation approximation method of functions via Jacobi frames
• Randomized least-squares with minimal oversampling and interpolation in general spaces
• Optimal sampling for least-squares approximation
• Stability of least squares approximation under random sampling

This page was built for publication: Optimal sampling rates for approximating analytic functions from pointwise samples

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