Multivariate integration for analytic functions with Gaussian kernels

Abstract:

We study multivariate integration of analytic functions defined on $\mathbb {R}^d$. These functions are assumed to belong to a reproducing kernel Hilbert space whose kernel is Gaussian, with nonincreasing shape parameters. We prove that a tensor product algorithm based on the univariate Gauss-Hermite quadrature rules enjoys exponential convergence and computes an $\varepsilon$-approximation for the $d$-variate integration using an order of $(\ln \varepsilon ^{-1})^d$ function values as $\varepsilon$ goes to zero. We prove that the exponent $d$ is sharp by proving a lower bound on the minimal (worst case) error of any algorithm based on finitely many function values. We also consider four notions of tractability describing how the minimal number $n(\varepsilon ,d)$ of function values needed to find an $\varepsilon$-approximation in the $d$-variate case behaves as a function of $d$ and $\ln \varepsilon ^{-1}$. One of these notions is new. In particular, we prove that for all positive shape parameters, the minimal number $n(\varepsilon ,d)$ is larger than any polynomial in $d$ and $\ln \varepsilon ^{-1}$ as $d$ and $\varepsilon ^{-1}$ go to infinity. However, it is not exponential in $d^{ t}$ and $\ln \varepsilon ^{-1}$ whenever $t>1$.