We consider approximation of weighted integrals of functions with infinitely many variables in the worst case deterministic and randomized settings. We assume that the integrands f belong to a weighted quasi-reproducing kernel Hilbert space, where the weights have product form and satisfy γj=O(j-β) for β>1. The cost of computing f(x) depends on the number Act(x) of active coordinates in x and is equal to (Act(x)), where is a given cost function. We prove, in particular, that if the corresponding univariate problem admits algorithms with errors O(n -κ2), where n is the number of function evaluations, then the ∞-variate problem is polynomially tractable with the tractability exponent bounded from above by max(2κ,2(β-1)) for all cost functions satisfying (d)=O(ek·d), for any k<0. This bound is sharp in the worst case setting if β and κ are chosen as large as possible and (d) is at least linear in d. The problem is weakly tractable even for a larger class of cost functions including (d)=O(ek·d). Moreover, our proofs are constructive.
|Number of pages||14|
|Journal||Journal of Complexity|
|State||Published - Dec 2011|
Bibliographical noteFunding Information:
We would like to thank Michael Gnewuch and Klaus Ritter for valuable comments concerning this paper. We also thank the anonymous reviewers whose remarks helped to improve the presentation. This research is partially supported by a grant from the Ministry of Science and Higher Education of Poland for 2010–2013.
- Infinite dimensional integration
- Worst case setting
ASJC Scopus subject areas
- Algebra and Number Theory
- Statistics and Probability
- Numerical Analysis
- Mathematics (all)
- Control and Optimization
- Applied Mathematics