Optimal quadrature for Haar wavelet spaces

Heinrich, Stefan; Hickernell, Fred; Yue, Rong-Xian

doi:10.1090/S0025-5718-03-01531-X

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