Construction of Optimal Algorithms for Function Approximation in Gaussian Sobolev Spaces
<|reference_start|>Construction of Optimal Algorithms for Function Approximation in Gaussian Sobolev Spaces: 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 $\alpha$. The first algorithm is based on scaled trigonometric interpolation and achieves the optimal rate $n^{-\alpha}$ 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}$.<|reference_end|>
@article{suzuki2024construction,
    title={Construction of Optimal Algorithms for Function Approximation in
  Gaussian Sobolev Spaces},
    author={Yuya Suzuki and Toni Karvonen},
    journal={arXiv preprint arXiv:2402.02917},
    year={2024},
    archivePrefix={arXiv},
    eprint={2402.02917},
    primaryClass={math.NA cs.NA}
}