BIT Numerical Mathematics Applied Mathematics

Construction of optimal algorithms for function approximation in Gaussian Sobolev spaces

Yuya Suzuki, Toni Karvonen
Springer Nature · 2026-03-30 · DOI 10.1007/s10543-026-01122-y

Abstract

Abstract This paper studies function approximation in Gaussian Sobolev spaces over the real line and measures the error in a Gaussian-weighted $$L^p$$ 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 $$\alpha $$ α . The first algorithm is based on scaled trigonometric interpolation and achieves the optimal rate $$n^{-\alpha }$$ 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^{-\alpha }$$ n - α .

Read at publisher →