JOURNAL OF COMPUTATIONAL MATHEMATICS

Browse issues
Connections between numerical integration, discrepancy, dispersion, and universal discretization
Vladimir Temlyakov1
1 University of South Carolina, USA; Steklov Institute of Mathematics and Lomonosov Moscow State University, Russia.
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:
DOI: 10.5802/smai-jcm.58
Classification: 41A65, 42A10, 46B20
Keywords: numerical integration, discrepancy, dispersion, discretization, greedy algorithm

Vladimir Temlyakov 1

1 University of South Carolina, USA; Steklov Institute of Mathematics and Lomonosov Moscow State University, Russia.
License: CC-BY-NC-ND 4.0
Copyrights: The authors retain unrestricted copyrights and publishing rights 
@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},
     pages = {185--209},
     publisher = {Soci\'et\'e de Math\'ematiques Appliqu\'ees et Industrielles},
     volume = {S5},
     year = {2019},
     doi = {10.5802/smai-jcm.58},
     language = {en},
     url = {https://smai-jcm.centre-mersenne.org/articles/10.5802/smai-jcm.58/}
}
TY  - JOUR
AU  - Vladimir Temlyakov
TI  - Connections between numerical integration, discrepancy, dispersion, and universal discretization
JO  - The SMAI Journal of computational mathematics
PY  - 2019
SP  - 185
EP  - 209
VL  - S5
PB  - Société de Mathématiques Appliquées et Industrielles
UR  - https://smai-jcm.centre-mersenne.org/articles/10.5802/smai-jcm.58/
DO  - 10.5802/smai-jcm.58
LA  - en
ID  - SMAI-JCM_2019__S5__185_0
ER  - 
%0 Journal Article
%A Vladimir Temlyakov
%T Connections between numerical integration, discrepancy, dispersion, and universal discretization
%J The SMAI Journal of computational mathematics
%D 2019
%P 185-209
%V S5
%I Société de Mathématiques Appliquées et Industrielles
%U https://smai-jcm.centre-mersenne.org/articles/10.5802/smai-jcm.58/
%R 10.5802/smai-jcm.58
%G en
%F SMAI-JCM_2019__S5__185_0
Vladimir Temlyakov. 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/articles/10.5802/smai-jcm.58/

[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 | DOI | MR | Zbl

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

[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

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

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

[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

[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 | DOI | MR | Zbl

[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 | Zbl

[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

[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 | DOI | MR | Zbl

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

[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 | DOI | MR | Zbl

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

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

[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 | DOI | MR | Zbl

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

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

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

[26] J. Sosnovec 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] 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

[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

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

[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

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

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

[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

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

[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 | DOI | Zbl

[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

[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 | DOI | MR

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

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

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

[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 | DOI | MR | Zbl

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

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

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

[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 | Zbl

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

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

[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 | Zbl

Cited by Sources: