Multivariate approximation for analytic functions with Gaussian kernels

We approximate d-variate analytic functions defined on Rd which belong to a tensor product reproducing kernel Hilbert space. The kernel of this space is Gaussian with non-increasing positive shape parameters γj2 for j=1,2,…,d. The error of approximation is defined in the L2 sense with the standard Gaussian weight. We study the worst case error of algorithms that use at most n arbitrary linear functionals on d-variate functions. We prove that for arbitrary shape parameters there are algorithms enjoying exponential convergence, but the exponent of exponential convergence depends on d and goes to zero as d approaches infinity. We study the absolute and normalized error criteria, in which the information complexity n(ε,d) is defined as the minimal number of linear functionals which are needed to find an algorithm whose worst case error is at most ε or at most ε times the norm of the approximation operator. We study different notions of tractability which describe how the information complexity behaves as a function of d and lnε−1. We find necessary and sufficient conditions on various notions of tractability in terms of shape parameters γj2. Surprisingly enough, these conditions are the same for the absolute and normalized error criteria although the norm of the approximation operator may be exponentially small in d making the normalized error much harder than the absolute one. In particular, for any positive t and κ we find conditions on γj2 for which limd+ε−1→∞lnn(ε,d)dt+[lnε−1]κ=0.This holds