The weighted star discrepancy of Korobov’s $p$-sets
HTML articles powered by AMS MathViewer
- by Josef Dick and Friedrich Pillichshammer PDF
- Proc. Amer. Math. Soc. 143 (2015), 5043-5057 Request permission
Abstract:
We analyze the weighted star discrepancy of so-called $p$-sets which go back to definitions due to Korobov in the 1950s and Hua and Wang in the 1970s. Since then, these sets have largely been ignored since a number of other constructions have been discovered which achieve a better convergence rate. However, it has recently been discovered that the $p$-sets perform well in terms of the dependence on the dimension.
We prove bounds on the weighted star discrepancy of the $p$-sets which hold for any choice of weights. For product weights, we give conditions under which the discrepancy bounds are independent of the dimension $s$. This implies strong polynomial tractability for the weighted star discrepancy. We also show that a very weak condition on the product weights suffices to achieve polynomial tractability.
References
- Christoph Aistleitner, Tractability results for the weighted star-discrepancy, J. Complexity 30 (2014), no. 4, 381–391. MR 3212778, DOI 10.1016/j.jco.2013.12.004
- Josef Dick, Numerical integration of Hölder continuous, absolutely convergent Fourier, Fourier cosine, and Walsh series, J. Approx. Theory 183 (2014), 14–30. MR 3209579, DOI 10.1016/j.jat.2014.03.015
- Josef Dick, Gunther Leobacher, and Friedrich Pillichshammer, Construction algorithms for digital nets with low weighted star discrepancy, SIAM J. Numer. Anal. 43 (2005), no. 1, 76–95. MR 2177135, DOI 10.1137/040604662
- Josef Dick, Harald Niederreiter, and Friedrich Pillichshammer, Weighted star discrepancy of digital nets in prime bases, Monte Carlo and quasi-Monte Carlo methods 2004, Springer, Berlin, 2006, pp. 77–96. MR 2208703, DOI 10.1007/3-540-31186-6_{6}
- 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, Ian H. Sloan, Xiaoqun Wang, and Henryk Woźniakowski, Liberating the weights, J. Complexity 20 (2004), no. 5, 593–623. MR 2086942, DOI 10.1016/j.jco.2003.06.002
- Benjamin Doerr, Michael Gnewuch, and Anand Srivastav, Bounds and constructions for the star-discrepancy via $\delta$-covers, J. Complexity 21 (2005), no. 5, 691–709. MR 2170868, DOI 10.1016/j.jco.2005.05.002
- Michael Drmota and Robert F. Tichy, Sequences, discrepancies and applications, Lecture Notes in Mathematics, vol. 1651, Springer-Verlag, Berlin, 1997. MR 1470456, DOI 10.1007/BFb0093404
- N. M. Korobov, Approximate calculation of repeated integrals by number-theoretical methods, Dokl. Akad. Nauk SSSR (N.S.) 115 (1957), 1062–1065 (Russian). MR 0098714
- N. M. Korobov, On number-theoretic methods in approximate analysis, Probl. Numer. Math. Comp. Techn. (Russian), Gosudarstv. Naučno-Tehn. Izdat. Mašinostr. Lit., Moscow, 1963, pp. 36–44 (Russian). MR 0189241
- L. Kuipers and H. Niederreiter, Uniform distribution of sequences, Pure and Applied Mathematics, Wiley-Interscience [John Wiley & Sons], New York-London-Sydney, 1974. MR 0419394
- 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
- Stefan Heinrich, Erich Novak, Grzegorz W. Wasilkowski, and Henryk Woźniakowski, The inverse of the star-discrepancy depends linearly on the dimension, Acta Arith. 96 (2001), no. 3, 279–302. MR 1814282, DOI 10.4064/aa96-3-7
- Aicke Hinrichs, Covering numbers, Vapnik-Červonenkis classes and bounds for the star-discrepancy, J. Complexity 20 (2004), no. 4, 477–483. MR 2068153, DOI 10.1016/j.jco.2004.01.001
- Aicke Hinrichs, Friedrich Pillichshammer, and Wolfgang Ch. Schmid, Tractability properties of the weighted star discrepancy, J. Complexity 24 (2008), no. 2, 134–143. MR 2400312, DOI 10.1016/j.jco.2007.08.002
- Loo Keng Hua and Yuan Wang, Applications of number theory to numerical analysis, Springer-Verlag, Berlin-New York; Kexue Chubanshe (Science Press), Beijing, 1981. Translated from the Chinese. MR 617192
- Rudolf Lidl and Harald Niederreiter, Finite fields, 2nd ed., Encyclopedia of Mathematics and its Applications, vol. 20, Cambridge University Press, Cambridge, 1997. With a foreword by P. M. Cohn. MR 1429394
- 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, When are integration and discrepancy tractable?, Foundations of computational mathematics (Oxford, 1999) London Math. Soc. Lecture Note Ser., vol. 284, Cambridge Univ. Press, Cambridge, 2001, pp. 211–266. MR 1836619
- 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
- Erich Novak and Henryk Woźniakowski, Tractability of multivariate problems. Volume III: Standard information for operators, EMS Tracts in Mathematics, vol. 18, European Mathematical Society (EMS), Zürich, 2012. MR 2987170, DOI 10.4171/116
- 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
- Xiaoqun Wang, A constructive approach to strong tractability using quasi-Monte Carlo algorithms, J. Complexity 18 (2002), no. 3, 683–701. MR 1928803, DOI 10.1006/jcom.2002.0641
- Xiaoqun Wang, Strong tractability of multivariate integration using quasi-Monte Carlo algorithms, Math. Comp. 72 (2003), no. 242, 823–838. MR 1954970, DOI 10.1090/S0025-5718-02-01440-0
- André Weil, On some exponential sums, Proc. Nat. Acad. Sci. U.S.A. 34 (1948), 204–207. MR 27006, DOI 10.1073/pnas.34.5.204
Additional Information
- Josef Dick
- Affiliation: School of Mathematics and Statistics, The University of New South Wales, Sydney, Australia
- Email: josef.dick@unsw.edu.au
- Friedrich Pillichshammer
- Affiliation: Institut für Analysis, Universität Linz, Altenbergerstraße 69, A-4040 Linz, Austria
- MR Author ID: 661956
- ORCID: 0000-0001-6952-9218
- Email: friedrich.pillichshammer@jku.at
- Received by editor(s): March 31, 2014
- Received by editor(s) in revised form: September 11, 2014
- Published electronically: May 7, 2015
- Additional Notes: The first author was supported by a QEII Fellowship of the Australian Research Council DP1097023.
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”. - Communicated by: Walter Van Assche
- © Copyright 2015 American Mathematical Society
- Journal: Proc. Amer. Math. Soc. 143 (2015), 5043-5057
- MSC (2010): Primary 11K38, 65C05
- DOI: https://doi.org/10.1090/proc/12636
- MathSciNet review: 3411125