Remote Access Mathematics of Computation
Green Open Access

Mathematics of Computation

ISSN 1088-6842(online) ISSN 0025-5718(print)



Infinite-dimensional integration on weighted Hilbert spaces

Author: Michael Gnewuch
Journal: Math. Comp. 81 (2012), 2175-2205
MSC (2010): Primary 65C05, 65D30; Secondary 11K38
Published electronically: April 5, 2012
MathSciNet review: 2945151
Full-text PDF

Abstract | References | Similar Articles | Additional Information

Abstract: We study the numerical integration problem for functions with infinitely many variables which stem from a weighted reproducing kernel Hilbert space. We study the worst case $ \varepsilon $-complexity which is defined as the minimal cost among all algorithms whose worst case error over the Hilbert space unit ball is at most $ \varepsilon $. Here we assume that the cost of evaluating a function depends polynomially on the number of active variables. The infinite-dimensional integration problem is tractable if the $ \varepsilon $-complexity is bounded by a constant times a power of $ 1/\varepsilon $. The smallest such power is called the exponent of tractability.

We provide improved lower bounds for the exponent of tractability for general finite-order weights and, with the help of multilevel algorithms, improved upper bounds for three newly defined classes of finite-order weights. The newly defined finite-intersection weights model the situation where each group of variables interacts with at most $ \rho $ other groups of variables, $ \rho $ some fixed number. For these weights we obtain sharp upper bounds for any decay of the weights and any polynomial degree of the cost function. For the other two classes of finite-order weights our upper bounds are sharp if, e.g., the decay of the weights is fast or slow enough.

Furthermore, we deduce a lower bound for the exponent of tractability for arbitrary weights and a constructive upper bound for product weights.

References [Enhancements On Off] (What's this?)

  • 1. N. Aroszajn, Theory of reproducing kernels, Trans. Amer. Math. Soc. 68 (1950), 337-404. MR 0051437 (14:479c)
  • 2. J. Baldeaux, Scrambled polynomial lattice rules for infinite-dimensional integration, preprint Math. Archive 2010, to appear in Monte Carlo and Quasi-Monte Carlo Methods 2010.
  • 3. J. Creutzig, S. Dereich, T. Müller-Gronbach, K. Ritter, Infinite-dimensional quadrature and approximation of distributions, Found. Comput. Math. 9 (2009), 391-429. MR 2519865 (2010h:65027)
  • 4. J. Dick, I. H. Sloan, X. Wang, H. Woźniakowski, Liberating the weights, J. Complexity 20 (2004), 593-623. MR 2086942 (2005h:65008)
  • 5. J. Dick, I. H. Sloan, X. Wang, H. Woźniakowski, Good lattice rules in weighted Korobov spaces with general weights, Numer. Math. 103 (2006), 63-97. MR 2207615 (2006m:65014)
  • 6. B. Doerr, M. Gnewuch, M. Wahlström, Algorithmic construction of low-discrepancy point sets via dependent randomized rounding, J. Complexity 26 (2010), 490-507. MR 2719644
  • 7. H. Faure, Discrépance de suites associées à un système de numèration (en dimension $ s$), Acta Arith. 41 (1982), 337-351. MR 677547 (84m:10050)
  • 8. M. B. Giles, Multilevel Monte Carlo path simulation, Oper. Res. 56 (2008), 607-617. MR 2436856 (2009g:65008)
  • 9. M. B. Giles, Improved multilevel Monte Carlo convergence using the Milstein scheme, in: A. Keller, S. Heinrich, H. Niederreiter (Eds.), Monte Carlo and Quasi-Monte Carlo Methods 2006, 343-358, Springer, Berlin-Heidelberg, 2008. MR 2479233 (2010c:65007)
  • 10. M. B. Giles, B. J. Waterhouse, Multilevel quasi-Monte Carlo path simulation, Radon Ser. Comput. Appl. Math. 8 (2009), 165-181. MR 2648461 (2011c:91261)
  • 11. M. Gnewuch, Weighted geometric discrepancies and numerical integration on reproducing kernel Hilbert spaces, J. Complexity 2011. (doi:10.1016/j.jco.2011.02.003)
  • 12. M. Gnewuch, H. Woźniakowski, Generalized tractability for multivariate problems, Part I: Linear tensor product problems and linear information, J. Complexity 23 (2007), 262-295. MR 2314760 (2008d:65164)
  • 13. M. Gnewuch, H. Woźniakowski, Generalized Tractability for Linear Functionals, in: A. Keller, S. Heinrich, H. Niederreiter (Eds.), Monte Carlo and Quasi-Monte Carlo Methods 2006, 359-381, Springer, Berlin-Heidelberg, 2008. MR 2479234 (2010d:41040)
  • 14. J. H. Halton, On the efficiency of certain quasi-random sequences of points in evaluating multi-dimensional integrals, Numer. Math. 2 (1960), 84-90. MR 0121961 (22:12688)
  • 15. S. Heinrich, Monte Carlo complexity of global solution of integral equations, J. Complexity 14 (1998), 151-175. MR 1629093 (99g:65135)
  • 16. S. Heinrich, Multilevel Monte Carlo methods, in: S. Margenov, J. Wasniewski, P. Yalamov (Eds.), Large Scale Scientific Computing, LNiCS 2179, 58-67, Springer, Berlin, 2001.
  • 17. F. J. Hickernell, A generalized discrepancy and quadrature error bound, Math. Comp. 67 (1998), 299-322. MR 1433265 (98c:65032)
  • 18. F. J. Hickernell, T. Müller-Gronbach, B. Niu, K. Ritter, Multi-level Monte Carlo algorithms for infinite-dimensional integration on $ \mathbb{R}^{\mathbb{N}}$, J. Complexity 26 (2010), 229-254. MR 2657363 (2011d:65008)
  • 19. F. J. Hickernell, I. H. Sloan, G. W. Wasilkowski, The strong tractability of multivariate integration using lattice rules, in: H. Niederreiter (Ed.), Monte Carlo and Quasi-Monte Carlo Methods 2002, Springer, Berlin, 2004. MR 2076938
  • 20. F. J. Hickernell, X. Wang, The error bounds and tractability of quasi-Monte Carlo algorithms in infinite dimension, Math. Comp. 71 (2002), 1641-1661. MR 1933048 (2003i:65009)
  • 21. S. Joe, Component by component construction of rank-$ 1$ lattice rules having $ O(n^{-1}(\mathrm {ln}\, n)^d)$ star discrepancy, in: H. Niederreiter (Ed.), Monte Carlo and Quasi-Monte Carlo Methods 2002, 293-298, Springer, Berlin Heidelberg, 2004. MR 2076940
  • 22. F. Y. Kuo, I. H. Sloan, G. W. Wasilkowski, H. Woźniakowski, Liberating the dimension, J. Complexity 26 (2010), 422-454. MR 2719642
  • 23. F. Y. Kuo, I. H. Sloan, G. W. Wasilkowski, H. Woźniakowski, On decompositions of multivariate functions, Math. Comput. 79 (2010), 953-966. MR 2600550 (2011a:41039)
  • 24. T. Müller-Gronbach, K. Ritter, Variable subspace sampling and multi-level algorithms, in: P. L'Ecuyer, A. B. Owen (Eds.), Monte Carlo and Quasi-Monte Carlo Methods 2008, 131-156, Springer, Heidelberg, 2009. MR 2743892
  • 25. H. Niederreiter, Low-discrepancy and low-dispersion sequences, J. Number Theory 30 (1988), 51-70. MR 960233 (89k:11064)
  • 26. H. Niederreiter, Random Number Generation and Quasi-Monte Carlo Methods, SIAM, Philadelphia, 1992. MR 1172997 (93h:65008)
  • 27. H. Niederreiter, C. Xing, Low-discrepancy sequences and global function fields with many rational places, Finite Field Appl. 2 (1996), 241-273. MR 1398076 (97h:11080)
  • 28. B. Niu, F. J. Hickernell, Monte Carlo simulation of stochastic integrals when the cost of function evaluations is dimension dependent, in: P. L'Ecuyer, A. B. Owen (Eds.), Monte Carlo and Quasi-Monte Carlo Methods 2008, 545-560, Springer, Heidelberg, 2009. MR 2743918
  • 29. B. Niu, F. J. Hickernell, T. Müller-Gronbach, K. Ritter, Deterministic multi-level algorithms for infinite-dimensional integration on $ \mathbb{R}^{\mathbb{N}}$, J. Complexity 27 (2011), 331-351.
  • 30. E. Novak, H. Woźniakowski, $ L_2$ discrepancy and multivariate integration, in: Analytic Number Theory: Essays in Honour of Klaus Roth, W. W. Chen, W. T. Gowers, H. Halberstam, W. M. Schmidt, R. C. Vaughan (Eds.), Cambridge University Press, 359-388, 2008. MR 2508657 (2010d:11088)
  • 31. E. Novak, H. Woźniakowski, Tractability of Multivariate Problems, Volume I, European Mathematical Society, Zürich, 2008. MR 2455266 (2009m:46037)
  • 32. E. Novak, H. Woźniakowski, Tractability of Multivariate Problems, Volume II, European Mathematical Society, Zürich, 2010. MR 2676032 (2011h:46093)
  • 33. L. Plaskota, G. W. Wasilkowski, Tractability of infinite-dimensional integration in the worst case and randomized settings, J. Complexity 2011. (doi:10.1016/j.jco.2011.01.006)
  • 34. L. Plaskota, G. W. Wasilkowski, H. Woźniakowski, A new algorithm and worst case complexity for Feynman-Kac path integration, J. of Computational Physics 164 (2000), 335-353. MR 1792515 (2001i:65146)
  • 35. I. H. Sloan, X. Wang, H. Woźniakowski, Finite-order weights imply tractability of multivariate integration, J. Complexity 20 (2004), 46-74. MR 2031558 (2004j:65034)
  • 36. I. H. Sloan, H. Woźniakowski, When are quasi-Monte Carlo algorithms efficient for high dimensional integrals?, J. Complexity 14 (1998), 1-33. MR 1617765 (99d:65384)
  • 37. I. M. Sobol', The distribution of points in a cube and the approximate evaluation of integrals, Zh. Vychisl. Mat. i Mat. Fiz. 7 (1967), 748-802. (Russian) MR 0219238 (36:2321)
  • 38. J. F. Traub, G. W. Wasilkowski, H. Woźniakowski, Information-Based Complexity, Academic Press, New York, 1988. MR 958691 (90f:68085)
  • 39. G. W. Wasilkowski and H. Woźniakowski, On tractability of path integration, J. Math. Physics 37 (1996), 2071-2088. MR 1380891 (97a:65010)

Similar Articles

Retrieve articles in Mathematics of Computation with MSC (2010): 65C05, 65D30, 11K38

Retrieve articles in all journals with MSC (2010): 65C05, 65D30, 11K38

Additional Information

Michael Gnewuch
Affiliation: Department of Computer Science, Columbia University, 1214 Amsterdam Avenue, New York, New York 10027

Received by editor(s): May 21, 2010
Received by editor(s) in revised form: May 31, 2011
Published electronically: April 5, 2012
Article copyright: © Copyright 2012 American Mathematical Society
The copyright for this article reverts to public domain 28 years after publication.

American Mathematical Society