Connections between numerical integration, discrepancy, dispersion, and universal discretization
The SMAI journal of computational mathematics, Volume S5 (2019) , pp. 185-209.

The main goal of this paper is to provide a brief survey of recent results, which connect together results from different areas of research. It is well known that numerical integration of functions with mixed smoothness is closely related to the discrepancy theory. We discuss this connection in detail and provide a general view of this connection. It was established recently that the new concept of fixed volume discrepancy is very useful in proving the upper bounds for the dispersion. Also, it was understood recently that point sets with small dispersion are very good for the universal discretization of the uniform norm of trigonometric polynomials.

Published online: 2020-01-29
DOI: https://doi.org/10.5802/smai-jcm.58
Classification: 41A65,  42A10,  46B20
Keywords: numerical integration, discrepancy, dispersion, discretization, greedy algorithm
@article{SMAI-JCM_2019__S5__185_0,
     author = {Vladimir Temlyakov},
     title = {Connections between numerical integration, discrepancy, dispersion, and universal discretization},
     journal = {The SMAI journal of computational mathematics},
     publisher = {Soci\'et\'e de Math\'ematiques Appliqu\'ees et Industrielles},
     volume = {S5},
     year = {2019},
     pages = {185-209},
     doi = {10.5802/smai-jcm.58},
     language = {en},
     url = {smai-jcm.centre-mersenne.org/item/SMAI-JCM_2019__S5__185_0/}
}
Temlyakov, Vladimir. Connections between numerical integration, discrepancy, dispersion, and universal discretization. The SMAI journal of computational mathematics, Volume S5 (2019) , pp. 185-209. doi : 10.5802/smai-jcm.58. https://smai-jcm.centre-mersenne.org/item/SMAI-JCM_2019__S5__185_0/

[1] C. Aistleitner; A. Hinrichs; D. Rudolf On the size of the largest empty box amidst a point set, Discrete Appl. Math., Volume 230 (2017), pp. 146-150 | Article | MR 3684948 | Zbl 1373.51002

[2] J. Beck; W. Chen Irregularities of distribution, Cambridge University Press, 1987 | Zbl 0617.10039

[3] D. Bilyk Roth’s Orthogonal Function Method in Discrepancy Theory and Some New Connections, Panorama of Discrepancy Theory. Lecture Notes in Mathematics. 2017, Springer, 2014, pp. 71-158 | Zbl 1358.11083

[4] D. Bilyk; M. Lacey On the Small Ball Inequality in three dimensions, Duke Math. J., Volume 143 (2008), pp. 81-115 | Article | MR 2414745 | Zbl 1202.42007

[5] D. Bilyk; M. Lacey; A. Vagharshakyan On the Small Ball Inequality in all dimensions, J. Funct. Anal., Volume 254 (2008), pp. 2470-2502 | Article | MR 2409170 | Zbl 1214.42024

[6] P. Binev; A. Cohen; W. Dahmen; R. DeVore; V. N. Temlyakov Universal algorithms for learning theory. Part I: piecewise constant functions, J. Mach. Learn. Theory, Volume 6 (2005), pp. 1297-1321 | Zbl 1191.62068

[7] V. A. Bykovskii On the correct order of the error of optimal cubature formulas in spaces with dominating derivative, and on quadratic deviations of grids (1985) (to appear in Computing Center Far-Eastern Scientific Center, Akad. Sci. USSR, Vladivostok)

[8] J. G. van der Corput Verteilungsfunktionen.I, Proc. Akad. Wet. Amsterdam, Volume 38 (1935), pp. 813-821

[9] J. G. van der Corput Verteilungsfunktionen.II, Proc. Akad. Wet. Amsterdam, Volume 38 (1935), pp. 1058-1066

[10] F. Dai; A. Prymak; V. N. Temlyakov; S. Tikhonov Integral norm discretization and related problems (2018) (https://arxiv.org/abs/1807.01353v1)

[11] A. Dumitrescu; M. Jiang On the largest empty axis-parallel box amidst n points, Algorithmica, Volume 66 (2013), pp. 225-248 | Article | MR 3028639 | Zbl 1262.68186

[12] D. Dũng; V. N. Temlyakov; T. Ullrich Hyperbolic Cross Approximation (2016) (https://arxiv.org/abs/1601.03978v2)

[13] K. K. Frolov Upper bounds on the error of quadrature formulas on classes of functions, Dokl. Akad. Nauk SSSR, Volume 231 (1976), pp. 818-821 (English transl. in Sov. Math., Dokl. 17, 1976) | MR 427922 | Zbl 0358.65014

[14] L. Györfy; M. Kohler; A. Krzyzak; H. Walk A distribution-free theory of nonparametric regression, Springer, 2002

[15] G. Halász On Roth’s method in the theory of irregularities of points distributions, Recent Progress in Analytic Number Theory. Vol. 2, Academic Press Inc., 1981, pp. 79-94 | Zbl 0459.10032

[16] D. Krieg On the Dispersion of Sparse Grids (2017) (https://arxiv.org/abs/1709.02983)

[17] V. F. Lev The exact order of generalized diaphony and multidimensional numerical integration, J. Aust. Math. Soc., Ser. A, Volume 66 (1999), pp. 1-17 | Article | MR 1658707 | Zbl 0926.11054

[18] J. Matousek Geometric Discrepancy, Springer, 1999 | Zbl 0930.11060

[19] H. Niederreiter; C. Xing Low-discrepancy sequences and global function fields with many rational places, Finite Fields Appl., Volume 2 (1996), pp. 241-273 | Article | MR 1398076 | Zbl 0893.11029

[20] G. Rote; F. Tichy Quasi-Monte Carlo methods and the dispersion of point sequences, Math. Comput. Modelling, Volume 23 (1996), pp. 9-23 | Article | MR 1397998 | Zbl 0855.11041

[21] K. F. Roth On irregularities of distribution, Mathematica, Volume 1 (1954), pp. 73-79 | Zbl 0057.28604

[22] D. Rudolf An Upper Bound of the Minimal Dispersion via Delta Covers, Contemporary Computational Mathematics - A Celebration of the 80th Birthday of Ian Sloan, Springer, 2018, pp. 1099-1108 | Article | MR 3822275 | Zbl 1405.65025

[23] W. M. Schmidt Irregularities of distribution.VII, Acta Arith., Volume 21 (1972), pp. 45-50 | Article | MR 319933

[24] W. M. Schmidt Irregularities of distribution. X, Number Theory and Algebra, Academic Press Inc., 1977, pp. 311-329 | Zbl 0373.10020

[25] M. M. Skriganov Constructions of uniform distributions in terms of geometry of numbers, Algebra Anal., Volume 6 (1994), pp. 200-230 | Zbl 0840.11041

[26] J. Sosnovec A note on minimal dispersion of point sets in the unit cube, Eur. J. Comb., Volume 69 (2018), pp. 255-259 | Article | MR 3738155 | Zbl 1376.05028

[27] V. N. Temlyakov Approximation by elements of a finite-dimensional subspace of functions from various Sobolev or Nikol’skii spaces, Mat. Zametki, Volume 43 (1988), pp. 770-786 (English transl. in Math. Notes 43, 1988) | Zbl 0708.41018

[28] V. N. Temlyakov On a way of obtaining lower estimates for the errors of quadrature formulas, Mat. Sbornik, Volume 181 (1990), pp. 1403-1413 (English transl. in Math. USSR Sbornik 71, 1992) | Zbl 0758.41032

[29] V. N. Temlyakov Approximation of periodic functions, Computational Mathematics and Analysis Series, Nova Science Publishers, 1993 | Zbl 0899.41001

[30] V. N. Temlyakov On error estimates for cubature formulas, Tr. Mat. Inst. Steklova, Volume 207 (1994), pp. 326-338 (English transl. in Proc. Steklov Inst. Math. 6:299–309, 1995) | Zbl 1126.41303

[31] V. N. Temlyakov Cubature formulas, discrepancy, and nonlinear approximation, J. Complexity, Volume 19 (2003), pp. 352-391 | Article | MR 1984119 | Zbl 1031.41016

[32] V. N. Temlyakov Greedy-Type Approximation in Banach Spaces and Applications, Constr. Approx., Volume 21 (2005), pp. 257-292 | Article | MR 2107941 | Zbl 1070.41018

[33] V. N. Temlyakov On universal estimators in learning theory, Tr. Mat. Inst. Steklova, Volume 255 (2006), pp. 256-272 (English transl. in Proc. Steklov Inst. Math. 255:244–259, 2006) | Zbl 1351.68238

[34] V. N. Temlyakov Greedy approximation, Cambridge University Press, 2011 | Article | Zbl 1217.41020

[35] V. N. Temlyakov Incremental Greedy Algorithm and Its Applications in Numerical Integration, Monte Carlo and Quasi-Monte Carlo Methods, Springer, 2016, pp. 557-570 | Article | Zbl 1356.65088

[36] V. N. Temlyakov Fixed volume discrepancy in the periodic case (2017) (https://arxiv.org/abs/1710.11499v1)

[37] V. N. Temlyakov The Marcinkiewicz-type discretization theorems for the hyperbolic cross polynomials, Jaen J. Approx., Volume 9 (2017), pp. 37-63 | MR 3739140

[38] V. N. Temlyakov Remarks on numerical integration, discrepancy, and diaphony (2017) (https://arxiv.org/abs/1711.07017v1)

[39] V. N. Temlyakov The Marcinkiewicz-type discretization theorems, Constr. Approx., Volume 48 (2018), pp. 337-369 | Article | MR 3848042

[40] V. N. Temlyakov Multivariate approximation, Cambridge University Press, 2018 | Article | Zbl 06894860

[41] V. N. Temlyakov Universal discretization, J. Complexity, Volume 47 (2018), pp. 97-109 | Article | MR 3804602 | Zbl 06879964

[42] V. N. Temlyakov Smooth fixed volume discrepancy, dispersion, and related problems, J. Approximation Theory, Volume 237 (2019), pp. 113-134 | Article | MR 3868628 | Zbl 1410.65073

[43] M. Ullrich On "Upper error bounds for quadrature formulas on function classes" by K. K. Frolov, Monte Carlo and Quasi-Monte Carlo Methods, MCQMC, Springer, 2016, pp. 571-582 | Article | MR 3536683 | Zbl 1356.65089

[44] M. Ullrich A lower bound for the dispersion on the torus, Math. Comput. Simulation, Volume 143 (2018), pp. 186-190 | Article | MR 3698227

[45] M. Ullrich A note on the dispersion of admissible lattices, Discrete Appl. Math., Volume 257 (2019), pp. 385-387 | Article | MR 3926407 | Zbl 07034243

[46] M. Ullrich; J. Vybiral An upper bound on the minimal dispersion, J. Complexity, Volume 45 (2018), pp. 120-126 | Article | MR 3748601 | Zbl 1391.05070

[47] T. van Aardenne-Ehrenfest Proof of the impossibility of a just distribution of an infinite sequence of points over an interval, Proc. Akad. Wet. Amsterdam, Volume 48 (1945), pp. 266-271 | MR 15143 | Zbl 0060.13002

[48] T. van Aardenne-Ehrenfest On the impossibility of a just distribution, Proc. Akad. Wet. Amsterdam, Volume 52 (1949), pp. 734-739 | MR 32717 | Zbl 0035.32002

[49] H. Weyl Über die Gleichverteilung von Zahlen mod. Eins, Math. Ann., Volume 77 (1916), pp. 313-352 | Article | Zbl 46.0278.06

[50] P. Zinterhof Über einige Abschätzungen bei der Approximation von Funktionen mit Gleichverteilungsmethoden, Österr. Akad. Wiss., Math.-Naturw. Kl., S.-Ber., Abt. II, Volume 185 (1976), pp. 121-132 | MR 501760 | Zbl 0356.65007