Strong tractability of integration using scrambled Niederreiter points
HTML articles powered by AMS MathViewer
- by Rong-Xian Yue and Fred J. Hickernell PDF
- Math. Comp. 74 (2005), 1871-1893 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
Additional Information
- Rong-Xian Yue
- Affiliation: Division of Scientific Computation, E-Institute of Shanghai Universities, 100 Guilin Road, Shanghai 200234, People’s Republic of China
- Email: yue2@shnu.edu.cn
- Fred J. Hickernell
- Affiliation: Department of Applied Mathematics, Shanghai Normal University, Shanghai, People’s Republic of China
- Address at time of publication: Department of Applied Mathematics, Illinois Institute of Technology, 10 West 32nd Street, E1 Building, Room 208, Chicago, Illinois 60616-3793
- ORCID: 0000-0001-6677-1324
- Email: fred@hkbu.edu.hk, hickernell@iit.edu
- Received by editor(s): November 24, 2003
- Received by editor(s) in revised form: July 6, 2004
- Published electronically: March 3, 2005
- Additional Notes: This work was partially supported by Hong Kong Research Grants Council grant HKBU/2020/02P, National Science Foundation of China grant 10271078, E-Institute of Shanghai Municipal Education Commission (E03004), and the Special Funds for Major Specialties of the Shanghai Education Committee
- © Copyright 2005 American Mathematical Society
- Journal: Math. Comp. 74 (2005), 1871-1893
- MSC (2000): Primary 65C05, 65D30
- DOI: https://doi.org/10.1090/S0025-5718-05-01755-2
- MathSciNet review: 2164101