Optimal quadrature for Haar wavelet spaces
HTML articles powered by AMS MathViewer
- by Stefan Heinrich, Fred J. Hickernell and Rong-Xian Yue PDF
- Math. Comp. 73 (2004), 259-277 Request permission
Abstract:
This article considers the error of the scrambled equidistribution quadrature rules in the worst-case, random-case, and average-case settings. The underlying space of integrands is a Hilbert space of multidimensional Haar wavelet series, $\mathcal {H}_{\text {wav}}$. The asymptotic orders of the errors are derived for the case of the scrambled $(\lambda ,t,m,s)$-nets and $(t,s)$-sequences. These rules are shown to have the best asymptotic convergence rates for any random quadrature rule for the space of integrands $\mathcal {H}_{\text {wav}}$.References
- Karl Entacher, Quasi-Monte Carlo methods for numerical integration of multivariate Haar series, BIT 37 (1997), no. 4, 846–861. MR 1485869, DOI 10.1007/BF02510355
- Karl Entacher, Quasi-Monte Carlo methods for numerical integration of multivariate Haar series. II, BIT 38 (1998), no. 2, 283–292. MR 1638104, DOI 10.1007/BF02512368
- Stefan Heinrich, Random approximation in numerical analysis, Functional analysis (Essen, 1991) Lecture Notes in Pure and Appl. Math., vol. 150, Dekker, New York, 1994, pp. 123–171. MR 1241675
- 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
- F. J. Hickernell, The mean square discrepancy of randomized nets, ACM Trans. Model. Comput. Simul. 6 (1996), 274–296.
- F. J. Hickernell and H. Woźniakowski, The price of pessimism for multidimensional quadrature, J. Complexity 17 (2001), 625–659.
- 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
- Gerhard Larcher, Digital point sets: analysis and application, Random and quasi-random point sets, Lect. Notes Stat., vol. 138, Springer, New York, 1998, pp. 167–222. MR 1662842, DOI 10.1007/978-1-4612-1702-2_{4}
- G. Larcher, A. Lauss, H. Niederreiter, and W. Ch. Schmid, Optimal polynomials for $(t,m,s)$-nets and numerical integration of multivariate Walsh series, SIAM J. Numer. Anal. 33 (1996), no. 6, 2239–2253. MR 1427461, DOI 10.1137/S0036142994264705
- W.-L. Loh, On the asymptotic distribution of scrambled net quadrature, 2001, submitted for publication.
- Gerhard Larcher and Gottlieb Pirsic, Base change problems for generalized Walsh series and multivariate numerical integration, Pacific J. Math. 189 (1999), no. 1, 75–105. MR 1687739, DOI 10.2140/pjm.1999.189.75
- Harald Niederreiter and Peter Jau-Shyong Shiue (eds.), Monte Carlo and quasi-Monte Carlo methods in scientific computing, Lecture Notes in Statistics, vol. 106, Springer-Verlag, New York, 1995. MR 1445777, DOI 10.1007/978-1-4612-2552-2
- G. Larcher and W. Ch. Schmid, On the numerical integration of high-dimensional Walsh-series by quasi-Monte Carlo methods, Math. Comput. Simulation 38 (1995), no. 1-3, 127–134. Probabilités numériques (Paris, 1992). MR 1341165, DOI 10.1016/0378-4754(93)E0075-G
- G. Larcher, W. Ch. Schmid, and R. Wolf, Quasi-Monte Carlo methods for the numerical integration of multivariate Walsh series, Math. Comput. Modelling 23 (1996), no. 8-9, 55–67. Monte Carlo and quasi-Monte Carlo methods. MR 1398001, DOI 10.1016/0895-7177(96)00039-8
- Gerhard Larcher and Claudia Traunfellner, On the numerical integration of Walsh series by number-theoretic methods, Math. Comp. 63 (1994), no. 207, 277–291. MR 1234426, DOI 10.1090/S0025-5718-1994-1234426-9
- 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
- Erich Novak, Deterministic and stochastic error bounds in numerical analysis, Lecture Notes in Mathematics, vol. 1349, Springer-Verlag, Berlin, 1988. MR 971255, DOI 10.1007/BFb0079792
- H. Niederreiter and G. Pirsic, The microstructure of $(t,m,s)$-nets, J. Complexity 17 (2001), 683–696.
- Harald Niederreiter and Peter Jau-Shyong Shiue (eds.), Monte Carlo and quasi-Monte Carlo methods in scientific computing, Lecture Notes in Statistics, vol. 106, Springer-Verlag, New York, 1995. MR 1445777, DOI 10.1007/978-1-4612-2552-2
- 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
- Art B. Owen, Monte Carlo, quasi-Monte Carlo, and randomized quasi-Monte Carlo, Monte Carlo and quasi-Monte Carlo methods 1998 (Claremont, CA), Springer, Berlin, 2000, pp. 86–97. MR 1849844
- Klaus Ritter, Average-case analysis of numerical problems, Lecture Notes in Mathematics, vol. 1733, Springer-Verlag, Berlin, 2000. MR 1763973, DOI 10.1007/BFb0103934
- R. X. Yue and F. J. Hickernell, Integration and approximation based on scramble sampling in arbitrary dimensions, J. Complexity 17 (2001), 881–897.
- R. X. Yue and F. J. Hickernell, The discrepancy and gain coefficients of scrambled digital nets, J. Complexity 18 (2002), 135–151.
- 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
- Rong-Xian Yue, Variance of quadrature over scrambled unions of nets, Statist. Sinica 9 (1999), no. 2, 451–473. MR 1707849
Additional Information
- Stefan Heinrich
- Affiliation: FB Informatik, Universität Kaiserslautern, PF 3049, D-67653 Kaiserslautern, Germany
- Email: heinrich@informatik.uni-kl.de
- Fred J. Hickernell
- Affiliation: Department of Mathematics, Hong Kong Baptist University, Kowloon Tong, Hong Kong SAR, China
- ORCID: 0000-0001-6677-1324
- Email: fred@hkbu.edu.hk
- Rong-Xian Yue
- Affiliation: College of Mathematical Science, Shanghai Normal University, 100 Guilin Road, Shanghai 200234, China
- Email: rxyue@online.sh.cn
- Received by editor(s): July 9, 2001
- Received by editor(s) in revised form: May 13, 2002
- Published electronically: April 28, 2003
- Additional Notes: This work was partially supported by a Hong Kong Research Grants Council grant HKBU/2030/99P, by Hong Kong Baptist University grant FRG/97-98/II-99, by Shanghai NSF Grant 00JC14057, and by Shanghai Higher Education STF grant 01D01-1.
- © Copyright 2003 American Mathematical Society
- Journal: Math. Comp. 73 (2004), 259-277
- MSC (2000): Primary 65C05, 65D30
- DOI: https://doi.org/10.1090/S0025-5718-03-01531-X
- MathSciNet review: 2034121