Remote Access Mathematics of Computation
Green Open Access

Mathematics of Computation

ISSN 1088-6842(online) ISSN 0025-5718(print)



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
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, $\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 [Enhancements On Off] (What's this?)

  • [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 $(t,s)$-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 $(t,m,s)$-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 $(t,m,s)$-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 $(t,m,s)$-nets and $(t,s)$-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

Similar Articles

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

Fred J. Hickernell
Affiliation: Department of Mathematics, Hong Kong Baptist University, Kowloon Tong, Hong Kong SAR, China

Rong-Xian Yue
Affiliation: College of Mathematical Science, Shanghai Normal University, 100 Guilin Road, Shanghai 200234, China

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

American Mathematical Society