Optimal Randomized Multilevel Algorithms for Infinite-Dimensional Integration on Function Spaces with ANOVA-Type Decomposition

Michael Gnewuch and Jan Baldeaux
Additional contact information
Michael Gnewuch: School of Mathematics and Statistics, University of New South Wales

No 313, Research Paper Series from Quantitative Finance Research Centre, University of Technology, Sydney

Abstract: In this paper, we consider the infinite-dimensional integration problem on weighted reproducing kernel Hilbert spaces with norms induced by an underlying function space decomposition of ANOVA-type. The weights model the relative importance of different groups of variables. We present new randomized multilevel algorithms to tackle this integration problem and prove upper bounds for their randomized error. Furthermore, we provide in this setting the first non-trivial lower error bounds for general randomized algorithms, which, in particular, may be adaptive or non-linear. These lower bounds show that our multilevel algorithms are optimal. Our analysis refines and extends the analysis provided in [F. J. Hickernell, T. Muller-Gronbach, B. Niu, K. Ritter, J. Complexity 26 (2010), 229–254], and our error bounds improve substantially on the error bounds presented there. As an illustrative example, we discuss the unanchored Sobolev space and employ randomized quasi-Monte Carlo multilevel algorithms based on scrambled polynomial lattice rules.

Keywords: multilevel algorithms; ANOVA decomposition; randomized algorithms; numerical integration; reproducing kernel Hilbert spaces; scrambled polynomial lattice rules (search for similar items in EconPapers)
Pages: 32 pages
Date: 2012-09-01
References: View references in EconPapers View complete reference list from CitEc
Citations:

Published as: Gnewuch, M. and Baldeaux, J., 2014, "Optimal Randomized Multilevel Algorithms for Infinite-Dimensional Integration on Function Spaces with ANOVA-Type Decomposition", SIAM Journal on Numerical Analysis, 52(3), 1128-1155.

Downloads: (external link)
https://www.uts.edu.au/sites/default/files/qfr-archive-03/QFR-rp313.pdf (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:uts:rpaper:313

Access Statistics for this paper

More papers in Research Paper Series from Quantitative Finance Research Centre, University of Technology, Sydney PO Box 123, Broadway, NSW 2007, Australia. Contact information at EDIRC.
Bibliographic data for series maintained by Duncan Ford ().