Construction of Optimal Algorithms for Function Approximation in Gaussian Sobolev Spaces
This addresses approximation theory problems for researchers in numerical analysis, offering incremental improvements with optimal convergence rates.
The paper tackles function approximation in Gaussian Sobolev spaces by constructing two linear algorithms using n evaluations: one achieves near-optimal rate n^{-α} with a logarithmic factor and fast computation, while the other attains the optimal rate n^{-α}.
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^{-α}$.