# zbMATH — the first resource for mathematics

The Marcinkiewicz-type discretization theorems. (English) Zbl 1404.41012
Let $$\Omega$$ be a compact subset of $$\mathbb{R}^d,\, \mu$$ a probability measure on $$\Omega$$ and $$1\leq q<\infty.$$ One says that an $$N$$-dimensional subspace $$X_N$$ of $$L_q(\Omega,\mu)$$ satisfies a Marcinkiewicz type theorem if there exist a subset $$\{\xi^\nu: 1\leq\nu\leq m\}$$ of $$\Omega$$ and two constants $$C_1(d,q),C_2(d,q)>0$$ such that
$C_1(d,q)\|f\|^q_q\leq \frac1m\sum_{\nu=1}^m|f(\xi^\nu)|^q\leq C_2(d,q)\|f\|^q_q\,,(\ast)$ for all $$f\in X_N.$$ In the case of the uniform norm one asks that $C_1(d,q)\|f\|_\infty\leq\max_{1\leq \nu\leq m}|f(\xi^\nu)| \leq\|f\|_\infty\,,$ for all $$f\in X_N\subset C(\Omega).$$
As the author mention, such a result was obtained for the first time by J. Marcinkiewicz in the case of univariate trigonometric polynomials:
$C_1(q)\|f\|^q_q\leq \frac1m\sum_{\nu=1}^{2n+1}|f\big(2\pi\nu/(2n+1)\big)|^q\leq C_2(q)\|f\|^q_q\,.$ The author considers also some variants of Marcinkiewicz problem:
$$\bullet$$ the Marcinkiewicz problem with weights (with $$\sum_{\nu=1}^m\lambda_\nu|f(\xi^\nu)|^q$$ in $$(*)$$);
$$\bullet$$ the Marcinkiewicz problem with $$\varepsilon$$ (when $$C_1(d,q)=1-\varepsilon$$ and $$C_2(d,q)=1+\varepsilon$$).
The aim of the paper is “to present here a new technique, which works well for discretization of the integral norm. It is a combination of probabilistic technique, based on chaining, and results on the entropy numbers in the uniform norm.” (quoted from abstract).

##### MSC:
 41A65 Abstract approximation theory (approximation in normed linear spaces and other abstract spaces) 46B15 Summability and bases; functional analytic aspects of frames in Banach and Hilbert spaces 41A46 Approximation by arbitrary nonlinear expressions; widths and entropy
##### Keywords:
discretization; chaining; sparse approximation; entropy
Full Text:
##### References:
 [1] Batson, J; Spielman, DA; Srivastava, N, Twice-Ramanujan sparsifiers, SIAM J. Comput., 41, 1704-1721, (2012) · Zbl 1260.05092 [2] Bourgain, J; Lindenstrauss, J; Milman, V, Approximation of zonoids by zonotopes, Acta Math., 162, 73-141, (1989) · Zbl 0682.46008 [3] Dũng, D., Temlyakov, V.N., Ullrich, T.: Hyperbolic cross approximation (2016). arXiv:1601.03978v2 [math.NA] [4] Donahue, M; Gurvits, L; Darken, C; Sontag, E, Rate of convex approximation in non-Hilbert spaces, Constr. Approx., 13, 187-220, (1997) · Zbl 0876.41016 [5] Kashin, BS, Lunin’s method for selecting large submatrices with small norm, Matem. Sb., 206, 95-102, (2015) · Zbl 1336.46014 [6] Kashin, BS; Temlyakov, VN, On a norm and related applications, Mat. Zametki, 64, 637-640, (1998) · Zbl 0955.42002 [7] Kashin, B.S., Temlyakov, V.N.: On a norm and approximation characteristics of classes of functions of several variables. Metric theory of functions and related problems in analysis, Izd. Nauchno-Issled. Aktuarno-Finans. Tsentra (AFTs), Moscow, pp. 69-99 (1999) [8] Kashin, BS; Temlyakov, VN, The volume estimates and their applications, East J. Approx., 9, 469-485, (2003) · Zbl 1111.41019 [9] Marcus, A; Spielman, DA; Srivastava, N, Interlacing families II: mixed characteristic polynomials and the kadison-Singer problem, Ann. Math., 182, 327-350, (2015) · Zbl 1332.46056 [10] Nitzan, S; Olevskii, A; Ulanovskii, A, Exponential frames on unbounded sets, Proc. Am. Math. Soc., 144, 109-118, (2016) · Zbl 1327.42035 [11] Rudelson, M, Almost orthogonal submatrices of an orthogonal matrix, Izr. J. Math., 111, 143-155, (1999) · Zbl 0958.15019 [12] Temlyakov, VN, Weak greedy algorithms, Adv. Comput. Math., 12, 213-227, (2000) · Zbl 0964.65009 [13] Temlyakov, VN, Greedy algorithms in Banach spaces, Adv. Comput. Math., 14, 277-292, (2001) · Zbl 0988.41022 [14] Temlyakov, VN, Greedy-type approximation in Banach spaces and applications, Constr. Approx., 21, 257-292, (2005) · Zbl 1070.41018 [15] Temlyakov, V.N.: Greedy Approximation. Cambridge University Press, Cambridge (2011) · Zbl 1279.41001 [16] Temlyakov, VN, An inequality for the entropy numbers and its application, J. Approx. Theory, 173, 110-121, (2013) · Zbl 1283.41021 [17] Temlyakov, V.N.: Incremental greedy algorithm and its applications in numerical integration. In: Springer Proceedings in Mathematics and Statistics, Monte Carlo and Quasi-Monte Carlo Methods, MCQMC, Leuven, Belgium, Apr 2014, pp. 557-570 (2014) · Zbl 1356.65088 [18] Temlyakov, V.N.: Constructive sparse trigonometric approximation and other problems for functions with mixed smoothness. Matem. Sb. 206, 131-160 (2015). arXiv:1412.8647v1 [math.NA] · Zbl 1362.41009 [19] Temlyakov, V.N.: Constructive sparse trigonometric approximation for functions with small mixed smoothness. Constr. Approx. 45, 467-495 (2017). arXiv:1503.0282v1 [math.NA] · Zbl 1373.42009 [20] Temlyakov, V.N.: On the entropy numbers of the mixed smoothness function classes. J. Approx. Theory 207, 26-56 (2017). arXiv:1602.08712v1 [math.NA] · Zbl 1366.41019 [21] Temlyakov, V.N.: The Marcinkewiecz-type discretization theorems for the hyperbolic cross polynomials. Jaen J. Approx. 9(1), 37-63 (2017). arXiv:1702.01617v2 [math.NA] [22] Tropp, JA, User-friendly tail bounds for sums of random matrices, Found. Comput. Math., 12, 389-434, (2012) · Zbl 1259.60008 [23] Zygmund, A.: Trigonometric Series. Cambridge University Press, Cambridge (1959) · Zbl 0085.05601
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.