On quasi-Monte Carlo methods in weighted ANOVA spaces
HTML articles powered by AMS MathViewer
- by P. Kritzer, F. Pillichshammer and G. W. Wasilkowski;
- Math. Comp. 90 (2021), 1381-1406
- DOI: https://doi.org/10.1090/mcom/3598
- Published electronically: January 11, 2021
- HTML | PDF | Request permission
Abstract:
In the present paper we study quasi-Monte Carlo rules for approximating integrals over the $d$-dimensional unit cube for functions from weighted Sobolev spaces of regularity one. While the properties of these rules are well understood for anchored Sobolev spaces, this is not the case for the ANOVA spaces, which are another very important type of reference spaces for quasi-Monte Carlo rules.
Using a direct approach we provide a formula for the worst case error of quasi-Monte Carlo rules for functions from weighted ANOVA spaces. As a consequence we bound the worst case error from above in terms of weighted discrepancy of the employed integration nodes. On the other hand we also obtain a general lower bound in terms of the number $n$ of used integration nodes.
For the one-dimensional case our results lead to the optimal integration rule and also in the two-dimensional case we provide rules yielding optimal convergence rates.
References
- Christoph Aistleitner and Josef Dick, Functions of bounded variation, signed measures, and a general Koksma-Hlawka inequality, Acta Arith. 167 (2015), no. 2, 143–171. MR 3312093, DOI 10.4064/aa167-2-4
- Gagik Amirkhanyan, Dmitriy Bilyk, and Michael T. Lacey, Dichotomy results for the $L^1$ norm of the discrepancy function, J. Math. Anal. Appl. 410 (2014), no. 1, 1–6. MR 3109814, DOI 10.1016/j.jmaa.2013.08.002
- Luca Brandolini, Leonardo Colzani, Giacomo Gigante, and Giancarlo Travaglini, On the Koksma-Hlawka inequality, J. Complexity 29 (2013), no. 2, 158–172. MR 3018136, DOI 10.1016/j.jco.2012.10.003
- Josef Dick, Frances Y. Kuo, and Ian H. Sloan, High-dimensional integration: the quasi-Monte Carlo way, Acta Numer. 22 (2013), 133–288. MR 3038697, DOI 10.1017/S0962492913000044
- Josef Dick and Friedrich Pillichshammer, Digital nets and sequences, Cambridge University Press, Cambridge, 2010. Discrepancy theory and quasi-Monte Carlo integration. MR 2683394, DOI 10.1017/CBO9780511761188
- Josef Dick and Friedrich Pillichshammer, The weighted star discrepancy of Korobov’s $p$-sets, Proc. Amer. Math. Soc. 143 (2015), no. 12, 5043–5057. MR 3411125, DOI 10.1090/proc/12636
- Henri Faure, Star extreme discrepancy of generalized two-dimensional Hammersley point sets, Unif. Distrib. Theory 3 (2008), no. 2, 45–65. MR 2452584
- Henri Faure and Friedrich Pillichshammer, $L_p$ discrepancy of generalized two-dimensional Hammersley point sets, Monatsh. Math. 158 (2009), no. 1, 31–61. MR 2525920, DOI 10.1007/s00605-008-0039-1
- M. Gnewuch, M. Hefter, A. Hinrichs, K. Ritter, and G. W. Wasilkowski, Equivalence of weighted anchored and ANOVA spaces of functions with mixed smoothness of order one in $L_p$, J. Complexity 40 (2017), 78–99. MR 3631818, DOI 10.1016/j.jco.2017.01.001
- G. Halász, Roth’s method in the theory of irregularities of point distributions, Recent progress in analytic number theory, Vol. 2 (Durham, 1979), pp. 79–94, Academic Press, London-New York, 1981.
- Mario Hefter and Klaus Ritter, On embeddings of weighted tensor product Hilbert spaces, J. Complexity 31 (2015), no. 3, 405–423. MR 3325681, DOI 10.1016/j.jco.2014.03.003
- M. Hefter, K. Ritter, and G. W. Wasilkowski, On equivalence of weighted anchored and ANOVA spaces of functions with mixed smoothness of order one in $L_1$ or $L_\infty$, J. Complexity 32 (2016), no. 1, 1–19. MR 3424634, DOI 10.1016/j.jco.2015.07.001
- Fred J. Hickernell, A generalized discrepancy and quadrature error bound, Math. Comp. 67 (1998), no. 221, 299–322. MR 1433265, DOI 10.1090/S0025-5718-98-00894-1
- Aicke Hinrichs, Peter Kritzer, Friedrich Pillichshammer, and G. W. Wasilkowski, Truncation dimension for linear problems on multivariate function spaces, Numer. Algorithms 80 (2019), no. 2, 661–685. MR 3905510, DOI 10.1007/s11075-018-0501-7
- Aicke Hinrichs, Ralph Kritzinger, and Friedrich Pillichshammer, Optimal order of $L_p$-discrepancy of digit shifted Hammersley point sets in dimension 2, Unif. Distrib. Theory 10 (2015), no. 1, 115–133. MR 3408580
- Aicke Hinrichs and Jan Schneider, Equivalence of anchored and ANOVA spaces via interpolation, J. Complexity 33 (2016), 190–198. MR 3450729, DOI 10.1016/j.jco.2015.11.002
- Edmund Hlawka, Funktionen von beschränkter Variation in der Theorie der Gleichverteilung, Ann. Mat. Pura Appl. (4) 54 (1961), 325–333 (German). MR 139597, DOI 10.1007/BF02415361
- J. F. Koksma, A general theorem from the theory of uniform distribution modulo 1, Mathematica, Zutphen. B. 11 (1942), 7–11 (Dutch). MR 15094
- Peter Kritzer, Gerhard Larcher, and Friedrich Pillichshammer, A thorough analysis of the discrepancy of shifted Hammersley and van der Corput point sets, Ann. Mat. Pura Appl. (4) 186 (2007), no. 2, 229–250. MR 2295117, DOI 10.1007/s10231-006-0002-5
- Peter Kritzer, Friedrich Pillichshammer, and G. W. Wasilkowski, Very low truncation dimension for high dimensional integration under modest error demand, J. Complexity 35 (2016), 63–85. MR 3507353, DOI 10.1016/j.jco.2016.02.002
- Peter Kritzer, Friedrich Pillichshammer, and G. W. Wasilkowski, A note on equivalence of anchored and ANOVA spaces; lower bounds, J. Complexity 38 (2017), 31–38. MR 3574544, DOI 10.1016/j.jco.2016.06.001
- Ralph Kritzinger and Markus Passenbrunner, Extremal distributions of discrepancy functions, J. Complexity 54 (2019), 101409, 10. MR 3983219, DOI 10.1016/j.jco.2019.05.003
- Ralph Kritzinger and Friedrich Pillichshammer, Digital nets in dimension two with the optimal order of $L_p$ discrepancy, J. Théor. Nombres Bordeaux 31 (2019), no. 1, 179–204 (English, with English and French summaries). MR 3994725
- Gunther Leobacher and Friedrich Pillichshammer, Bounds for the weighted $L^p$ discrepancy and tractability of integration, J. Complexity 19 (2003), no. 4, 529–547. MR 1991981, DOI 10.1016/S0885-064X(03)00009-8
- Gunther Leobacher and Friedrich Pillichshammer, Introduction to quasi-Monte Carlo integration and applications, Compact Textbooks in Mathematics, Birkhäuser/Springer, Cham, 2014. MR 3289176, DOI 10.1007/978-3-319-03425-6
- Lev Markhasin, Discrepancy of generalized Hammersley type point sets in Besov spaces with dominating mixed smoothness, Unif. Distrib. Theory 8 (2013), no. 1, 135–164. MR 3112211
- H. Niederreiter, Application of Diophantine approximations to numerical integration, Diophantine approximation and its applications (Proc. Conf., Washington, D.C., 1972) Academic Press, New York-London, 1973, pp. 129–199. MR 357357
- 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 and Henryk Woźniakowski, Tractability of multivariate problems. Vol. 1: Linear information, EMS Tracts in Mathematics, vol. 6, European Mathematical Society (EMS), Zürich, 2008. MR 2455266, DOI 10.4171/026
- Erich Novak and Henryk Woźniakowski, Tractability of multivariate problems. Volume II: Standard information for functionals, EMS Tracts in Mathematics, vol. 12, European Mathematical Society (EMS), Zürich, 2010. MR 2676032, DOI 10.4171/084
- Florian Pausinger and Anne Marie Svane, A Koksma-Hlawka inequality for general discrepancy systems, J. Complexity 31 (2015), no. 6, 773–797. MR 3400993, DOI 10.1016/j.jco.2015.06.002
- K. F. Roth, On irregularities of distribution, Mathematika 1 (1954), 73–79. MR 66435, DOI 10.1112/S0025579300000541
- Wolfgang M. Schmidt, Irregularities of distribution. VII, Acta Arith. 21 (1972), 45–50. MR 319933, DOI 10.4064/aa-21-1-45-50
- Wolfgang M. Schmidt, Irregularities of distribution. X, Number theory and algebra, Academic Press, New York-London, 1977, pp. 311–329. MR 491574
- Ian H. Sloan and Henryk Woźniakowski, When are quasi-Monte Carlo algorithms efficient for high-dimensional integrals?, J. Complexity 14 (1998), no. 1, 1–33. MR 1617765, DOI 10.1006/jcom.1997.0463
- Ian H. Sloan and Henryk Woźniakowski, Tractability of integration in non-periodic and periodic weighted tensor product Hilbert spaces, J. Complexity 18 (2002), no. 2, 479–499. Algorithms and complexity for continuous problems/Algorithms, computational complexity, and models of computation for nonlinear and multivariate problems (Dagstuhl/South Hadley, MA, 2000). MR 1919445, DOI 10.1006/jcom.2001.0626
Bibliographic Information
- P. Kritzer
- Affiliation: Johann Radon Institute for Computational and Applied Mathematics (RICAM), Austrian Academy of Sciences, Altenbergerstr. 69, 4040 Linz, Austria
- MR Author ID: 773334
- ORCID: 0000-0002-7919-7672
- Email: peter.kritzer@oeaw.ac.at
- F. Pillichshammer
- Affiliation: Institut für Finanzmathematik und Angewandte Zahlentheorie, Johannes Kepler Universität Linz, Altenbergerstr. 69, 4040 Linz, Austria
- MR Author ID: 661956
- ORCID: 0000-0001-6952-9218
- Email: friedrich.pillichshammer@jku.at
- G. W. Wasilkowski
- Affiliation: Computer Science Department, University of Kentucky, 301 David Marksbury Building, 329 Rose Street, Lexington, Kentucky 40506
- MR Author ID: 189251
- ORCID: 0000-0003-4727-7368
- Email: greg@cs.uky.edu
- Received by editor(s): January 16, 2020
- Received by editor(s) in revised form: August 4, 2020, and September 1, 2020
- Published electronically: January 11, 2021
- Additional Notes: The first author was supported by the Austrian Science Fund (FWF): Project F5506-N26, which is a part of the Special Research Program “Quasi-Monte Carlo Methods: Theory and Applications”.
The second author was supported by the Austrian Science Fund (FWF): Project F5509-N26, which is a part of the Special Research Program “Quasi-Monte Carlo Methods: Theory and Applications”. - © Copyright 2021 American Mathematical Society
- Journal: Math. Comp. 90 (2021), 1381-1406
- MSC (2020): Primary 65D30, 65C05, 11K38
- DOI: https://doi.org/10.1090/mcom/3598
- MathSciNet review: 4232228