Connections between numerical integration, discrepancy, dispersion, and universal discretization

Temlyakov, Vladimir

The SMAI Journal of computational mathematics, Tome 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.

Classification : 41A65, 42A10, 46B20
Mots clés : numerical integration, discrepancy, dispersion, discretization, greedy algorithm

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

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

[3] Bilyk, D. 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

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

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

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

[7] Bykovskii, V. A. 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] Corput, J. G. van der Verteilungsfunktionen.I, Proc. Akad. Wet. Amsterdam, Volume 38 (1935), pp. 813-821

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

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

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

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

[13] Frolov, K. K. 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 | Zbl

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

[15] Halász, G. 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

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

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

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

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

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

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

[22] Rudolf, D. 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 | DOI | MR | Zbl

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

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

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

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

[27] Temlyakov, V. N. 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

[28] Temlyakov, V. N. 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

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

[30] Temlyakov, V. N. 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

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

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

[33] Temlyakov, V. N. 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

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

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

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

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

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

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

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

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

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

[43] Ullrich, M. 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 | DOI | MR | Zbl

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

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

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

[47] van Aardenne-Ehrenfest, T. 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 | Zbl

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

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

[50] Zinterhof, P. Ü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 | Zbl