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

We study multivariate approximation with the error measured in L-infinity and weighted L-2 norms. We 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. We analyze algorithms that use standard information consisting of n function values, and we are especially 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). We prove that b epsilon [2P(2)/(2p + 1), p] for weighted L-2 approximation and b epsilon [2p(p - 1/2)/(2p + 1), p - 1/2] for L-infinity 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 we have p > 1/2. It was shown in our previous paper that the optimal order for Loo approximation and linear information is p - 1/2. We do not know if our bounds are sharp for standard information. We also study tractability of multivariate approximation, i.e., we analyze when the worst case error bounds depend at most polynomially on d and n(-1). We present necessary and sufficient conditions on tractability and illustrate our 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. (C) 2008 Elsevier Inc. All rights reserved.