Available in electronic format
Available in print format		 Mathematics of Computation
Journal of the American Mathematical Society
ISSN 1088-6842(e) ISSN 0025-5718(p)
Previous issue | Table of contents | Next issue
Articles in press | Recently posted articles | Most recent issue | All issues
Previous Article | Next Article
     

Optimal quadrature for Haar wavelet spaces

Author(s): Stefan Heinrich; Fred J. Hickernell; Rong-Xian Yue.
Journal: Math. Comp. 73 (2004), 259-277.
MSC (2000): Primary 65C05, 65D30
Posted: April 28, 2003
Retrieve article in: PDF DVI PostScript

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:

[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
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: 10.1090/S0025-5718-03-01531-X
PII: S 0025-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
Posted: 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 of article: Copyright 2003, American Mathematical Society

  AMS Website Logo Small Comments: webmaster@ams.org
© Copyright 2008, American Mathematical Society
Privacy Statement 		Search the AMSPowered by Google