Remote Access Mathematics of Computation
Green Open Access

Mathematics of Computation

ISSN 1088-6842(online) ISSN 0025-5718(print)



Infinite-dimensional integration on weighted Hilbert spaces

Author: Michael Gnewuch
Journal: Math. Comp. 81 (2012), 2175-2205
MSC (2010): Primary 65C05, 65D30; Secondary 11K38
Published electronically: April 5, 2012
MathSciNet review: 2945151
Full-text PDF Free Access

Abstract | References | Similar Articles | Additional Information


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/\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.

References [Enhancements On Off] (What's this?)


Similar Articles

Retrieve articles in Mathematics of Computation with MSC (2010): 65C05, 65D30, 11K38

Retrieve articles in all journals with MSC (2010): 65C05, 65D30, 11K38

Additional Information

Michael Gnewuch
Affiliation: Department of Computer Science, Columbia University, 1214 Amsterdam Avenue, New York, New York 10027
MR Author ID: 728124

Received by editor(s): May 21, 2010
Received by editor(s) in revised form: May 31, 2011
Published electronically: April 5, 2012
Article copyright: © Copyright 2012 American Mathematical Society
The copyright for this article reverts to public domain 28 years after publication.