On quasi-Monte Carlo methods in weighted ANOVA spaces

Kritzer, P.; Pillichshammer, F.; Wasilkowski, G.

doi:10.1090/mcom/3598

On quasi-Monte Carlo methods in weighted ANOVA spaces
HTML articles powered by AMS MathViewer

by P. Kritzer, F. Pillichshammer and G. W. Wasilkowski HTML | PDF

Math. Comp. 90 (2021), 1381-1406 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, 1973, pp. 129–199. MR 0357357
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, 1977, pp. 311–329. MR 0491574
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