Many recent papers considered the problem of multivariate integration, and studied the tractability of the problem in the worst case setting as the dimensionality d increases. The typical question is: can we find an algorithm for which the error is bounded polynomially in d, or even independently of d? And the general answer is: yes, if we have a suitably weighted function space. Since there are important problems with infinitely many variables, here we take one step further: we consider the integration problem with infinitely many variablesthus liberating the dimensionand we seek algorithms with small error and minimal cost. In particular, we assume that the cost for evaluating a function depends on the number of active variables. The choice of the cost function plays a crucial role in the infinite dimensional setting. We present a number of lower and upper estimates of the minimal cost for product and finite-order weights. In some cases, the bounds are sharp.
|Number of pages||33|
|Journal||Journal of Complexity|
|State||Published - Oct 2010|
Bibliographical noteFunding Information:
The support of the Australian Research Council under its Centres of Excellence Program is gratefully acknowledged. The first author is supported by an Australian Research Council Queen Elizabeth II Research Fellowship. The last two authors were partially supported by the National Science Foundation under Grants DMS-0609703 and DMS-0608727, respectively, and the research on this paper was started when they visited the University of New South Wales in July/August of 2008. The authors thank Stefan Heinrich for the comments and suggestions.
- Infinite dimensional integration
- Randomly shifted lattice rules
- Worst case error
ASJC Scopus subject areas
- Algebra and Number Theory
- Statistics and Probability
- Numerical Analysis
- Mathematics (all)
- Control and Optimization
- Applied Mathematics