# 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:
  Batson, J; Spielman, DA; Srivastava, N, Twice-Ramanujan sparsifiers, SIAM J. Comput., 41, 1704-1721, (2012) · Zbl 1260.05092  Bourgain, J; Lindenstrauss, J; Milman, V, Approximation of zonoids by zonotopes, Acta Math., 162, 73-141, (1989) · Zbl 0682.46008  Dũng, D., Temlyakov, V.N., Ullrich, T.: Hyperbolic cross approximation (2016). arXiv:1601.03978v2 [math.NA]  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  Kashin, BS, Lunin’s method for selecting large submatrices with small norm, Matem. Sb., 206, 95-102, (2015) · Zbl 1336.46014  Kashin, BS; Temlyakov, VN, On a norm and related applications, Mat. Zametki, 64, 637-640, (1998) · Zbl 0955.42002  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)  Kashin, BS; Temlyakov, VN, The volume estimates and their applications, East J. Approx., 9, 469-485, (2003) · Zbl 1111.41019  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  Nitzan, S; Olevskii, A; Ulanovskii, A, Exponential frames on unbounded sets, Proc. Am. Math. Soc., 144, 109-118, (2016) · Zbl 1327.42035  Rudelson, M, Almost orthogonal submatrices of an orthogonal matrix, Izr. J. Math., 111, 143-155, (1999) · Zbl 0958.15019  Temlyakov, VN, Weak greedy algorithms, Adv. Comput. Math., 12, 213-227, (2000) · Zbl 0964.65009  Temlyakov, VN, Greedy algorithms in Banach spaces, Adv. Comput. Math., 14, 277-292, (2001) · Zbl 0988.41022  Temlyakov, VN, Greedy-type approximation in Banach spaces and applications, Constr. Approx., 21, 257-292, (2005) · Zbl 1070.41018  Temlyakov, V.N.: Greedy Approximation. Cambridge University Press, Cambridge (2011) · Zbl 1279.41001  Temlyakov, VN, An inequality for the entropy numbers and its application, J. Approx. Theory, 173, 110-121, (2013) · Zbl 1283.41021  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  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  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  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  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]  Tropp, JA, User-friendly tail bounds for sums of random matrices, Found. Comput. Math., 12, 389-434, (2012) · Zbl 1259.60008  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.