Liberating the dimension

Frances Y. Kuo, Ian H. Sloan, Grzegorz W. Wasilkowski, Henryk Woźniakowski

Research output: Contribution to journalArticlepeer-review

54 Scopus citations

Abstract

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.

Original languageEnglish
Pages (from-to)422-454
Number of pages33
JournalJournal of Complexity
Volume26
Issue number5
DOIs
StatePublished - Oct 2010

Bibliographical note

Funding 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.

Keywords

  • Infinite dimensional integration
  • Randomly shifted lattice rules
  • Tractability
  • Worst case error

ASJC Scopus subject areas

  • Algebra and Number Theory
  • Statistics and Probability
  • Numerical Analysis
  • General Mathematics
  • Control and Optimization
  • Applied Mathematics

Fingerprint

Dive into the research topics of 'Liberating the dimension'. Together they form a unique fingerprint.

Cite this