Infinite-dimensional integration on weighted Hilbert spaces
Michael Gnewuch
We study the numerical integration problem for functions with infinitely many variables which stem from a weighted reproducing kernel Hilbert space. We study the worst case ε \varepsilon -complexity which is defined as the minimal cost among all algorithms whose worst case error over the Hilbert space unit ball is at most ε \varepsilon . Here we assume that the cost of evaluating a function depends polynomially on the number of active variables. The infinite-dimensional integration problem is tractable if the ε \varepsilon -complexity is bounded by a constant times a power of 1 / ε 1/\varepsilon . The smallest such power is called the exponent of tractability. We provide improved lower bounds for the exponent of tractability for general finite-order weights and, with the help of multilevel algorithms, improved upper bounds for three newly defined classes of finite-order weights. The newly defined finite-intersection weights model the situation where each group of variables interacts with at most ρ \rho other groups of variables, ρ \rho some fixed number. For these weights we obtain sharp upper bounds for any decay of the weights and any polynomial degree of the cost function. For the other two classes of finite-order weights our upper bounds are sharp if, e.g., the decay of the weights is fast or slow enough. Furthermore, we deduce a lower bound for the exponent of tractability for arbitrary weights and a constructive upper bound for product weights.
Mathematics of Computation•Apr 5, 2012•38 citations