On Dimension-independent Rates of Convergence for Function Approximation with Gaussian Kernels

This article studies the problem of approximating functions belonging to a Hilbert space Hd with an isotropic or anisotropic translation invariant (or stationary) reproducing kernel with special attention given to the Gaussian kernel Kd(x,t) = exp(-∑₌₁ᵈγ_²(x₋t₎²) for all x,tᵈ. The isotropic (or radial) case corresponds to using the same shape parameters for all coordinates, i.e., γ₌γ>0 for all , whereas the anisotropic case corresponds to varying γ_. The approximation error of the optimal approximation algorithm, called a meshfree or kriging method, is known to decay faster than any polynomial in n⁻¹, for fixed d, where n is the number of data points. We are especially interested in moderate to large d, which in particular arise in the construction of surrogates for computer experiments. This article presents dimension-independent error bounds, i.e., the error is bounded by Cn⁻ᵖ, where C and p are independent of both d and n. This is equivalent to strong polynomial tractability. The pertinent error criterion is the worst case of such an algorithm over the unit ball in Hd, with the error for a single function given by the L₂ norm whose weight is also a Gaussian which is used to “localize” Rᵈ. We consider two classes of algorithms: (i) using data generated by finitely many arbitrary linear functionals, and (ii) using only finitely many function values. Provided that arbitrary linear functional data is available, we show $p=1/2$ is possible for any translation invariant positive definite kernel. We also consider the sequence of shape parameters γd decaying to zero like d-ω as d tends to ∞. Note that for large ω this means that the function to be approximated is “essentially low-dimensional.” Then the largest p is roughly max(1/2,ω). If only function values are available, dimension-independent convergence rates are somewhat worse. If the goal is to make the error smaller than Cn⁻ᵖ times the initial $(n=0)$ error, then the corresponding dimension-independent exponent p is roughly ω. In particular, for the isotropic case, when ω=0, the error does not even decay polynomially with n⁻¹. In summary, excellent dimension-independent error decay rates are possible only when the sequence of shape parameters decays rapidly.