Strong tractability of integration using scrambled Niederreiter points

Yue, Rong-Xian; Hickernell, Fred

doi:10.1090/S0025-5718-05-01755-2

Strong tractability of integration using scrambled Niederreiter points
HTML articles powered by AMS MathViewer

by Rong-Xian Yue and Fred J. Hickernell;

Math. Comp. 74 (2005), 1871-1893

DOI: https://doi.org/10.1090/S0025-5718-05-01755-2

Published electronically: March 3, 2005

PDF | Request permission

Abstract:

We study the randomized worst-case error and the randomized error of scrambled quasi–Monte Carlo (QMC) quadrature as proposed by Owen. The function spaces considered in this article are the weighted Hilbert spaces generated by Haar-like wavelets and the weighted Sobolev-Hilbert spaces. Conditions are found under which multivariate integration is strongly tractable in the randomized worst-case setting and the randomized setting, respectively. The $\varepsilon$-exponents of strong tractability are found for the scrambled Niederreiter nets and sequences. The sufficient conditions for strong tractability for Sobolev spaces are more lenient for scrambled QMC quadratures than those for deterministic QMC net quadratures.

References

Stefan Heinrich, Fred J. Hickernell, and Rong-Xian Yue, Optimal quadrature for Haar wavelet spaces, Math. Comp. 73 (2004), no. 245, 259–277. MR 2034121, DOI 10.1090/S0025-5718-03-01531-X
Hickernell, F. J. (1996). The mean square discrepancy of randomized nets, ACM Trans. Model. Comput. Simul. 6, 274-296.
Fred J. Hickernell and Hee Sun Hong, The asymptotic efficiency of randomized nets for quadrature, Math. Comp. 68 (1999), no. 226, 767–791. MR 1609662, DOI 10.1090/S0025-5718-99-01019-4
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
F. J. Hickernell and H. Woźniakowski, Integration and approximation in arbitrary dimensions, Adv. Comput. Math. 12 (2000), no. 1, 25–58. High dimensional integration. MR 1758946, DOI 10.1023/A:1018948631251
Fred J. Hickernell and Henryk Woźniakowski, The price of pessimism for multidimensional quadrature, J. Complexity 17 (2001), no. 4, 625–659. Complexity of multivariate problems (Kowloon, 1999). MR 1881662, DOI 10.1006/jcom.2001.0593
Fred J. Hickernell and Henryk Woźniakowski, Tractability of multivariate integration for periodic functions, J. Complexity 17 (2001), no. 4, 660–682. Complexity of multivariate problems (Kowloon, 1999). MR 1881663, DOI 10.1006/jcom.2001.0592
Fred J. Hickernell and Rong-Xian Yue, The mean square discrepancy of scrambled $(t,s)$-sequences, SIAM J. Numer. Anal. 38 (2000), no. 4, 1089–1112. MR 1786132, DOI 10.1137/S0036142999358019
Kuo, F. Y. and Sloan, I. H. (2004). Quasi-Monte Carlo methods can be efficient for integration over products of spheres, J. Complexity to appear.
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 Gottlieb Pirsic, The microstructure of $(t,m,s)$-nets, J. Complexity 17 (2001), no. 4, 683–696. Complexity of multivariate problems (Kowloon, 1999). MR 1881664, DOI 10.1006/jcom.2001.0596
Art B. Owen, Randomly permuted $(t,m,s)$-nets and $(t,s)$-sequences, Monte Carlo and quasi-Monte Carlo methods in scientific computing (Las Vegas, NV, 1994) Lect. Notes Stat., vol. 106, Springer, New York, 1995, pp. 299–317. MR 1445791, DOI 10.1007/978-1-4612-2552-2_{1}9
Art B. Owen, Monte Carlo variance of scrambled net quadrature, SIAM J. Numer. Anal. 34 (1997), no. 5, 1884–1910. MR 1472202, DOI 10.1137/S0036142994277468
Art B. Owen, Scrambled net variance for integrals of smooth functions, Ann. Statist. 25 (1997), no. 4, 1541–1562. MR 1463564, DOI 10.1214/aos/1031594731
Art B. Owen, Scrambling Sobol′and Niederreiter-Xing points, J. Complexity 14 (1998), no. 4, 466–489. MR 1659008, DOI 10.1006/jcom.1998.0487
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
Ian H. Sloan and Henryk Woźniakowski, Tractability of multivariate integration for weighted Korobov classes, J. Complexity 17 (2001), no. 4, 697–721. Complexity of multivariate problems (Kowloon, 1999). MR 1881665, DOI 10.1006/jcom.2001.0599
Ian H. Sloan and Henryk Woźniakowski, When does Monte Carlo depend polynomially on the number of variables?, Monte Carlo and quasi-Monte Carlo methods 2002, Springer, Berlin, 2004, pp. 407–437. MR 2076949
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
Grace Wahba, Spline models for observational data, CBMS-NSF Regional Conference Series in Applied Mathematics, vol. 59, Society for Industrial and Applied Mathematics (SIAM), Philadelphia, PA, 1990. MR 1045442, DOI 10.1137/1.9781611970128
Xiaoqun Wang, A constructive approach to strong tractability using quasi-Monte Carlo algorithms, J. Complexity 18 (2002), no. 3, 683–701. MR 1928803, DOI 10.1006/jcom.2002.0641
Xiaoqun Wang, Strong tractability of multivariate integration using quasi-Monte Carlo algorithms, Math. Comp. 72 (2003), no. 242, 823–838. MR 1954970, DOI 10.1090/S0025-5718-02-01440-0
Henryk Woźniakowski, Efficiency of quasi-Monte Carlo algorithms for high dimensional integrals, Monte Carlo and quasi-Monte Carlo methods 1998 (Claremont, CA), Springer, Berlin, 2000, pp. 114–136. MR 1849846
Rong-Xian Yue and Fred J. Hickernell, Integration and approximation based on scramble sampling in arbitrary dimensions, J. Complexity 17 (2001), no. 4, 881–897. Complexity of multivariate problems (Kowloon, 1999). MR 1881675, DOI 10.1006/jcom.2001.0602
Rong-Xian Yue, Variance of quadrature over scrambled unions of nets, Statist. Sinica 9 (1999), no. 2, 451–473. MR 1707849
Rong-Xian Yue and Shi-Song Mao, On the variance of quadrature over scrambled nets and sequences, Statist. Probab. Lett. 44 (1999), no. 3, 267–280. MR 1711617, DOI 10.1016/S0167-7152(99)00018-8