Liberating the dimension

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

doi:10.1016/j.jco.2009.12.003

Liberating the dimension

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

Computer Science

Research output: Contribution to journal › Article › peer-review

55 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 language	English
Pages (from-to)	422-454
Number of pages	33
Journal	Journal of Complexity
Volume	26
Issue number	5
DOIs	https://doi.org/10.1016/j.jco.2009.12.003
State	Published - 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

Access to Document

10.1016/j.jco.2009.12.003

Cite this

@article{440bea856d4d4180ac0b29d96f3b8bbf,

title = "Liberating the dimension",

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.",

keywords = "Infinite dimensional integration, Randomly shifted lattice rules, Tractability, Worst case error",

author = "Kuo, {Frances Y.} and Sloan, {Ian H.} and Wasilkowski, {Grzegorz W.} and Henryk Wo{\'z}niakowski",

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. ",

year = "2010",

month = oct,

doi = "10.1016/j.jco.2009.12.003",

language = "English",

volume = "26",

pages = "422--454",

number = "5",

}

TY - JOUR

T1 - Liberating the dimension

AU - Kuo, Frances Y.

AU - Sloan, Ian H.

AU - Wasilkowski, Grzegorz W.

AU - Woźniakowski, Henryk

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

PY - 2010/10

Y1 - 2010/10

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

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

KW - Infinite dimensional integration

KW - Randomly shifted lattice rules

KW - Tractability

KW - Worst case error

UR - http://www.scopus.com/inward/record.url?scp=78649751997&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=78649751997&partnerID=8YFLogxK

U2 - 10.1016/j.jco.2009.12.003

DO - 10.1016/j.jco.2009.12.003

M3 - Article

AN - SCOPUS:78649751997

SN - 0885-064X

VL - 26

SP - 422

EP - 454

JO - Journal of Complexity

JF - Journal of Complexity

IS - 5

ER -

Liberating the dimension

Abstract

Bibliographical note

Keywords

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this