On the power of standard information for tractability for $L_{\infty }$ approximation of periodic functions in the worst case setting

Abstract

We study multivariate approximation of periodic function in the worst case setting with the error measured in the $L_{\infty }$ norm. We consider algorithms that use standard information ${\Lambda }^{\mathrm{std}}$ consisting of function values or general linear information ${\Lambda }^{\mathrm{all}}$ consisting of arbitrary continuous linear functionals. We investigate the equivalences of various notions of algebraic and exponential tractability for ${\Lambda }^{\mathrm{std}}$ and ${\Lambda }^{\mathrm{all}}$ under the absolute or normalized error criterion, and show that the power of ${\Lambda }^{\mathrm{std}}$ is the same as the one of ${\Lambda }^{\mathrm{all}}$ for some notions of algebraic and exponential tractability. Our result can be applied to weighted Korobov spaces and Korobov spaces with exponential weight. This gives a special solution to Open problem 145 as posed by Novak and Woźniakowski (2012).

25 pages. arXiv admin note: text overlap with arXiv:2101.05200, arXiv:2101.03665