Optimal quadrature for Haar wavelet spaces

Authors:
Stefan Heinrich, Fred J. Hickernell and Rong-Xian Yue

Journal:
Math. Comp. **73** (2004), 259-277

MSC (2000):
Primary 65C05, 65D30

DOI:
https://doi.org/10.1090/S0025-5718-03-01531-X

Published electronically:
April 28, 2003

MathSciNet review:
2034121

Full-text PDF

Abstract | References | Similar Articles | Additional Information

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, . The asymptotic orders of the errors are derived for the case of the scrambled -nets and -sequences. These rules are shown to have the best asymptotic convergence rates for any random quadrature rule for the space of integrands .

**[Ent97]**K. Entacher,*Quasi-Monte Carlo methods for numerical integration of multivariate Haar series*, BIT**37**(1997), 846-861. MR**98m:65011****[Ent98]**K. Entacher,*Quasi-Monte Carlo methods for numerical integration of multivariate Haar series II*, BIT**38**(1998), 283-292. MR**99h:65010****[Hei93]**S. Heinrich,*Random approximation in numerical analysis*, Functional analysis. Proceedings of the Essen Conference, held in Essen, Germany, November 24 - 30, 1991. (K. D. Bierstedt, A. Pietsch, W. M. Ruess, and D. Vogt, eds.), Lecture Notes in Pure and Applied Mathematics, vol. 150, Marcel Dekker, New York, 1993, pp. 123-171. MR**94i:65015****[HH99]**F. J. Hickernell and H. S. Hong,*The asymptotic efficiency of randomized nets for quadrature*, Math. Comp.**68**(1999), 767-791. MR**99i:65021****[Hic96]**F. J. Hickernell,*The mean square discrepancy of randomized nets*, ACM Trans. Model. Comput. Simul.**6**(1996), 274-296.**[HW01]**F. J. Hickernell and H. Wozniakowski,*The price of pessimism for multidimensional quadrature*, J. Complexity**17**(2001), 625-659.**[HY00]**F. J. Hickernell and R. X. Yue,*The mean square discrepancy of scrambled -sequences*, SIAM J. Numer. Anal.**38**(2000), 1089-1112. MR**2002c:65009****[Lar98]**G. Larcher,*Digital point sets: Analysis and applications*, Random and Quasi-Random Point Sets (P. Hellekalek and G. Larcher, eds.), Lecture Notes in Statistics, vol. 138, Springer-Verlag, New York, 1998, pp. 167-222. MR**99m:11085****[LLNS96]**G. Larcher, A. Lauss, H. Niederreiter, and W. Ch. Schmid,*Optimal polynomials for -nets and numerical integration of Walsh series*, SIAM J. Numer. Anal.**33**(1996), 2239-2253. MR**97m:65046****[Loh01]**W.-L. Loh,*On the asymptotic distribution of scrambled net quadrature*, 2001, submitted for publication.**[LP99]**G. Larcher and G. Pirsic,*Base change problems for generalized Walsh series and multivariate numerical integration*, Pac. J. Math.**189**(1999), 75-105. MR**2000f:42017****[LS95a]**G. Larcher and W. Ch. Schmid,*Multivariate Walsh-series, digital nets, and quasi-Monte Carlo integration*, In Niederreiter and Shiue [NS95], pp. 252-262. MR**97j:65002****[LS95b]**G. Larcher and W. Ch. Schmid,*On the numerical integration of high dimensional multivariate Walsh-series by quasi-Monte Carlo methods*, Math. Comput. Simul.**38**(1995), 127-134. MR**96c:65009****[LSW96]**G. Larcher, W. Ch. Schmid, and R. Wolf,*Quasi-Monte Carlo methods for the numerical integration of multivariate Walsh series*, Mathl. Comput. Modelling**23**(1996), 55-67. MR**97j:65044****[LT94]**G. Larcher and C. Traunfellner,*On the numerical integration of Walsh series by number-theoretic methods*, Math. Comp.**63**(1994), 277-291. MR**94j:65030****[Nie92]**H. Niederreiter,*Random number generation and quasi-Monte Carlo methods*, CBMS-NSF Regional Conference Series in Applied Mathematics, SIAM, Philadelphia, 1992. MR**93h:65008****[Nov88]**E. Novak,*Deterministic and stochastic error bounds in numerical analysis*, Lectures Notes in Math., no. 1349, Springer-Verlag, Berlin, 1988. MR**90a:65004****[NP01]**H. Niederreiter and G. Pirsic,*The microstructure of -nets*, J. Complexity**17**(2001), 683-696.**[NS95]**H. Niederreiter and P. J.-S. Shiue (eds.),*Monte Carlo and quasi-Monte Carlo methods in scientific computing*, Lecture Notes in Statistics, vol. 106, Springer-Verlag, New York, 1995. MR**97j:65002****[Owe95]**A. B. Owen,*Randomly permuted -nets and -sequences*, In Niederreiter and Shiue [NS95], pp. 299-317. MR**97k:65013****[Owe97a]**A. B. Owen,*Monte Carlo variance of scrambled net quadrature*, SIAM J. Numer. Anal.**34**(1997), 1884-1910. MR**98h:65006****[Owe97b]**A. B. Owen,*Scrambled net variance for integrals of smooth functions*, Ann. Stat.**25**(1997), 1541-1562. MR**98j:65004****[Owe98]**A. B. Owen,*Scrambling Sobol' and Niederreiter-Xing points*, J. Complexity**14**(1998), 466-489. MR**2000c:65005****[Owe00]**A. B. Owen,*Monte Carlo, quasi-Monte Carlo, and randomized quasi-Monte Carlo*, Monte Carlo and Quasi-Monte Carlo Methods 1998 (H. Niederreiter and J. Spanier, eds.), Springer-Verlag, Berlin, 2000, 86-97. MR**2002e:65013****[Rit00]**K. Ritter,*Average-case analysis of numerical problems*, Lecture Notes in Mathematics, vol. 1733, Springer-Verlag, Berlin, 2000. MR**2001i:65001****[YH01]**R. X. Yue and F. J. Hickernell,*Integration and approximation based on scramble sampling in arbitrary dimensions*, J. Complexity**17**(2001), 881-897.**[YH02]**R. X. Yue and F. J. Hickernell,*The discrepancy and gain coefficients of scrambled digital nets*, J. Complexity**18**(2002), 135-151.**[YM99]**R. X. Yue and S. S. Mao,*On the variance of quadrature over scrambled nets and sequences*, Statist. Probab. Lett.**44**(1999), 267-280. MR**2000i:65008****[Yue99]**R. X. Yue,*Variance of quadrature over scrambled unions of nets*, Statist. Sinica**9**(1999), 451-473. MR**2000h:65022**

Retrieve articles in *Mathematics of Computation*
with MSC (2000):
65C05,
65D30

Retrieve articles in all journals with MSC (2000): 65C05, 65D30

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

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

DOI:
https://doi.org/10.1090/S0025-5718-03-01531-X

Keywords:
Quasi-Monte Carlo methods,
Monte Carlo methods,
high dimensional integration,
lower bounds

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.

Article copyright:
© Copyright 2003
American Mathematical Society