On the power of standard information for multivariate approximation in the worst case setting (Q1019157)

The paper deals with the general problem of approximating a function \(f\) from a source space \(F\) by an algorithm \(A(f)\) with error measured in a target space \(G\). In other words, the algorithm \(A:F\rightarrow G\) is an approximation of the embedding operator from \(F\) to \(G\). The choice of the target space \(G\) determines the norm in which the error \(f-A(f)\) is measured. Properties of the source space \(F\), such as the smoothness of the functions, affect the error of \(A\). Specifically, the authors study multivariate approximation with the error measured in \(L_{\infty }\) and weighted \(L_2\) norms. They consider the worst case setting for a general reproducing kernel Hilbert space of functions of \(d\) variables with a bounded or integrable kernel. Here \(d\) can be arbitrarily large. They analyze algorithms that use standard information consisting of \(n\) function values, and they are specifically interested in the optimal order of convergence, i.e., in the maximal exponent \(b\) for which the worst case error of such an algorithm is of order \(n^{-b}\). They prove that \(b\in [2p^2/(2p+1),p]\) for weighted \(L_2\) approximation and \(b\in [2p(p-1/2)/(2p+1),p-1/2]\) for \(L_{\infty }\) approximation, where \(p\) is the optimal order of convergence for weighted \(L_2\) approximation among all algorithms that may use arbitrary linear functionals, as opposed to function values only. Under a mild assumption on the reproducing kernels one has \(p>1/2\). It was shown in a previous paper of the authors that the optimal order for \(L_{\infty }\) approximation and linear information is \(p-1/2\). They do not know if the bounds are sharp for standard information. They also study tractability of multivariate approximation, i.e., they analyze when the worst case error bounds depend at most polynomially on \(d\) and \(n^{-1}\). Necessary and sufficient conditions on tractability are presented and illustrate the results for the weighted Korobov spaces with arbitrary smoothness and for the weighted Sobolev spaces with the Wiener sheet kernel. Tractability conditions for these spaces are given in terms of the weights defining these spaces.