Infinite-dimensional integration on weighted Hilbert spaces

Gnewuch, Michael

doi:10.1090/S0025-5718-2012-02583-X

Infinite-dimensional integration on weighted Hilbert spaces
HTML articles powered by AMS MathViewer

by Michael Gnewuch PDF

Math. Comp. 81 (2012), 2175-2205 Request permission

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

N. Aronszajn, Theory of reproducing kernels, Trans. Amer. Math. Soc. 68 (1950), 337–404. MR 51437, DOI 10.1090/S0002-9947-1950-0051437-7
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.
Jakob Creutzig, Steffen Dereich, Thomas Müller-Gronbach, and Klaus Ritter, Infinite-dimensional quadrature and approximation of distributions, Found. Comput. Math. 9 (2009), no. 4, 391–429. MR 2519865, DOI 10.1007/s10208-008-9029-x
Josef Dick, Ian H. Sloan, Xiaoqun Wang, and Henryk Woźniakowski, Liberating the weights, J. Complexity 20 (2004), no. 5, 593–623. MR 2086942, DOI 10.1016/j.jco.2003.06.002
Josef Dick, Ian H. Sloan, Xiaoqun Wang, and Henryk Woźniakowski, Good lattice rules in weighted Korobov spaces with general weights, Numer. Math. 103 (2006), no. 1, 63–97. MR 2207615, DOI 10.1007/s00211-005-0674-6
Benjamin Doerr, Michael Gnewuch, and Magnus Wahlström, Algorithmic construction of low-discrepancy point sets via dependent randomized rounding, J. Complexity 26 (2010), no. 5, 490–507. MR 2719644, DOI 10.1016/j.jco.2010.03.004
Henri Faure, Discrépance de suites associées à un système de numération (en dimension $s$), Acta Arith. 41 (1982), no. 4, 337–351 (French). MR 677547, DOI 10.4064/aa-41-4-337-351
Michael B. Giles, Multilevel Monte Carlo path simulation, Oper. Res. 56 (2008), no. 3, 607–617. MR 2436856, DOI 10.1287/opre.1070.0496
Mike Giles, Improved multilevel Monte Carlo convergence using the Milstein scheme, Monte Carlo and quasi-Monte Carlo methods 2006, Springer, Berlin, 2008, pp. 343–358. MR 2479233, DOI 10.1007/978-3-540-74496-2_{2}0
Michael B. Giles and Benjamin J. Waterhouse, Multilevel quasi-Monte Carlo path simulation, Advanced financial modelling, Radon Ser. Comput. Appl. Math., vol. 8, Walter de Gruyter, Berlin, 2009, pp. 165–181. MR 2648461, DOI 10.1515/9783110213140.165
M. Gnewuch, Weighted geometric discrepancies and numerical integration on reproducing kernel Hilbert spaces, J. Complexity 2011. (doi:10.1016/j.jco.2011.02.003)
Michael Gnewuch and Henryk Woźniakowski, Generalized tractability for multivariate problems. I. Linear tensor product problems and linear information, J. Complexity 23 (2007), no. 2, 262–295. MR 2314760, DOI 10.1016/j.jco.2006.06.006
Michael Gnewuch and Henryk Woźniakowski, Generalized tractability for linear functionals, Monte Carlo and quasi-Monte Carlo methods 2006, Springer, Berlin, 2008, pp. 359–381. MR 2479234, DOI 10.1007/978-3-540-74496-2_{2}1
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 121961, DOI 10.1007/BF01386213
S. Heinrich, Monte Carlo complexity of global solution of integral equations, J. Complexity 14 (1998), no. 2, 151–175. MR 1629093, DOI 10.1006/jcom.1998.0471
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.
Fred J. Hickernell, A generalized discrepancy and quadrature error bound, Math. Comp. 67 (1998), no. 221, 299–322. MR 1433265, DOI 10.1090/S0025-5718-98-00894-1
Fred J. Hickernell, Thomas Müller-Gronbach, Ben Niu, and Klaus Ritter, Multi-level Monte Carlo algorithms for infinite-dimensional integration on $\Bbb R^{\Bbb N}$, J. Complexity 26 (2010), no. 3, 229–254. MR 2657363, DOI 10.1016/j.jco.2010.02.002
Fred J. Hickernell, Ian H. Sloan, and Grzegorz W. Wasilkowski, The strong tractability of multivariate integration using lattice rules, Monte Carlo and quasi-Monte Carlo methods 2002, Springer, Berlin, 2004, pp. 259–273. MR 2076938
Fred J. Hickernell and Xiaoqun Wang, The error bounds and tractability of quasi-Monte Carlo algorithms in infinite dimension, Math. Comp. 71 (2002), no. 240, 1641–1661. MR 1933048, DOI 10.1090/S0025-5718-01-01377-1
Stephen Joe, Component by component construction of rank-1 lattice rules having $O(n^{-1}(\ln (n))^d)$ star discrepancy, Monte Carlo and quasi-Monte Carlo methods 2002, Springer, Berlin, 2004, pp. 293–298. MR 2076940
Frances Y. Kuo, Ian H. Sloan, Grzegorz W. Wasilkowski, and Henryk Woźniakowski, Liberating the dimension, J. Complexity 26 (2010), no. 5, 422–454. MR 2719642, DOI 10.1016/j.jco.2009.12.003
F. Y. Kuo, I. H. Sloan, G. W. Wasilkowski, and H. Woźniakowski, On decompositions of multivariate functions, Math. Comp. 79 (2010), no. 270, 953–966. MR 2600550, DOI 10.1090/S0025-5718-09-02319-9
Thomas Müller-Gronbach and Klaus Ritter, Variable subspace sampling and multi-level algorithms, Monte Carlo and quasi-Monte Carlo methods 2008, Springer, Berlin, 2009, pp. 131–156. MR 2743892, DOI 10.1007/978-3-642-04107-5_{8}
Harald Niederreiter, Low-discrepancy and low-dispersion sequences, J. Number Theory 30 (1988), no. 1, 51–70. MR 960233, DOI 10.1016/0022-314X(88)90025-X
Harald Niederreiter, Random number generation and quasi-Monte Carlo methods, CBMS-NSF Regional Conference Series in Applied Mathematics, vol. 63, Society for Industrial and Applied Mathematics (SIAM), Philadelphia, PA, 1992. MR 1172997, DOI 10.1137/1.9781611970081
Harald Niederreiter and Chaoping Xing, Low-discrepancy sequences and global function fields with many rational places, Finite Fields Appl. 2 (1996), no. 3, 241–273. MR 1398076, DOI 10.1006/ffta.1996.0016
Ben Niu and Fred J. Hickernell, Monte Carlo simulation of stochastic integrals when the cost of function evaluation is dimension dependent, Monte Carlo and quasi-Monte Carlo methods 2008, Springer, Berlin, 2009, pp. 545–560. MR 2743918, DOI 10.1007/978-3-642-04107-5_{3}5
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.
Erich Novak and Henryk Woźniakowski, $L_2$ discrepancy and multivariate integration, Analytic number theory, Cambridge Univ. Press, Cambridge, 2009, pp. 359–388. MR 2508657
Erich Novak and Henryk Woźniakowski, Tractability of multivariate problems. Vol. 1: Linear information, EMS Tracts in Mathematics, vol. 6, European Mathematical Society (EMS), Zürich, 2008. MR 2455266, DOI 10.4171/026
Erich Novak and Henryk Woźniakowski, Tractability of multivariate problems. Volume II: Standard information for functionals, EMS Tracts in Mathematics, vol. 12, European Mathematical Society (EMS), Zürich, 2010. MR 2676032, DOI 10.4171/084
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)
Leszek Plaskota, Grzegorz W. Wasilkowski, and Henryk Woźniakowski, A new algorithm and worst case complexity for Feynman-Kac path integration, J. Comput. Phys. 164 (2000), no. 2, 335–353. MR 1792515, DOI 10.1006/jcph.2000.6599
Ian H. Sloan, Xiaoqun Wang, and Henryk Woźniakowski, Finite-order weights imply tractability of multivariate integration, J. Complexity 20 (2004), no. 1, 46–74. MR 2031558, DOI 10.1016/j.jco.2003.11.003
Ian H. Sloan and Henryk Woźniakowski, When are quasi-Monte Carlo algorithms efficient for high-dimensional integrals?, J. Complexity 14 (1998), no. 1, 1–33. MR 1617765, DOI 10.1006/jcom.1997.0463
I. M. Sobol′, Distribution of points in a cube and approximate evaluation of integrals, Ž. Vyčisl. Mat i Mat. Fiz. 7 (1967), 784–802 (Russian). MR 219238
J. F. Traub, G. W. Wasilkowski, and H. Woźniakowski, Information-based complexity, Computer Science and Scientific Computing, Academic Press, Inc., Boston, MA, 1988. With contributions by A. G. Werschulz and T. Boult. MR 958691
Grzegorz W. Wasilkowski and Henryk Woźniakowski, On tractability of path integration, J. Math. Phys. 37 (1996), no. 4, 2071–2086. MR 1380891, DOI 10.1063/1.531493