Geodesic
Integral norm discretization and related problems
Trudy Matematicheskogo Instituta imeni V.A. Steklova, Tome 74 (2019) no. 4, pp. 579-630
Cet article a éte moissonné depuis la source Math-Net.Ru

Voir la notice de l'article

The problem is discussed of replacing an integral norm with respect to a given probability measure by the corresponding integral norm with respect to a discrete measure. This problem is investigated for elements of finite-dimensional spaces. Also, discretization of the uniform norm of functions in a given finite-dimensional subspace of continuous functions is studied. Special attention is given to the case of multivariate trigonometric polynomials with frequencies (harmonics) in a finite set with fixed cardinality. Both new results and a survey of known results are presented. Bibliography: 47 titles.
Keywords: trigonometric polynomials, discretization, Marcinkiewicz-type theorems. 
@article{RM_2019_74_4_a0,
     author = {F. Dai and A. Prymak and V. N. Temlyakov and S. Yu. Tikhonov},
     title = {Integral norm discretization and related problems},
     journal = {Trudy Matematicheskogo Instituta imeni V.A. Steklova},
     pages = {579--630},
     year = {2019},
     volume = {74},
     number = {4},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/RM_2019_74_4_a0/}
}
TY  - JOUR
AU  - F. Dai
AU  - A. Prymak
AU  - V. N. Temlyakov
AU  - S. Yu. Tikhonov
TI  - Integral norm discretization and related problems
JO  - Trudy Matematicheskogo Instituta imeni V.A. Steklova
PY  - 2019
SP  - 579
EP  - 630
VL  - 74
IS  - 4
UR  - http://geodesic.mathdoc.fr/item/RM_2019_74_4_a0/
LA  - en
ID  - RM_2019_74_4_a0
ER  - 
%0 Journal Article
%A F. Dai
%A A. Prymak
%A V. N. Temlyakov
%A S. Yu. Tikhonov
%T Integral norm discretization and related problems
%J Trudy Matematicheskogo Instituta imeni V.A. Steklova
%D 2019
%P 579-630
%V 74
%N 4
%U http://geodesic.mathdoc.fr/item/RM_2019_74_4_a0/
%G en
%F RM_2019_74_4_a0
F. Dai; A. Prymak; V. N. Temlyakov; S. Yu. Tikhonov. Integral norm discretization and related problems. Trudy Matematicheskogo Instituta imeni V.A. Steklova, Tome 74 (2019) no. 4, pp. 579-630. http://geodesic.mathdoc.fr/item/RM_2019_74_4_a0/

[1] C. Aistleitner, A. Hinrichs, D. Rudolf, “On the size of the largest empty box amidst a point set”, Discrete Appl. Math., 230 (2017), 146–150 ; (2017 (v1 – 2015)), 7 pp., arXiv: 1507.02067v3 | DOI | MR | Zbl

[2] R. Askey, Orthogonal polynomials and special functions, CBMS-NSF Regional Conf. Ser. in Appl. Math., 21, Society for Industrial and Applied Mathematics (SIAM), Philadelphia, PA, 1975, vii+110 pp. | DOI | MR | Zbl

[3] J. Batson, D. A. Spielman, N. Srivastava, “Twice-Ramanujan sparsifiers”, SIAM J. Comput., 41:6 (2012), 1704–1721 | DOI | MR | Zbl

[4] J. Bourgain, J. Lindenstrauss, V. Milman, “Approximation of zonoids by zonotopes”, Acta Math., 162:1-2 (1989), 73–141 | DOI | MR | Zbl

[5] A. Dumitrescu, M. Jiang, “On the largest empty axis-parallel box amidst $n$ points”, Algorithmica, 66:2 (2013), 225–248 | DOI | MR | Zbl

[6] D. Dũng, V. Temlyakov, T. Ullrich, Hyperbolic cross approximation, Adv. Courses Math. CRM Barcelona, Birkhäuser/Springer, Cham, 2018, xi+218 pp. ; 2016, 182 pp., arXiv: 1601.03978v2 | DOI | MR | Zbl

[7] E. Gine, J. Zinn, “Some limit theorems for empirical processes”, Ann. Probab., 12:4 (1984), 929–989 | DOI | MR | Zbl

[8] E. D. Gluskin, “Extremal properties of orthogonal parallelepipeds and their applications to the geometry of Banach spaces”, Math. USSR-Sb., 64:1 (1989), 85–96 | DOI | MR | Zbl

[9] B. S. Kashin, “On certain properties of the space of trigonometric polynomials with uniform norm”, Proc. Steklov Inst. Math., 145 (1981), 121–127 | MR | Zbl

[10] B. S. Kashin, “Lunin's method for selecting large submatrices with small norm”, Sb. Math., 206:7 (2015), 980–987 | DOI | DOI | MR | Zbl

[11] B. S. Kashin, V. N. Temlyakov, “On a certain norm and related applications”, Math. Notes, 64:4 (1998), 551–554 | DOI | DOI | MR | Zbl

[12] B. S. Kashin, V. N. Temlyakov, “Ob odnoi norme i approksimatsionnykh kharakteristikakh klassov funktsii mnogikh peremennykh”, Metricheskaya teoriya funktsii i smezhnye voprosy analiza, AFTs, M., 1999, 69–99 | MR

[13] B. S. Kashin, V. N. Temlyakov, “The volume estimates and their applications”, East J. Approx., 9:4 (2003), 469–485 | MR | Zbl

[14] B. S. Kashin, V. N. Temlyakov, “Observations on discretization of trigonometric polynomials with given spectrum”, Russian Math. Surveys, 73:6 (2018), 1128–1130 | DOI | DOI | MR | Zbl

[15] B. S. Kashin, V. N. Temlyakov, Some remarks on discretization of the uniform norm, manuscript, 2018

[16] S. V. Konyagin, V. N. Temlyakov, “The entropy in learning theory. Error estimates”, Constr. Approx., 25:1 (2007), 1–27 | DOI | MR | Zbl

[17] V. I. Krylov, Approximate calculation of integrals, The Macmillan Co., New York–London, 1962, x+357 pp. | MR | MR | Zbl

[18] A. W. Marcus, D. A. Spielman, N. Srivastava, “Interlacing families II: Mixed characteristic polynomials and the Kadison–Singer problem”, Ann. of Math. (2), 182:1 (2015), 327–350 | DOI | MR | Zbl

[19] J. Matoušek, Geometric discrepancy. An illustrated guide, Algorithms Combin., 18, Springer-Verlag, Berlin, 1999, xii+288 pp. | DOI | MR | Zbl

[20] H. Niederreiter, C. Xing, “Low-discrepancy sequences and global function fields with many rational places”, Finite Fields Appl., 2:3 (1996), 241–273 | DOI | MR | Zbl

[21] S. Nitzan, A. Olevskii, A. Ulanovskii, “Exponential frames on unbounded sets”, Proc. Amer. Math. Soc., 144:1 (2016), 109–118 | DOI | MR | Zbl

[22] E. Nursultanov, S. Tikhonov, “A sharp Remez inequality for trigonometric polynomials”, Constr. Approx., 38:1 (2013), 101–132 | DOI | MR | Zbl

[23] M. Putinar, “A note on Tchakaloff's theorem”, Proc. Amer. Math. Soc., 125:8 (1997), 2409–2414 | DOI | MR | Zbl

[24] R. T. Rockafellar, Convex analysis, Princeton Math. Ser., 28, Princeton Univ. Press, Princeton, NJ, 1970, xviii+451 pp. | MR | Zbl | Zbl

[25] G. Rote, R. F. Tichy, “Quasi-Monte-Carlo methods and the dispersion of point sequences”, Math. Comput. Modelling, 23:8-9 (1996), 9–23 | DOI | MR | Zbl

[26] M. Rudelson, “Almost orthogonal submatrices of an orthogonal matrix”, Izrael J. Math., 111 (1999), 143–155 | DOI | MR | Zbl

[27] I. Z. Ruzsa, “Solving a linear equation in a set of integers. I”, Acta Arith., 65:3 (1993), 259–282 | DOI | MR | Zbl

[28] I. Z. Ruzsa, “An infinite Sidon sequence”, J. Number Theory, 68:1 (1998), 63–71 | DOI | MR | Zbl

[29] M. Talagrand, The generic chaining. Upper and lower bounds of stochastic processes, Springer Monogr. Math., Springer-Verlag, Berlin, 2005, viii+222 pp. | DOI | MR | Zbl

[30] V. N. Temlyakov, “Approximation of functions with bounded mixed derivative”, Proc. Steklov Inst. Math., 178 (1989), 1–121 | MR | Zbl

[31] V. N. Temlyakov, “O vosstanovlenii periodicheskikh funktsii neskolkikh peremennykh po znacheniyam v uzlakh teoretikochislovykh setok”, Anal. Math., 12:4 (1986), 287–305 | DOI | MR | Zbl

[32] V. N. Temlyakov, “Approximation by elements of a finite-dimensional subspace of functions from various Sobolev or Nikol'skii spaces”, Math. Notes, 43:6 (1988), 444–454 | DOI | MR | Zbl

[33] V. N. Temlyakov, “Estimates of the asymptotic characteristics of classes of functions with bounded mixed derivative or difference”, Proc. Steklov Inst. Math., 189 (1990), 161–197 | MR | Zbl

[34] V. N. Temlyakov, “Bilinear approximation and related questions”, Proc. Steklov Inst. Math., 194 (1993), 245–265 | MR | Zbl

[35] V. N. Temlyakov, Approximation of periodic functions, Comput. Math. Anal. Ser., Nova Sci. Publ., Commack, NY, 1993, x+419 pp. | MR | Zbl

[36] V. N. Temlyakov, “On approximate recovery of functions with bounded mixed derivative”, J. Complexity, 9:1 (1993), 41–59 | DOI | MR | Zbl

[37] V. Temlyakov, Greedy approximation, Cambridge Monogr. Appl. Comput. Math., 20, Cambridge Univ. Press, Cambridge, 2011, xiv+418 pp. | DOI | MR | Zbl

[38] V. Temlyakov, “On the entropy numbers of the mixed smoothness function classes”, J. Approx. Theory, 217 (2017), 26–56 ; (2016), 41 pp., arXiv: 1602.08712v1 | DOI | MR | Zbl

[39] V. N. Temlyakov, “The Marcinkiewicz-type discretization theorems for the hyperbolic cross polynomials”, Jaen J. Approx., 9:1 (2017), 37–63 | MR

[40] V. N. Temlyakov, “The Marcinkiewicz-type discretization theorems”, Constr. Approx., 48:2 (2018), 337–369 ; (2017), 35 pp., arXiv: 1703.03743v1 | DOI | MR | Zbl

[41] V. N. Temlyakov, “Universal discretization”, J. Complexity, 47 (2018), 97–109 ; (2017), 18 pp., arXiv: 1708.08544v1 | DOI | MR | Zbl

[42] V. Temlyakov, Multivariate approximation, Cambridge Monogr. Appl. Comput. Math., 32, Cambridge Univ. Press, Cambridge, 2018, xvi+534 pp. | DOI | MR | Zbl

[43] V. Temlyakov, S. Tikhonov, “Remez-type and Nikol'skii-type inequalities: general relations and the hyperbolic cross polynomials”, Constr. Approx., 46:3 (2017), 593–615 | DOI | MR | Zbl

[44] J. A. Tropp, “User-friendly tail bounds for sums of random matrices”, Found. Comput. Math., 12:4 (2012), 389–434 | DOI | MR | Zbl

[45] M. W. Wilson, “Uniform approximation of nonnegative continuous linear functionals”, J. Approx. Theory, 2:3 (1969), 241–248 | DOI | MR | Zbl

[46] H. Woźniakowski, “A survey of information-based complexity”, J. Complexity, 1:1 (1985), 11–44 | DOI | MR | Zbl

[47] A. Zygmund, Trigonometric series, v. I, II, 2nd ed., Cambridge Univ. Press, New York, 1959, xii+383 pp., vii+354 pp. | MR | MR | Zbl | Zbl