Construction of Optimal Algorithms for Function Approximation in Gaussian Sobolev Spaces

2024/02/05 by Suzuki, Yuya, Karvonen, Toni
#41A15 #41A25 #42A15 #65D15 #FOS: Mathematics #Numerical Analysis (math.NA)

paper · doi:10.48550/arxiv.2402.02917

Abstract

This paper studies function approximation in Gaussian Sobolev spaces over the real line and measures the error in a Gaussian-weighted L^p-norm. We construct two linear approximation algorithms using n function evaluations that achieve the optimal or almost optimal rate of worst-case convergence in a Gaussian Sobolev space of order α. The first algorithm is based on scaled trigonometric interpolation and achieves the optimal rate n^-α up to a logarithmic factor. This algorithm can be constructed in almost-linear time with the fast Fourier transform. The second algorithm is more complicated, being based on spline smoothing, but attains the optimal rate n^-α.

Related

• Optimal numerical integration and approximation of functions on ℝ^d equipped with Gaussian measure
• A note on Lusin-type approximation of Sobolev functions on Gaussian\n spaces
• Pseudo s-Numbers of Embeddings of Gaussian Weighted Sobolev Spaces
• Worst-case optimal approximation with increasingly flat Gaussian kernels
• Recovery of Sobolev functions restricted to iid sampling