A survey of sampling discretization of integral and uniform norms F. Dai, E. Kosov and V. Temlyakov Abstract This paper surveys recent developments in the sampling discretization of integral and uniform norms for functions in general finite-dimensional spaces. These results generalize the classical Marcinkiewicz-Zygmund inequalities for trigonometric and algebraic polynomials, which play a crucial role in Fourier analysis, interpolation, and approximation theory. We focus on the problem in the broad context of finite-dimensional subspaces, where norms defined by general probability measures are approximated by their discrete counterparts. The primary emphasis is on results closely related to the authors’ recent research. A key objective is to highlight the main ideas and techniques that form the foundation of the proofs in this area. This survey serves as a complement to three recently published survey papers on sampling discretization [ 15 , 31 , 44 ] . MSC: 41-02, 41A17, 41A10, 47-02 fourierlargesymbols147 Surveys in Approximation Theory Volume 6, 2026. pp. 1– A survey of sampling discretization of integral and uniform norms . © 2026 Surveys in Approximation Theory. ISSN 1555-578X All rights of reproduction in any form reserved. 1 Introduction The classical Marcinkiewicz inequality has the following original form (see [ 67 , Vol. II, p. 30] ): For any 10 be two given positive constants. The weighted Marcinkiewicz discretization of the L_{p} norm, 1\leq p<\infty , in the space X_{N} approximates the continuous L_{p}(\Omega,\mu) norm using a discrete signed measure supported on a finite subset \Omega_{m}=\{\xi^{1},\cdots,\xi^{m}\}\subset\Omega . Specifically, we require that the integral norm of every f\in X_{N} is bounded by a weighted discrete sum as follows: \displaystyle C_{1}\int_{\Omega}|f|^{p}\,d\mu\leq\sum_{j=1}^{m}\lambda_{j}|f(\xi^{j})|^{p}\leq C_{2}\int_{\Omega}|f|^{p}\,d\mu, (1.2) where the nodes \xi^{j}\in\Omega and the weights \lambda_{j}\in\mathbb{R} are independent of f\in X_{N} . If the estimate ( 1.2 ) holds for every function f in a subspace X_{N} , we say that X_{N} admits a weighted Marcinkiewicz-type discretization theorem with parameters p and m\in\mathbb{N} , and constants C_{1},C_{2} . Of particular interest are the following special cases of ( 1.2 ) where the weights are uniform, i.e., \lambda_{1}=\cdots=\lambda_{m}=\frac{1}{m} . (i) The Marcinkiewicz discretization problem. We say that X_{N} admits a Marcinkiewicz-type discretization theorem with parameters p and m\in\mathbb{N} , and constants C_{1},C_{2} if C_{1}\|f\|_{L_{p}(\Omega,\mu)}^{p}\leq\frac{1}{m}\sum_{j=1}^{m}|f(\xi^{j})|^{p}\leq C_{2}\|f\|_{L_{p}(\Omega,\mu)}^{p},\ \ \forall f\in X_{N}. (1.3) (ii) The Marcinkiewicz discretization problem with \epsilon\in(0,1) . We say that X_{N} admits a Marcinkiewicz-type discretization theorem with \epsilon and parameters p and m\in\mathbb{N} if (1-\epsilon)\|f\|_{L_{p}(\Omega,\mu)}^{p}\leq\frac{1}{m}\sum_{j=1}^{m}|f(\xi^{j})|^{p}\leq(1+\epsilon)\|f\|_{L_{p}(\Omega,\mu)}^{p},\ \ \forall f\in X_{N}. (1.4) The Bernstein discretization problem. The above definition can also be modified to include the case p=\infty , where we ask for C_{1}\|f\|_{L_{\infty}(\Omega)}\leq\max_{1\leq j\leq m}\left|f\left(\xi^{j}\right)\right|\leq\|f\|_{L_{\infty}(\Omega)},\ \ \forall f\in X_{N}. Universal Marcinkiewicz-type discretization problem. We can also consider a universal Marcinkiewicz-type discretization problem for a finite collection {\mathcal{X}}:=\{X_{k}\}_{k=1}^{L} of finite-dimensional spaces of functions on \Omega . Given 1\leq p<\infty , we say that a finite set \{\xi^{j}\}_{j=1}^{m}\subset\Omega provides universal discretization of the L_{p} norm for the collection {\mathcal{X}} with positive constants C_{1},C_{2} if for any f\in\bigcup_{k=1}^{L}X_{k} , C_{1}\|f\|_{L_{p}(\Omega,\mu)}^{p}\leq\frac{1}{m}\sum_{j=1}^{m}|f(\xi^{j})|^{p}\leq C_{2}\|f\|_{L_{p}(\Omega,\mu)}^{p}. Universal weighted discretization can be defined likewise. In the framework described above, X_{N} can be either a real or complex space. For Marcinkiewicz discretization with general constants C_{1},C_{2}>0 , results for complex spaces can be derived from real case by separating the real and imaginary parts. However, this reduction fails for the Marcinkiewicz discretization problem with \epsilon>0 , as the separation argument distorts the isometric constants (1\pm\epsilon) . For simplicity, we generally assume X_{N} is a real space unless stated otherwise. Nevertheless, most results extend to complex spaces using similar techniques. This survey presents tools and techniques for the Marcinkiewicz discretization problem on finite-dimensional spaces subject to certain additional conditions. Typically, two main types of conditions are used: (i) bounds on entropy numbers; and (ii) Nikol’skii-type inequalities. We postpone the definition and discussion of entropy numbers to Section 4 . In this section, we focus on Nikol’skii-type inequalities. These inequalities constitute the main assumption imposed on the subspaces in our setting and appear throughout the paper in the formulation of various results. Nikol’skii-type inequality. Given p\in[1,\infty) , an N -dimensional subspace X_{N}\subset L_{\infty}(\Omega) is said to satisfy the (p,\infty) -Nikol’skii inequality with constant M>0 if \|f\|_{L_{\infty}(\Omega)}\leq M\|f\|_{L_{p}(\Omega,\mu)},\ \ \forall f\in X_{N}, (1.5) in which case we write X_{N}\in\textnormal{NI}_{p,\infty}(M) . Of particular interest is the case of p=2 , where the exact constant M in ( 1.5 ) can be written explicitly as follows. Let \{\varphi_{j}(x)\}_{j=1}^{N} be an orthonormal basis of X_{N}\subset L_{2}(\Omega,\mu) . Then we have \sup_{f\in X_{N},\|f\|_{L_{2}(\Omega,\mu)}\leq 1}|f(x)|=\Bigl(\sum_{j=1}^{N}\varphi_{j}(x)^{2}\Bigr)^{1/2}=:\sqrt{\Phi(x)},\ \ \forall x\in\Omega, which implies X_{N}\in\textnormal{NI}_{2,\infty}(M)\iff\|\Phi\|_{L_{\infty}(\Omega)}\leq M^{2}. (1.6) The function \lambda(X_{N},\mu;x):=\frac{1}{\Phi(x)}, known as the Christoffel function of the space X_{N} , is independent of the selection of orthonormal basis of X_{N} . Finally, since \|f\|_{L_{2}(\Omega,\mu)}^{2}\leq\|f\|_{L_{p}(\Omega,\mu)}^{p}\,\|f\|_{L_{\infty}(\Omega)}^{2-p} for 1\leq p\leq 2 , the condition \|f\|_{L_{\infty}(\Omega)}\leq\sqrt{M}\,\|f\|_{{L_{2}(\Omega,\mu)}} implies \|f\|_{L_{2}(\Omega,\mu)}\leq M^{\frac{1}{p}-\frac{1}{2}}\|f\|_{L_{p}(\Omega,\mu)}\quad\text{and}\quad\|f\|_{L_{\infty}(\Omega)}\leq M^{1/p}\|f\|_{L_{p}(\Omega,\mu)}. (1.7) In terms of the Nikol’skii inequalities, this establishes the implication X_{N}\in\textnormal{NI}_{2,\infty}(\sqrt{M})\implies X_{N}\in\textnormal{NI}_{p,\infty}(M^{1/p})\ \ \text{for any $1\leq p\leq 2$}. (1.8) Notation. To conclude this section, we introduce some notation that will be used throughout this paper. Given a finite set of points \Omega_{m}=\{\xi^{1},\ldots,\xi^{m}\} , and 1\leq p\leq\infty , we denote by L_{p}(\Omega_{m}) the space of all functions on \Omega_{m} equipped with the norm \|f\|_{L_{p}(\Omega_{m})}:=\begin{cases}\bigl(\frac{1}{m}\sum\limits_{j=1}^{m}|f(\xi^{j})|^{p}\bigr)^{1/p},&\ \ \text{if $1\leq p<\infty$},\\[14.22636pt] \max\limits_{1\leq j\leq m}|f(\xi^{j})|,&\ \ \text{if $p=\infty$}.\end{cases} We identify vectors in \mathbb{R}^{m} with functions defined on the set \Omega_{m}:=\{1,\ldots,m\}. In this special case, we adopt the following conventions for vectors f\in\mathbb{R}^{m} . We denote the normalized norm \|f\|_{L_{p}(\Omega_{m})} by \|f\|_{L_{p}^{m}} and the unnormalized norm by \|f\|_{\ell_{p}^{m}}:=m^{1/p}\|f\|_{L_{p}^{m}}=\begin{cases}\bigl(\sum\limits_{j=1}^{m}|f(j)|^{p}\bigr)^{1/p},&\ \ \text{if $1\leq p<\infty$},\\[14.22636pt] \max\limits_{1\leq j\leq m}|f(j)|,&\ \ \text{if $p=\infty$}.\end{cases} Accordingly, we define the unit ball B_{\ell_{p}^{m}}:=\bigl\{f\in\mathbb{R}^{m}\colon\|f\|_{\ell_{p}^{m}}\leq 1\bigr\}. More generally, for a normed space (X,\|\cdot\|_{X}) , we define B_{X}:=\bigl\{f\in X\colon\|f\|_{X}\leq 1\bigr\}. We also denote the Euclidean norm of x\in\mathbb{R}^{m} as |x| . Unless otherwise stated, the symbols C,c,C_{1},c_{1},\ldots denote positive universal constants. Organization of the paper. The remainder of the paper is organized as follows. In Section 2, we discuss the close connections between the Marcinkiewicz discretization problem and several related areas, including embeddings of finite-dimensional subspaces, frames, spectral properties, and operator norms of submatrices of a given matrix. In Section 3, we survey recent results on Marcinkiewicz sampling discretization for L_{2} -norms, which is the most extensively studied case. In Section 4, we present one of the general technical approaches to the Marcinkiewicz sampling discretization of L_{p} -norms for all 1\leq p<\infty . It is stated in the form of the conditional sampling discretization theorem, which highlights the connection between the Marcinkiewicz discretization problem and entropy numbers of compact subsets of bounded functions under the uniform metric. We also outline the key ideas used in the proofs. In Section 5, we discuss universal discretization, and its connection with the Restricted Isometry Property, a fundamental concept in compressed sensing. Section 6 covers recent improvements in bounds for sampling discretization of integral norms, along with the main ideas behind their proofs. Finally, in Section 7, we briefly discuss some recent progress on sampling discretization in the uniform norm. 2 Connections with other areas The Marcinkiewicz discretization problem is closely connected to several other areas. In this section, we provide a brief overview of these interactions and reformulate the problem in different contexts. We refer to the survey paper [ 31 ] for a detailed discussion of these connections. First, there are deep results on embeddings of finite-dimensional subspaces of L_{p}(\Omega,\mu) into \ell_{p}^{N} , which are closely related to the sampling discretization of the L_{p} norms (see, for instance, [ 7 , 29 ] ). Techniques developed for these embedding problems have proven highly effective for sampling discretization (see [ 29 ] ). A detailed discussion of this connection is available in Section 4.2 of [ 31 ] . Second, there is a close connection between the Marcinkiewicz discretization of L_{p} -norms and the concept of (\Lambda,p) -frames (see Section 5 of [ 12 ] ). We recall the following definition from [ 12 , Definition 5.2] . Definition 2.1 ( [ 12 ] ) . Let \Lambda:=\{\lambda_{j}\}_{j=1}^{m}\subset\mathbb{R} and 1\leq p<\infty . A sequence \{\psi_{j}\}_{j=1}^{m} of functions in X_{N} is called a (\Lambda,p) -frame of X_{N} with positive constants A and B if for any f\in X_{N} we have A\|f\|_{L_{p}(\Omega,\mu)}^{p}\leq\sum_{j=1}^{m}\lambda_{j}|\langle f,\psi_{j}\rangle|^{p}\leq B\|f\|_{L_{p}(\Omega,\mu)}^{p}, where \langle\cdot,\cdot\rangle denotes the inner product of L_{2}(\Omega,\mu) . When \lambda_{1}=\ldots=\lambda_{m}=1 , a (\Lambda,p) -frame is called a p -frame (see [ 1 ] ). Let \mathcal{D}(X_{N},\cdot,\cdot) denote the reproducing kernel (Dirichlet kernel) of the space X_{N}\subset L_{2}(\Omega,\mu)\cap L_{p}(\Omega,\mu) ; namely, \mathcal{D}(X_{N},x,y):=\sum_{j=1}^{N}u_{j}(x){u_{j}(y)},\ \ x,y\in\Omega where \{u_{j}\}_{j=1}^{N} is an orthonormal basis (o.n.b.) of (X_{N},\|\cdot\|_{L_{2}(\Omega,\mu)}) . Note that \mathcal{D}(X_{N},\cdot,\cdot) is independent of the choice of the orthonormal basis. The Marcinkiewicz inequality ( 1.2 ) is equivalent to C_{1}\|f\|_{L_{p}(\Omega,\mu)}^{p}\leq\sum_{j=1}^{m}\lambda_{j}|\langle f,\mathcal{D}(X_{N},\xi^{j},\cdot)\rangle|^{p}\leq C_{2}\|f\|_{L_{p}(\Omega,\mu)}^{p},\ \ \forall f\in X_{N}. In other words, in terms of (\Lambda,p) -frames, X_{N} admits a weighted Marcinkiewicz-type discretization theorem of the form ( 1.2 ) with constants C_{1},C_{2}>0 if and only if there exist points \xi^{1},\ldots,\xi^{m}\in\Omega and weights \Lambda=\{\lambda_{j}\}_{j=1}^{m}\subset\mathbb{R} such that the sequence \{\mathcal{D}(X_{N},\xi^{j},\cdot)\}_{j=1}^{m} forms a (\Lambda,p) -frame of X_{N} with constants C_{1},C_{2}>0 . Third, there is a probabilistic approach to the Marcinkiewicz discretization problem with \epsilon\in(0,1) . It aims to establish that for IID random points \xi^{1},\ldots,\xi^{m} drawn from \mu on \Omega , and 1\leq p<\infty , the inequality \sup_{f\in X_{N}^{p}}\Bigl|\frac{1}{m}\sum_{j=1}^{m}|f(\xi^{j})|^{p}-\int_{\Omega}|f|^{p}\,d\mu\Bigr|<\epsilon (2.1) holds with high probability, which, in particular, implies that X_{N} admits a Marcinkiewicz-type discretization theorem of the form ( 1.4 ). This approach connects to moment estimates of random vectors in probability. Let \xi be a random point drawn from \mu . Given a basis \{u_{k}\}_{k=1}^{N} of X_{N} , consider the vector-valued function \mathbf{u}=(u_{1},\ldots,u_{N}) on \Omega , and the random vector \boldsymbol{\eta}=\mathbf{u}(\xi) . Let \boldsymbol{\eta}^{j}=\mathbf{u}(\xi^{j}) , j=1,\ldots,m be independent copies of \boldsymbol{\eta} . Since each function f\in X_{N} has a unique representation f=\langle\mathbf{y},\mathbf{u}\rangle with \mathbf{y}=(y_{1},\ldots,y_{N})\in\mathbb{R}^{N} , the inequality ( 2.1 ) above is equivalent to \sup_{\mathbf{y}\in K}\Bigl|\frac{1}{m}\sum_{j=1}^{m}|\langle\mathbf{y},\boldsymbol{\eta}^{j}\rangle|^{p}-\mathbb{E}|\langle\mathbf{y},\boldsymbol{\eta}\rangle|^{p}\Bigr|<\epsilon, (2.2) where K:=\{\mathbf{y}\in\mathbb{R}^{N}:\ \mathbb{E}|\langle\mathbf{y},\mathbf{u}\rangle|^{p}\leq 1\} is a symmetric convex set in \mathbb{R}^{N} and \langle\mathbf{x},\mathbf{y}\rangle denotes the dot product \sum_{j=1}^{N}x_{j}y_{j} of \mathbf{x},\mathbf{y}\in\mathbb{R}^{N} . Thus, the probabilistic approach to the Marcinkiewicz discretization problem asks: How many independent copies of a random vector \boldsymbol{\eta} are needed to ensure that ( 2.2 ) holds with high probability? Fourth, the Marcinkiewicz discretization in finite-dimensional spaces relates to the spectral properties and operator norms of submatrices of a given matrix. It can be reduced to a corresponding matrix problem. As above, we fix a basis \{u_{k}\}_{k=1}^{N} of X_{N} , and define the vector-valued function \mathbf{u}=(u_{1},\ldots,u_{N}) on \Omega . Given a set \boldsymbol{\xi}=\{\xi^{1},\xi^{2},\ldots,\xi^{m}\} of distinct points in \Omega , consider the m\times N matrix \boldsymbol{\Phi}(\boldsymbol{\xi}):=\begin{bmatrix}\mathbf{u}(\xi^{1})\\ \mathbf{u}(\xi^{2})\\ \vdots\\ \mathbf{u}(\xi^{m})\end{bmatrix}=\begin{bmatrix}u_{1}(\xi^{1})&u_{2}(\xi^{1})&\cdots&u_{N}(\xi^{1})\\ u_{1}(\xi^{2})&u_{2}(\xi^{2})&\cdots&u_{N}(\xi^{2})\\ \vdots&\vdots&\vdots&\vdots\\ u_{1}(\xi^{m})&u_{2}(\xi^{m})&\cdots&u_{N}(\xi^{m})\end{bmatrix}. Given 1\leq p\leq\infty , define the following norm on \mathbb{R}^{N} : \|\mathbf{y}\|_{L_{p}}=\|\langle\mathbf{y},\mathbf{u}\rangle\|_{L_{p}(\Omega,\mu)},\ \ \mathbf{y}=(y_{1},\cdots,y_{N})\in\mathbb{R}^{N}. The Marcinkiewicz inequality ( 1.3 ) can then be reformulated as C_{1}\|\mathbf{y}\|_{L_{p}}\leq\bigl\|\boldsymbol{\Phi}(\boldsymbol{\xi})\mathbf{y}\bigr\|_{L_{p}^{m}}\leq C_{2}\|\mathbf{y}\|_{L_{p}},\ \ \forall\mathbf{y}\in\mathbb{R}^{N}. If p=2 and \{u_{1},\ldots,u_{N}\} is an orthonormal basis of (X_{N},\|\cdot\|_{L_{2}(\Omega,\mu)}) , this is equivalent to C_{1}\|\mathbf{y}\|_{\ell_{2}^{m}}\leq\bigl\|\boldsymbol{\Phi}(\boldsymbol{\xi})\mathbf{y}\bigr\|_{L_{2}^{m}}\leq C_{2}\|\mathbf{y}\|_{\ell_{2}^{m}},\ \ \forall\mathbf{y}\in\mathbb{R}^{N}, which can be reformulated in terms of the spectrum of the sampling matrix \boldsymbol{\Phi}(\boldsymbol{\xi}) . Specifically, this translates into the following estimates for the maximum and minimum singular values: \sigma_{\max}(\boldsymbol{\Phi}(\boldsymbol{\xi}))\leq C_{2}\sqrt{m}\ \ \text{and}\ \ \sigma_{\min}(\boldsymbol{\Phi}(\boldsymbol{\xi}))\geq C_{1}\sqrt{m}. If \Omega=\Omega_{M}=\{x_{1},\ldots,x_{M}\} is a finite set, then the vector-valued function \mathbf{u} can be represented as a matrix with M rows and N columns: \boldsymbol{\Phi}:=\begin{bmatrix}\mathbf{u}(x_{1})\\ \mathbf{u}(x_{2})\\ \vdots\\ \mathbf{u}(x_{M})\end{bmatrix}=\begin{bmatrix}u_{1}(x_{1})&u_{2}(x_{1})&\cdots&u_{N}(x_{1})\\ u_{1}(x_{2})&u_{2}(x_{2})&\cdots&u_{N}(x_{2})\\ \vdots&\vdots&\vdots&\vdots\\ u_{1}(x_{M})&u_{2}(x_{M})&\cdots&u_{N}(x_{M})\end{bmatrix}. In this case, we are looking for an m\times N submatrix \boldsymbol{\Phi}(\boldsymbol{\xi}) of the full matrix \boldsymbol{\Phi} such that for each \mathbf{y}\in\mathbb{R}^{N} , C_{1}\|\boldsymbol{\Phi}\mathbf{y}\|_{L_{p}(\Omega_{M})}^{p}\leq\|\boldsymbol{\Phi}(\boldsymbol{\xi})\mathbf{y}\|_{L_{p}^{m}}^{p}\leq C_{2}\|\boldsymbol{\Phi}\mathbf{y}\|_{L_{p}(\Omega_{M})}^{p}. Finally, the universal Marcinkiewicz-type discretization problem can alternatively be reformulated in terms of certain properties of matrices. In particular, the universal discretization of the L_{2} norm is closely linked with the concept of the Restricted Isometry Property (RIP), which plays significant roles in compressed sensing. A detailed discussion of this connection will be presented in Section 5 of this paper. 3 Marcinkiewicz discretization of L_{2} norms In this section, we survey some known results on the Marcinkiewicz sampling discretization of the L_{2} -norms, which is the most studied case. Let X_{N} be an N -dimensional subspace of L_{2}(\Omega,\mu) . For simplicity, we assume all functions in X_{N} are real valued. Our goal is to discretize the L_{2} -norm in X_{N} via a finite discrete sum: (1-\epsilon)\int_{\Omega}|f|^{2}\,d\mu\leq\sum_{j=1}^{m}\lambda_{j}|f(\xi^{j})|^{2}\leq(1+\epsilon)\int_{\Omega}|f|^{2}\,d\mu,\ \ \forall f\in X_{N}, (3.1) where \xi^{j}\in\Omega , \lambda_{j}\geq 0 , j=1,2,\ldots,m , and \epsilon\in(0,1) . 3.1 Characterization of ( 3.1 ) via spectral norms The discretization ( 3.1 ) of the L_{2} -norms can be equivalently formulated using spectral norms of certain symmetric matrices. To this end, we first recall some useful results from matrix analysis. Let A be an N\times N real symmetric matrix. By the spectral theorem, one can diagonalize A using a sequence of N real eigenvalues, \lambda_{1}(A)\geq\lambda_{2}(A)\geq\ldots\geq\lambda_{N}(A), and an orthonormal basis of eigenvectors u_{1}(A),\ldots,u_{N}(A)\in\mathbb{R}^{N} such that A\big(u_{i}(A)\big)=\lambda_{i}(A)u_{i}(A),\ \ \ i=1,2,\ldots,N. Let \lambda_{\max}(A):=\lambda_{1}(A) and \lambda_{\min}(A):=\lambda_{N}(A) . Then we have \lambda_{\max}(A)=\max_{x\in\mathbb{S}^{N-1}}\langle Ax,x\rangle\ \ \ \text{and}\ \ \lambda_{\min}(A)=\min_{x\in\mathbb{S}^{N-1}}\langle Ax,x\rangle, (3.2) where \langle\cdot,\cdot\rangle denotes the dot product in \mathbb{R}^{N} . In general, the Courant-Fischer min-max theorem asserts that for each 1\leq k\leq N , \lambda_{k}(A)=\max_{\dim V=k}\ \ \min_{x\in V,|x|=1}\langle Ax,x\rangle and \lambda_{k}(A)=\min_{\dim V=N-k+1}\ \ \max_{x\in V,|x|=1}\langle Ax,x\rangle, where V ranges over all subspaces of \mathbb{R}^{N} with the indicated dimension. If A is positive definite, \lambda_{\max}(A) is the spectral norm of A , which coincides with the operator norm \|A\| of A : \|A\|:=\max_{x\in\mathbb{S}^{N-1}}|Ax|. For a general symmetric matrix, we have \|A\|=\max_{x\in\mathbb{S}^{N-1}}|\langle Ax,x\rangle|=\max\{|\lambda_{\max}(A)|,|\lambda_{\min}(A)|\}. Now we give an alternative formulation of ( 3.1 ) using spectral norms. Let \{u_{1},\ldots,u_{N}\} be an orthonormal basis of X_{N}\subset L_{2}(\Omega,\mu) , and consider the vector-valued function \mathbf{u}(\xi):=(u_{1}(\xi),\ldots,u_{N}(\xi)),\ \ \xi\in\Omega. Define \mathbf{G}(\xi):=\mathbf{u}(\xi)\otimes\mathbf{u}(\xi)=\Bigl[u_{i}(\xi)u_{j}(\xi)\Bigr]_{1\leq i,j\leq N}\in\mathbb{R}^{N\times N},\ \ \xi\in\Omega. Then for each f=\sum_{j=1}^{N}a_{j}u_{j}=\langle\mathbf{u},\mathbf{a}\rangle\in X_{N} with \mathbf{a}=(a_{1},\ldots,a_{N})^{T}\in\mathbb{R}^{N} , we have \sum_{j=1}^{m}\lambda_{j}|f(\xi^{j})|^{2}-\|f\|_{L^{2}(\mu)}^{2}=\mathbf{a}^{T}\Bigl(\sum_{j=1}^{m}\lambda_{j}\mathbf{G}(\xi^{j})-I\Bigr)\mathbf{a}. Here we treat \mathbf{a} as a column-vector and \mathbf{u}(x) as a row-vector. This together with ( 3.2 ) yields the following alternative formulation of ( 3.1 ). Lemma 3.1 . Let \xi^{1},\ldots,\xi^{m}\in\Omega , \lambda_{1},\ldots,\lambda_{m}\in\mathbb{R} and \epsilon\in(0,1) . Then X_{N} admits a Marcinkiewicz-type discretization theorem of the form ( 3.1 ) if and only if \Bigl\|I-\sum_{j=1}^{m}\lambda_{j}\mathbf{G}(\xi^{j})\Bigr\|\leq\epsilon, where I denotes the N\times N identity matrix, and \|\cdot\| denotes the spectral norm. Lemma 3.1 establishes a connection between the L_{2} -discretization ( 3.1 ) and the following nonlinear m -term approximation problem: \sigma_{m}(I,{\mathcal{D}})=\inf_{B\in\Sigma_{m}({\mathcal{D}})}\|I-B\|, where {\mathcal{D}}:=\{\mathbf{G}(\xi)\colon\xi\in\Omega\} and \Sigma_{m}({\mathcal{D}}) denotes the set of all N\times N matrices of the form B=\sum_{j=1}^{m}\lambda_{j}\mathbf{G}(\xi^{j}),\ \ \lambda_{1},\ldots,\lambda_{m}\in\mathbb{R},\ \ \xi^{1},\ldots,\xi^{m}\in\Omega. Using this connection, one can apply a relaxed greedy algorithm to construct a set of points \{\xi^{j}\}_{j=1}^{m}\subset\Omega , with m of order N^{2} , for which ( 3.1 ) holds with uniform weights \lambda_{1}=\ldots=\lambda_{m}=\frac{1}{m} (see [ 63 , Proposition 5.1] ). 3.2 Discretization using random samples We start with the following result, which was derived in [ 63 ] using Lemma 3.4 below. Theorem 3.2 ( [ 63 ] ) . Let X_{N} be an N -dimensional space of bounded functions on \Omega such that X_{N}\in\textnormal{NI}_{2,\infty}(\sqrt{KN}) for some constant K\geq 1 . Let \xi^{1},\ldots,\xi^{m} be a sequence of IID random points drawn from the probability measure \mu on \Omega . If m\geq 3AKN\epsilon^{-2}\log N for some constants A>1 and \epsilon\in(0,1) , then the inequality (1-\epsilon)\|f\|_{L_{2}(\Omega,\mu)}^{2}\leq\frac{1}{m}\sum_{j=1}^{m}|f(\xi^{j})|^{2}\leq(1+\epsilon)\|f\|_{L_{2}(\Omega,\mu)}^{2} (3.3) holds for all f\in X_{N} with probability at least 1-2N^{-A+1} . Remark 3.3 . By setting A=\frac{m\epsilon^{2}}{3KN\log N} , we may reformulate the conclusion of Theorem 3.2 as follows. If m\geq 3KN\epsilon^{-2}\log N , then the estimate ( 3.3 ) holds for all f\in X_{N} with probability at least 1-2N\exp\Bigl(-\frac{m\varepsilon^{2}}{3KN}\Bigr). We note that results of this type can be traced back to Rudelson [ 55 ] , whose work implies a similar discretization bound for random points but yields a slightly weaker probability estimate. The proof of Theorem 3.2 relies on the following result of Tropp [ 65 ] . Lemma 3.4 ( [ 65 ] ) . Let \{T_{k}\}_{k=1}^{m} be a sequence of independent N\times N positive semi-definite random matrices, and define T=\sum_{k=1}^{m}T_{k} . Assume that \max_{1\leq k\leq m}\|T_{k}\|\leq M<\infty\quad\text{almost surely} for some constant M>0 , where \|\cdot\| denotes the spectral norm. Let \lambda_{\min}:=\lambda_{\min}(\mathbb{E}T) and \lambda_{\max}:=\lambda_{\max}(\mathbb{E}T) . Then \displaystyle\mathbb{P}\Bigl[\lambda_{\min}(T)\leq(1-\epsilon)\lambda_{\min}\Bigr]\leq N\left(\frac{1}{e^{\epsilon}(1-\epsilon)^{1-\epsilon}}\right)^{\lambda_{\min}/M},\ \ \ \forall\epsilon\in[0,1), \displaystyle\mathbb{P}\Bigl[\lambda_{\max}(T)\geq(1+\epsilon)\lambda_{\max}\Bigr]\leq N\left(\frac{e^{\epsilon}}{(1+\epsilon)^{1+\epsilon}}\right)^{\lambda_{\max}/M},\ \ \forall\epsilon>0. Remark 3.5 . Let \varphi(t):=(1-t)\log(1-t) for t\in[0,1) . Since \varphi^{\prime\prime\prime}(t)=\frac{1}{(1-t)^{2}}>0,\ \ \forall t\in[0,1), it follows by Taylor’s theorem that \varphi(t)\geq\varphi(0)+\varphi^{\prime}(0)t+\frac{1}{2}\varphi^{\prime\prime}(0)t^{2}=-t+\frac{t^{2}}{2},\ \ \forall t\in[0,1), which implies (1-t)^{1-t}\geq\exp\Bigl(-t+\frac{t^{2}}{2}\Bigr),\ \ \forall t\in[0,1]. Similarly, using Taylor’s theorem, one has (1+t)\log(1+t)\geq t+\frac{1}{2}\frac{t^{2}}{1+t},\ \ \forall t\geq 0, implying (1+t)^{1+t}\geq\exp\Bigl(t+\frac{1}{2}\frac{t^{2}}{1+t}\Bigr),\ \ \forall t\geq 0. Substituting these estimates into Lemma 3.4 yields \displaystyle\mathbb{P}\Bigl[\lambda_{\min}(T)\leq(1-\epsilon)\lambda_{\min}\Bigr]\leq N\exp\Bigl(-\frac{\epsilon^{2}}{2}\frac{\lambda_{\min}}{M}\Bigr),\ \ \ \forall\epsilon\in[0,1), (3.4) \displaystyle\mathbb{P}\Bigl[\lambda_{\max}(T)\geq(1+\epsilon)\lambda_{\max}\Bigr]\leq N\exp\Bigl(-\frac{\epsilon^{2}}{2(1+\epsilon)}\cdot\frac{\lambda_{\max}}{M}\Bigr),\ \ \forall\epsilon>0. (3.5) For completeness, we provide a proof of Theorem 3.2 as follows. Proof of Theorem 3.2 . Let \{u_{1},\ldots,u_{N}\} be an orthonormal basis of X_{N} , and let \mathbf{u}(x):=(u_{1}(x),\ldots,u_{N}(x))\text{ for }x\in\Omega. The condition X_{N}\in\textnormal{NI}_{2,\infty}(\sqrt{KN}) implies (see ( 1.6 )) |\mathbf{u}(x)|^{2}=\sum_{j=1}^{N}|u_{j}(x)|^{2}\leq KN,\ \ \forall x\in\Omega. Now consider the m\times N random matrix \boldsymbol{\Phi}{u}=\begin{bmatrix}\mathbf{u}(\xi^{1})\\ \mathbf{u}(\xi^{2})\\ \vdots\\ \mathbf{u}(\xi^{m})\end{bmatrix}. Let T:=\frac{1}{m}\boldsymbol{\Phi}^{T}\boldsymbol{\Phi} . Then T=\frac{1}{m}\sum_{j=1}^{m}\mathbf{u}(\xi^{j})^{T}\mathbf{u}(\xi^{j})=\sum_{j=1}^{m}T_{j}\ \ \ \text{with}\ \ T_{j}=\frac{1}{m}\mathbf{u}(\xi^{j})^{T}\mathbf{u}(\xi^{j}). Clearly, the T_{j} are independent, positive semi-definite random matrices satisfying that \|T_{j}\|=\max_{x\in\mathbb{S}^{N-1}}x^{T}T_{j}x=\frac{1}{m}|\mathbf{u}(\xi^{j})|^{2}\leq\frac{KN}{m}. Moreover, since \{u_{j}\}_{j=1}^{N} is an orthonormal basis of X_{N} , we have \mathbb{E}T=\frac{1}{m}\sum_{j=1}^{m}\mathbb{E}\Bigl[\mathbf{u}(\xi^{j})^{T}\mathbf{u}(\xi^{j})\Bigr]=\mathbb{E}\Bigl[\mathbf{u}(\xi^{1})^{T}\mathbf{u}(\xi^{1})\Bigr]=I_{N}, where I_{N} denotes the N\times N identity matrix. Now applying Lemma 3.4 , ( 3.4 ) and ( 3.5 ) with M=\frac{KN}{m} and \lambda_{\max}=\lambda_{\min}=1 yields that for any \epsilon\in(0,1/2) , \displaystyle\mathbb{P}\Bigl[1-\epsilon\leq\lambda_{\min}(T)\leq\lambda_{\max}(T)\leq 1+\epsilon\Bigr] \displaystyle\geq 1-\mathbb{P}\Bigl[\lambda_{\min}(T)\leq 1-\epsilon\Bigr]-\mathbb{P}\Bigl[\lambda_{\max}(T)\geq 1+\epsilon\Bigr] \displaystyle\geq 1-N\Bigg[\exp\Bigl(-\frac{\epsilon^{2}}{2}\frac{m}{KN}\Bigr)+\exp\Bigl(-\frac{\epsilon^{2}}{2(1+\epsilon)}\cdot\frac{m}{KN}\Bigr)\Bigg] \displaystyle\geq 1-2N\exp\Bigl(-\frac{m\epsilon^{2}}{3KN}\Bigr)\geq 1-2N^{-A+1} provided that m\geq 3KAN\epsilon^{-2}\log N . Theorem 3.2 then follows by Lemma 3.1 . ∎ Remark 3.6 . Clearly, the above proof also yields the following estimate: for any \epsilon\geq 1 and any m\geq 1 , \displaystyle\mathbb{P}\Bigl[\lambda_{\max}(T)\leq 1+\epsilon\Bigr] \displaystyle\geq 1-N\exp\Bigl(-\frac{\epsilon^{2}}{2(1+\epsilon)}\cdot\frac{m}{KN}\Bigr) \displaystyle\geq 1-N\exp\Bigl(-\frac{\epsilon}{4}\frac{m}{KN}\Bigr). In particular, if 1\leq m\leq KN\log N , then taking \epsilon=\frac{4AKN\log N}{m} for some constant A>1 , we deduce \displaystyle\mathbb{P}\Bigl[\lambda_{\max}(T)\leq 1+\frac{4AKN\log N}{m}\Bigr]\geq 1-N^{-A+1}. Since for any \mathbf{y}\in\mathbb{R}^{N} , \langle T\mathbf{y},\mathbf{y}\rangle=\frac{1}{m}\sum_{j=1}^{m}|\langle\mathbf{y},\mathbf{u}(\xi^{j})\rangle|^{2}\leq\lambda_{\max}(T)\cdot|y|^{2}, this implies the following one-sided L_{2} -Marcinkiewicz inequality. Corollary 3.7 . Let X_{N} be an N -dimensional space of bounded functions on \Omega , and assume that X_{N}\in\textnormal{NI}_{2,\infty}(\sqrt{KN}) for some constant K\geq 1 . Let \xi^{1},\ldots,\xi^{m} be a sequence of IID random points drawn from the probability measure \mu on \Omega . If 1\leq m\leq KN\log N , then for any given constant A\geq 1 , the one-sided inequality \frac{1}{m}\sum_{j=1}^{m}|f(\xi^{j})|^{2}\leq\Bigl(1+\frac{4AKN\log N}{m}\Bigr)\|f\|_{L_{2}(\Omega,\mu)}^{2} holds for all f\in X_{N} with probability at least 1-N^{-A+1} . The Nikol’skii condition \textnormal{NI}_{2,\infty}(\sqrt{KN}) plays an important role in the above proof of Theorem 3.2 . However, the constant K in this assumption can be very large, in which case one cannot expect a Marcinkiewicz type theorem with uniform weights and at most CN\log N points with C>0 being a universal constant. For instance, consider the space \mathcal{P}_{N} of all algebraic polynomials of degree at most N-1 on [-1,1] . It is well-known that \mathcal{P}_{N} satisfies the (2,\infty) -Nikol’skii condition \textnormal{NI}_{2,\infty}(\sqrt{KN}) with a least constant K\geq CN , and any Marcinkiewicz type inequality with uniform weights for the space \mathcal{P}_{N} requires at least CN^{2} points (see [ 23 , Remark 2.1] ). Nonetheless, Theorem 3.2 with K=1 combined with a change of density argument could be used to yield a weighted discretization result for spaces X_{N} that may not satisfy \textnormal{NI}_{2,\infty}(\sqrt{KN}) assumption or satisfy it only with a very large constant K . To be more precise, let \lambda(X_{N},\mu;\cdot) denote the Christoffel function on \Omega associated with the space X_{N} and the measure \mu , defined as \lambda(X_{N},\mu;x):=\inf_{\begin{subarray}{c}f\in X_{N}\\ f(x)=1\end{subarray}}\int_{\Omega}|f(\xi)|^{2}\,d\mu(\xi),\ \ x\in\Omega, (3.6) where it is agreed that \lambda(X_{N},\mu;x)=\infty if f(x)=0 for all f\in X_{N} . It can be easily seen that \int_{\Omega}\frac{1}{\lambda(X_{N},\mu;x)}d\mu(x)=N. Corollary 3.8 . Let X_{N} be an N -dimensional subspace of L_{2}(\Omega,\mu) with the associated Christoffel function \lambda_{N}(\cdot)=\lambda(X_{N},\mu;\cdot) as defined in ( 3.6 ). Let \xi^{1},\ldots,\xi^{m} be a sequence of IID random points drawn from the distribution \frac{1}{N\lambda_{N}(x)}\,\mu(dx) . If m\geq 3AN\epsilon^{-2}\log N for some constants A>1 and \epsilon\in(0,1) , then the inequalities (1-\epsilon)\|f\|_{L_{2}(\Omega,\mu)}^{2}\leq\frac{N}{m}\sum_{j=1}^{m}\lambda_{N}(\xi^{j})\left|f\left(\xi^{j}\right)\right|^{2}\leq(1+\epsilon)\|f\|_{L_{2}(\Omega,\mu)}^{2},\quad\forall f\in X_{N}, hold simultaneously with probability at least 1-2N^{-A+1} . For completeness, we provide a proof of this corollary as follows. Proof. Let \left\{u_{1},\ldots,u_{N}\right\} be an orthonormal basis of X_{N} . Then \frac{1}{\lambda_{N}(x)}=NF(x)^{2}\ \ \text{with}\ \ F(x):=\Bigl(\frac{1}{N}\sum_{k=1}^{N}\left|u_{k}(x)\right|^{2}\Bigr)^{1/2}. Consider the probability measure d\nu:=F^{2}d\mu on \Omega . Define a mapping U:L_{2}(\Omega,\mu)\to L_{2}(\Omega,\nu) by Uf(x)=f(x)/F(x) if F(x)>0 , and Uf(x)=0 otherwise. Since F(x)=0 implies f(x)=0 for all f\in X_{N} , it follows that \|Uf\|_{L_{2}(\Omega,\nu)}=\|f\|_{L_{2}(\Omega,\mu)},\ \ \forall f\in X_{N}. Moreover, it is easily seen that \sup_{x\in\Omega}|g(x)|\leq\sqrt{N}\|g\|_{L_{2}(\Omega,\nu)},\ \ \forall g\in UX_{N}. Corollary 3.8 then follows by applying Theorem 3.2 to the space UX_{N}\subset L_{2}(\Omega,\nu) with K=1 . ∎ 3.3 The minimum number of points required for L_{2} -discretization Given two constants C_{2}\geq 1\geq C_{1}>0 , we denote by m(X_{N};2;C_{1},C_{2}) the smallest positive integer m for which there exist m points \xi^{1},\ldots,\xi^{m}\in\Omega such that C_{1}\|f\|_{L_{2}(\Omega,\mu)}^{2}\leq\frac{1}{m}\sum_{j=1}^{m}|f(\xi^{j})|^{2}\leq C_{2}\|f\|_{L_{2}(\Omega,\mu)}^{2},\ \ \forall f\in X_{N}. Clearly, m(X_{N};2;C_{1},C_{2})\geq N . Regarding the upper bound, Theorem 3.2 (originally due to Rudelson [ 54 ] ) establishes that if X_{N}\in\textnormal{NI}_{2,\infty}(\sqrt{KN}) , then m(X_{N};2;1/2,3/2)\leq CKN\log N. The following remarkable theorem asserts that the extra factor \log N in this bound can be removed. The proof relies on the breakthrough theorem of A. Marcus, D. Spielman, and N. Srivastava [ 49 ] combined with an iterative procedure initially proposed in [ 7 , 48 ] . Theorem 3.9 ( [ 37 , 45 ] ) . Let X_{N} be an N -dimensional space of bounded functions on \Omega such that X_{N}\in\textnormal{NI}_{2,\infty}(\sqrt{KN}) for some constant K\geq 1 . Then for any \epsilon\in(0,1) , there exist \xi^{1},\ldots,\xi^{m}\in\Omega with m\leq C\epsilon^{-2}KN and C being an absolute constant such that (1-\epsilon)\|f\|_{L_{2}(\Omega,\mu)}^{2}\leq\frac{1}{m}\sum_{j=1}^{m}|f(\xi^{j})|^{2}\leq(1+\epsilon)K\|f\|_{L_{2}(\Omega,\mu)}^{2},\ \ \forall f\in X_{N}. (3.7) We point out that Theorem 3.9 was established in [ 45 ] with general positive constants C_{1} and C_{2}K instead of the constants 1-\epsilon and (1+\epsilon)K in ( 3.7 ). The current version of Theorem 3.9 is due to [ 37 ] , where it was observed that inequality ( 3.7 ) can be obtained by refining the iteration technique introduced in [ 45 ] . Theorem 3.9 combined with the change of density argument as given in the proof of Corollary 3.8 yields immediately the following result: Corollary 3.10 ( [ 37 ] ) . Given any N -dimensional space X_{N} of bounded functions on \Omega , and any \epsilon\in(0,1) , there exist \xi^{1},\ldots,\xi^{m}\in\Omega with m\leq C\epsilon^{-2}N and C being an absolute constant and positive weights \lambda_{1},\cdots,\lambda_{m}>0 such that (1-\epsilon)\|f\|_{L_{2}(\Omega,\mu)}^{2}\leq\sum_{j=1}^{m}\lambda_{j}|f(\xi^{j})|^{2}\leq(1+\epsilon)\|f\|_{L_{2}(\Omega,\mu)}^{2},\ \ \forall f\in X_{N}. Example 3.11 . Let Q\subset\mathbb{Z}^{d} be a finite set of frequencies, and consider the space \mathcal{T}(Q):=\operatorname{span}\bigl\{e^{\mathbf{i}\langle k,\cdot\rangle}:k\in Q\bigr\} of all trigonometric polynomials with frequencies from Q on the cube \Omega=[0,2\pi)^{d} , equipped with the normalized Lebesgue measure \mu . Clearly, \mathcal{T}(Q)\in\textnormal{NI}_{2,\infty}(\sqrt{N}) with N:=\dim\mathcal{T}(Q)=|Q| . Therefore, by Theorem 3.9 , we can find a set of m\leq C\epsilon^{-2}N points \xi^{1},\ldots,\xi^{m}\in\Omega such that (1-\epsilon)\|f\|_{L_{2}(\Omega,\mu)}^{2}\leq\frac{1}{m}\sum_{j=1}^{m}|f(\xi^{j})|^{2}\leq(1+\epsilon)\|f\|_{L_{2}(\Omega,\mu)}^{2},\ \ \forall f\in\mathcal{T}(Q). We conclude this section with the following tight estimate on weighted Marcinkiewicz discretization inequality of L_{2} -norms, which follows directly from a result of G. Schechtman [ 56 ] . Theorem 3.12 ( [ 56 ] ) . If X_{N} is an N -dimensional subspace of L_{2}(\Omega) , then for any b\in(1,2] , there exist a set of m\leq bN points x^{1},\ldots,x^{m}\in\Omega and a set of nonnegative weights \lambda_{j} , j=1,\ldots,m such that \|f\|_{2}\leq\left(\sum_{j=1}^{m}\lambda_{j}\left|f\left(x^{j}\right)\right|^{2}\right)^{1/2}\leq\frac{C}{b-1}\|f\|_{2},\quad\forall f\in X_{N} where C>1 is an absolute constant. Note that in Theorem 3.12 , the parameter b>1 can be chosen to be arbitrarily close to 1 . 4 Marcinkiewicz discretization theorems This section presents general results and methods concerning the discretization of L_{p} norms for p\neq 2 . 4.1 A conditional theorem Let \mathcal{W} be a compact subset of the space of bounded functions on \Omega . Let \xi^{1},\xi^{2},\ldots be a sequence of independent random points in \Omega . Consider the following random sampling discretization problem: for \epsilon\in(0,1) , 1\leq p<\infty and f\in\mathcal{W} , (1-\epsilon)\|f\|_{L_{p}(\Omega,\mu)}^{p}\leq\frac{1}{m}\sum_{j=1}^{m}|f(\xi^{j})|^{p}\leq(1+\epsilon)\|f\|_{L_{p}(\Omega,\mu)}^{p}. (4.1) Without loss of generality, we may assume that \mathcal{W}\subset B_{L_{p}}:=\bigl\{f\in L_{p}(\Omega,\mu):\|f\|_{L_{p}(\Omega,\mu)}\leq 1\bigr\} since otherwise we may replace \mathcal{W} with the set \bigl\{f/\|f\|_{L_{p}(\Omega,\mu)}\colon f\in\mathcal{W}\bigr\}. Our goal is to estimate the probability that ( 4.1 ) holds for all f\in\mathcal{W} in terms of the number m of required random points. Such an estimate can be established in terms of an integral of the \epsilon -entropy of the set \mathcal{W} in the uniform metric. We begin by recalling standard definitions and known estimates concerning entropy (see [ 9 , 25 , 58 ] and [ 62 , Chapter 7] ). Entropy. Consider a normed linear space X:=(X,\|\cdot\|_{X}) , and let B_{X}:=\bigl\{x\in X\colon\|x\|_{X}\leq 1\bigr\} denote the closed unit ball in X . For any \epsilon>0 , the covering number N_{\epsilon}(A,X) of a compact subset A\subset X is defined as the smallest positive integer n for which there exist elements x^{1},\ldots,x^{n}\in A such that A\subset\bigcup_{j=1}^{n}\bigl(x^{j}+\epsilon B_{X}\bigr). The \epsilon -entropy \mathcal{H}_{\epsilon}(A;X) of a compact set A in X is defined by \mathcal{H}_{\epsilon}(A,X):=\log_{2}N_{\epsilon}(A,X), while the entropy numbers e_{k}(A,X) of the set A in X are defined by e_{k}(A,X):=\inf\{\epsilon>0\colon\mathcal{H}_{\epsilon}(A,X)\leq k\},\qquad k=0,1,2,\ldots. Note that in our definition we require x^{j}\in A , which differs from the standard definition of N_{\epsilon}(A,X) and e_{k}(A,X) , where this restriction is not imposed. However, it is well known (see [ 62 ] , p. 208) that these characteristics may differ by at most a factor of 2 . To emphasize the dependence on the seminorm \|\cdot\|_{X} , we often write e_{k}(A,\|\cdot\|_{X})=e_{k}(A,X) and \mathcal{H}_{\epsilon}(A,\|\cdot\|_{X})=\mathcal{H}_{\epsilon}(A,X) . There is a simple and useful bound for the entropy of the unit ball in the finite-dimensional case. If X=\mathbb{R}^{m} , then for any 0<\epsilon\leq 1 , m\log_{2}\frac{1}{\epsilon}\leq\mathcal{H}_{\epsilon}(B_{X},\|\cdot\|_{X})\leq m\log_{2}\Bigl(1+\frac{2}{\epsilon}\Bigr). (4.2) This also implies that 2^{-1}\cdot 2^{-k/m}\leq e_{k}(B_{X},\|\cdot\|_{X})\leq 6\cdot 2^{-k/m},\quad k\in\mathbb{N}. Sharp entropy estimates are generally difficult to establish in a general high-dimensional setting. Here we only formulate a useful bound for entropy numbers, which will be used later. Theorem 4.1 ( [ 36 , Lemma 4.10, Corollary 4.2] ) . Let \Omega_{m}=\{\xi^{1},\ldots,\xi^{m}\}\subset\Omega be a finite subset of points in \Omega . Let X_{N} be an N -dimensional space of bounded functions on \Omega satisfying \|f\|_{L_{\infty}(\Omega)}\leq\sqrt{M}\|f\|_{L_{2}(\Omega,\mu)},\ \ \forall f\in X_{N}, (4.3) where M\geq 2 is a constant. Then for any 1\leq p\leq 2 , e_{k}(X_{N}^{p},\|\cdot\|_{L_{\infty}(\Omega_{m})})\leq C_{p}\sqrt{\log m}(\log M)^{\frac{1}{p}-\frac{1}{2}}\Bigl(\frac{M}{k}\Bigr)^{1/p},\ \ k\in\mathbb{N}, (4.4) where X_{N}^{p}:=\{f\in X_{N}\colon\|f\|_{L_{p}(\Omega,\mu)}\leq 1\} . Remark 4.2 . For p\in(1,2) , Theorem 4.1 was established in [ 36 , Lemma 4.10] via a slight modification of the proof of Proposition 16.8.6 in [ 58 ] . The case p=2 is an immediate consequence of [ 36 , Corollary 4.2] . Finally, for p=1 , the conclusion follows from [ 13 , (3.8) and (3.10)] and the following estimate on entropy numbers: e_{2k}(X_{N}^{1},\|\cdot\|_{L_{\infty}(\Omega_{m})})\leq Ce_{k}(X_{N}^{1},\|\cdot\|_{L_{2}(\Omega,\mu)})e_{k}(X_{N}^{2},\|\cdot\|_{L_{\infty}(\Omega_{m})}). Remark 4.3 . While the dimension N does not appear explicitly in the estimate ( 4.4 ), the constant M in the Nikolski inequality 4.3 typically depends on N , particularly when m\gg N . Furthermore, the use of the L_{\infty}(\Omega_{m}) norm embeds the original space X_{N} into a subspace of \mathbb{R}^{m} . Remark 4.4 . By definition, it is easily seen that the estimates of entropy numbers e_{k}(A,X)\leq Rk^{-\alpha},\ \ k=1,2,\cdots imply \mathcal{H}_{\epsilon}(A,X)\leq c(R/\epsilon)^{1/\alpha},\ \ \epsilon>0, where R>0 is a constant independent of k\in\mathbb{N} , and c>0 is an absolute constant. As a result, Theorem 4.1 implies that under the condition 4.3 , for any 1\leq p\leq 2 , we have \mathcal{H}_{\epsilon}(X_{N}^{p},\|\cdot\|_{L_{\infty}(\Omega_{m})})\leq C_{p}(\log m)^{\frac{p}{2}}(\log M)^{1-\frac{p}{2}}M\epsilon^{-p},\ \ \epsilon>0. We are now ready to formulate the conditional discretization theorem for the Marcinkiewicz-type discretization inequality of the form ( 4.1 ). The following theorem extends results in [ 14 , Theorem 1.3] , [ 20 , Theorem 5.1] and [ 63 ] . Theorem 4.5 ( [ 21 , Theorem 6.1] ) . Let (\Omega,\mu,{\mathcal{F}}) be a probability space. Let \mathcal{W} be a nonempty set of bounded functions on \Omega satisfying the following conditions for some 1\leq p<\infty : (i) \sup\limits_{f\in\mathcal{W}}\sup\limits_{x\in\Omega}|f(x)|\leq R^{1/p} for some constant R\geq 1 ; (ii) \{\lambda f\colon\lambda>0,f\in\mathcal{W},\ \|f\|_{L_{p}(\Omega,\mu)}\leq 1\}=\mathcal{W} . Let \xi^{1},\ldots,\xi^{m} be a sequence of independent random points on \Omega satisfying \sum_{k=1}^{m}\mathbb{P}[\xi^{k}\in E]=m\cdot\mu(E),\ \ \forall E\in{\mathcal{F}}. (4.5) Then there exist positive constants C_{p}\geq 1 and c_{p}\in(0,1) depending only on p such that for any \epsilon\in(0,1/2) and any integer m\geq C_{p}\epsilon^{-5}\Bigl(\log\frac{R}{\epsilon}\Bigr)\int_{c_{p}\epsilon}^{R}{\mathcal{H}}_{\epsilon t^{1/p}}(\mathcal{W};L_{\infty})dt, (4.6) the inequality (1-\epsilon)\|f\|_{L_{p}(\Omega,\mu)}^{p}\leq\frac{1}{m}\sum_{j=1}^{m}|f(\xi^{j})|^{p}\leq(1+\epsilon)\|f\|_{L_{p}(\Omega,\mu)}^{p} holds for all f\in\mathcal{W} with probability at least 1-\exp\Bigl(-\frac{c_{p}m\epsilon^{4}}{R(\log\frac{R}{\epsilon})^{2}}\Bigr). Remark 4.6 . Theorem 4.5 was proved in [ 21 , Theorem 6.1] , where ( 4.6 ) is replaced by the following slightly different condition: m\geq C_{p}\epsilon^{-5}\left(\int_{c_{p}\epsilon^{1/p}}^{R^{1/p}}u^{\frac{p}{2}-1}\Bigl(\int_{u}^{R^{1/p}}\frac{{\mathcal{H}}_{\epsilon t}(\mathcal{W},L_{\infty})}{t}\,dt\Bigr)^{\frac{1}{2}}du\right)^{2}. (4.7) Note that, performing the change of variables v=u^{p} and s=t^{p} yields \text{RHS of \eqref{6-4}}=C^{\prime}_{p}\epsilon^{-5}\left(\int_{c^{\prime}_{p}\epsilon}^{R}v^{-\frac{1}{2}}\Bigl(\int_{v}^{R}\frac{{\mathcal{H}}_{\epsilon s^{1/p}}(\mathcal{W},L_{\infty})}{s}\,ds\Bigr)^{\frac{1}{2}}dv\right)^{2}, where c_{p}^{\prime}\in(0,1) . Using the Cauchy–Bunyakovsky–Schwarz inequality, and the Fubini theorem, we then obtain RHS of ( 4.7 ) \displaystyle\leq C_{p}\epsilon^{-5}\Bigl(\log\frac{R}{\epsilon}\Bigr)\int_{c_{p}^{\prime}\epsilon}^{R}{\mathcal{H}}_{\epsilon t^{1/p}}(\mathcal{W};L_{\infty})dt. Remark 4.7 . Note that either of the following two conditions implies the condition ( 4.5 ) in Theorem 4.5 : (i) \xi^{1},\ldots,\xi^{m} are identically distributed according to \mu ; (ii) there exists a partition \{\Lambda_{1},\ldots,\Lambda_{m}\} of \Omega such that \mu(\Lambda_{j})=\frac{1}{m} and \xi^{j}\in\Lambda_{j} is distributed according to m\cdot\mu\Bigl|_{\Lambda_{j}} for each 1\leq j\leq m . Theorem 4.5 combined with Theorem 4.1 implies Corollary 4.8 below. Corollary 4.8 . Let \{V_{j}\}_{j=1}^{L} be a sequence of linear subspaces of \mathbb{R}^{n} which satisfies the following condition for some constant R\geq 1 : \|f\|_{L_{\infty}^{n}}\leq\sqrt{R}\|f\|_{L_{2}^{n}},\ \ \ \forall f\in\bigcup_{j=1}^{L}V_{j}. (4.8) Let \xi^{1},\ldots,\xi^{m} be a sequence of independent random variables taking values in \{1,2,\ldots,n\} and satisfying \frac{1}{m}\sum_{j=1}^{m}\mathbb{P}[\xi^{j}\in E]=\frac{|E|}{n},\ \ \forall E\subset\{1,2,\ldots,n\}. Let \epsilon\in(0,\frac{1}{2}) . Then the following statements hold. (i) If 1\leq p\leq 2 , then there exist constants C_{p}(\epsilon)=C_{p}\epsilon^{-5-p}\log^{2}\frac{1}{\epsilon}\geq 1 and c_{p}>0 such that for any integer m\geq C_{p}(\epsilon)R\Bigl[(\log R)^{3-\frac{p}{2}}(\log n)^{\frac{p}{2}}+(\log L)(\log R)\Bigr], the Marcinkiewicz-type discretization inequality (1-\epsilon)\|f\|_{L_{p}^{n}}^{p}\leq\frac{1}{m}\sum_{j=1}^{m}|f(\xi^{j})|^{p}\leq(1+\epsilon)\|f\|_{L_{p}^{n}}^{p} (4.9) holds for all f\in\bigcup_{j=1}^{L}V_{j} with probability 1-\exp\Bigl(-\frac{c_{p}m\epsilon^{4}}{R(\log\frac{R}{\epsilon})^{2}}\Bigr). (ii) If 21 and c_{p}>0 such that for any integer m\geq C_{p}(\epsilon)R^{p/2}\log R\Bigl[\log n+\log L\Bigr], the Marcinkiewicz-type discretization inequality ( 4.9 ) holds for all f\in\bigcup_{j=1}^{L}V_{j} with probability 1-\exp\Bigl(-\frac{c_{p}m\epsilon^{4}}{R^{p/2}(\log\frac{R}{\epsilon})^{2}}\Bigr). Proof. Let \Omega_{n}:=\{1,2,\ldots,n\} and let \mu_{n} denote the uniform distribution on \Omega_{n} . Then the sequence of random variables \xi^{j} satisfies the condition ( 4.5 ) with \Omega=\Omega_{n} and \mu=\mu_{n} . Let \mathcal{W}_{p}:=\Bigl\{f\in\bigcup_{j=1}^{L}V_{j}:\ \|f\|_{L_{p}^{n}}\leq 1\Bigr\}. (i) Let 1\leq p\leq 2 . The assumption ( 4.8 ) implies that \|f\|_{L_{\infty}^{n}}\leq R^{1/p}\|f\|_{L_{p}^{n}} for all f\in\bigcup_{j=1}^{L}V_{j} (see ( 1.7 )). Therefore, using Theorem 4.1 (see Remark 4.4 ), we obtain {\mathcal{H}}_{t}(\mathcal{W}_{p},\|\cdot\|_{L_{\infty}^{n}})\leq C_{p}t^{-p}R(\log R)^{1-\frac{p}{2}}(\log n)^{\frac{p}{2}}+2\log L,\ \ \forall t>0, implying \displaystyle\int_{c_{p}\epsilon}^{R}{\mathcal{H}}_{\epsilon t^{1/p}}(\mathcal{W}_{p};\|\cdot\|_{L_{\infty}^{n}})dt\leq C_{p}\epsilon^{-p}\Bigl(\log\frac{1}{\epsilon}\Bigr)R(\log R)^{2-\frac{p}{2}}(\log n)^{\frac{p}{2}}+2R\log L. Thus, applying Theorem 4.5 to \mathcal{W}=\mathcal{W}_{p} , we prove (i). (ii) Now assume that p>2 . Then for all f\in\bigcup_{j=1}^{L}V_{j} , we have \|f\|_{L_{\infty}^{n}}\leq\sqrt{R}\|f\|_{L_{2}^{n}}\leq R_{1}^{1/p}\|f\|_{L_{p}^{n}}\ \ \text{with}\ \ R_{1}=R^{p/2}. Since \mathcal{W}_{p}\subset\mathcal{W}_{2} , we obtain from ( 4.8 ) that for any t>0 , \displaystyle{\mathcal{H}}_{t}(\mathcal{W}_{p},\|\cdot\|_{L_{\infty}^{n}}) \displaystyle\leq{\mathcal{H}}_{t}(\mathcal{W}_{2},\|\cdot\|_{L_{\infty}^{n}})\leq Ct^{-2}R(\log n)+2\log L, implying that \displaystyle\int_{c_{p}\epsilon}^{R_{1}} \displaystyle{\mathcal{H}}_{\epsilon t^{1/p}}(\mathcal{W}_{p};\|\cdot\|_{L_{\infty}^{n}})dt\leq CR^{p/2}\Bigl[\epsilon^{-2}\log n+\log L\Bigr]. (ii) then follows by applying Theorem 4.5 to \mathcal{W}=\mathcal{W}_{p} . ∎ 4.2 Preliminary discretizations Theorem 4.5 is often applied together with the entropy estimates stated in Theorem 4.1 , as was done in the proof of Corollary 4.8 . This normally requires a preliminary step of discretization involving more random points. The following result is useful. Proposition 4.9 . Let 1\leq p<\infty be a fixed number. Let \{V_{j}\}_{j=1}^{L} be a sequence of linear subspaces of L_{\infty}(\Omega) such that \dim V_{j}\leq s for all 1\leq j\leq L , and \|f\|_{L_{\infty}(\Omega)}\leq R^{1/p}\|f\|_{L_{p}(\Omega,\mu)},\ \ \forall f\in\bigcup_{j=1}^{L}V_{j}, (4.10) for some constant R\geq 1 . Assume that 0<\epsilon\leq\frac{1}{8} , m is an integer satisfying m\geq 16R\epsilon^{-2}\Bigl[\log L+s\log\frac{3}{\epsilon}\Bigr], (4.11) and \{\xi^{j}\}_{j=1}^{m} is a sequence of IID random points drawn from the distribution \mu on \Omega . Then the Marcinkiewicz-type discretization inequality \displaystyle(1-5\epsilon)\|f\|_{L_{p}(\Omega,\mu)}^{p}\leq\frac{1}{m}\sum_{j=1}^{m}|f(\xi^{j})|^{p}\leq(1+5\epsilon)\|f\|_{L_{p}(\Omega,\mu)}^{p} (4.12) holds for all f\in\bigcup_{j=1}^{L}V_{j} with probability \geq 1-2\exp\Bigl(-\frac{m\epsilon^{2}}{16R}\Bigr) . For the proof of Proposition 4.9 , we need the following two lemmas. The first lemma appears in [ 7 , Lemma 2.1] , but also follows directly from the classical Bernstein inequality (see [ 60 , Theorem 4.22] ). Lemma 4.10 ( [ 7 , Lemma 2.1] ) . Let \{\eta_{j}\}_{j=1}^{m} be an independent sequence of random variables such that \mathbb{E}\eta_{j}=0 , \mathbb{E}|\eta_{j}|\leq M_{1} and |\eta_{j}|\leq M_{\infty} almost surely for all 1\leq j\leq m and some constants M_{1},M_{\infty}>0 . Then for any 0<\lambda0 , \alpha\|x\|_{X}\leq\|Tx\|_{Y}\leq\beta\|x\|_{X},\ \ \ \forall x\in\mathcal{A}. Then for any z\in X , we have \alpha(1-\gamma\epsilon)\|z\|_{X}\leq\|Tz\|_{Y}\leq\beta(1+2\epsilon)\|z\|_{X}\ \ \text{with}\ \ \gamma=\frac{3\beta}{\alpha}. For completeness, we provide a proof of Lemma 4.11 below. Proof. For z\in B_{X} , we denote by \varphi(z) an element in \mathcal{A} such that \|z-\varphi(z)\|_{X}\leq\epsilon . Then for any z\in B_{X} , we have \displaystyle\|Tz\|_{Y}\leq\|T\|\epsilon+\|T\varphi(z)\|_{Y}\leq\|T\|\epsilon+\beta\|\varphi(z)\|_{X}\leq\|T\|\epsilon+\beta, which, taking supremum over all z\in B_{X} , implies \|T\|\leq\frac{\beta}{1-\epsilon}\leq\beta(1+2\epsilon). To prove the left-hand-side estimate, we note that for any z\in X with \|z\|_{X}=1 , we have \displaystyle\|Tz\|_{Y} \displaystyle\geq\|T\varphi(z)\|_{Y}-\|T\|\epsilon\geq\alpha\|\varphi(z)\|_{X}-\|T\|\epsilon \displaystyle\geq\alpha(1-\epsilon)-2\beta\epsilon\geq\alpha-3\beta\epsilon. This proves the lemma. ∎ Proof of Proposition 4.9 . By inequality ( 4.2 ), for each 1\leq j\leq L , there exists an \epsilon -net {\mathcal{A}}_{j}\subset V_{j}^{p} of V_{j}^{p}:=V_{j}\cap B_{L_{p}} in the space L_{p} such that |{\mathcal{A}}_{j}|\leq\bigl(1+\frac{2}{\epsilon}\bigr)^{v}. Let {\mathcal{A}}:=\bigcup_{j=1}^{L}{\mathcal{A}}_{j}. Then \displaystyle\log|{\mathcal{A}}| \displaystyle\leq\log\Bigl[L\Bigl(1+\frac{2}{\epsilon}\Bigr)^{v}\Bigr]\leq\log L+v\log\frac{3}{\epsilon}. (4.13) Furthermore, ( 4.10 ) implies that \frac{\|f\|_{\infty}^{p}}{\|f\|_{p}^{p}}=\Bigg\|\frac{|f|^{p}}{\|f\|_{p}^{p}}\Bigg\|_{\infty}\leq R\ \ \text{ for all $f\in{\mathcal{A}}$,} where \|f\|_{\infty}=\sup_{x\in\Omega}|f(x)| and \|f\|_{p}=\|f\|_{L_{p}(\Omega,\mu)} . Thus, using ( 4.13 ), and Lemma 4.10 with M_{\infty}=R , M_{1}=2 and \eta_{j}=\frac{|f(\xi^{j})|^{p}}{\|f\|_{p}^{p}}-1,\ \ j=1,2,\cdots,m, we conclude that the inequalities \Bigl|\frac{1}{m}\sum_{j=1}^{m}|f(\xi^{j})|^{p}-\int_{\Omega}|f|^{p}\,d\mu\Bigr|\leq\epsilon\|f\|_{L_{p}(\Omega,\mu)}^{p},\ \ \forall f\in{\mathcal{A}} (4.14) hold with probability \displaystyle\geq \displaystyle 1-2|{\mathcal{A}}|\exp\Bigl(-\frac{m\epsilon^{2}}{8R}\Bigr)=1-2\exp\Bigl(\log|{\mathcal{A}}|-\frac{m\epsilon^{2}}{8R}\Bigr) \displaystyle\geq \displaystyle 1-2\exp\Bigl(\log L+v\log\frac{3}{\epsilon}-\frac{m\epsilon^{2}}{8R}\Bigr). However, the condition ( 4.11 ) implies \log L+v\log\frac{3}{\epsilon}\leq\frac{m\epsilon^{2}}{16R}. It follows that ( 4.14 ) holds for all f\in{\mathcal{A}} with probability \geq 1-2\exp\Bigl(-\frac{m\epsilon^{2}}{16R}\Bigr). To complete the proof, we just need to note that by Lemma 4.11 , ( 4.14 ) implies ( 4.12 ). ∎ 4.3 Sampling discretization of L_{p} norms In this subsection, we show how to use the preliminary discretization from the last subsection, together with Corollary 4.8 , to deduce a Marcinkiewicz-type discretization theorem. Theorem 4.12 . Let X_{N} be an N -dimensional space of bounded functions on \Omega , and assume that X_{N}\in\textnormal{NI}_{2,\infty}(\sqrt{KN}) for some constant K\geq 2 . Let \{\xi^{j}\}_{j=1}^{\infty} be a sequence of IID random points drawn from the distribution \mu . Let \epsilon\in(0,1/2) . (i) If 1\leq p\leq 2 , then there exists a constant C_{p}(\epsilon)\geq 1 such that for any given parameter A\geq 1 , and any integer m\geq C_{p}(\epsilon)A\cdot KN\cdot\log^{3}(2KN), (4.15) the Marcinkiewicz-type discretization inequality (1-\epsilon)\|f\|_{L_{p}(\Omega,\mu)}^{p}\leq\frac{1}{m}\sum_{j=1}^{m}|f(\xi^{j})|^{p}\leq(1+\epsilon)\|f\|_{L_{p}(\Omega,\mu)}^{p} holds for all f\in X_{N} with probability \geq 1-(KN)^{-A} . (ii) If 20 is a sufficiently large fixed constant, since otherwise Theorem 4.12 follows directly from Proposition 4.9 with L=1 , s=N , and R=KN . We will use Corollary 4.8 (i). To this end, we need a step of preliminary discretization involving more points. Let \ell_{N} denote the smallest integer \geq CKN^{2}\epsilon^{-2}\log\frac{1}{\epsilon} . Let m_{1}:=m\ell_{N} , and let \Omega_{m_{1}}:=\{x_{1},\ldots,x_{m_{1}}\}\subset\Omega be a set of IID random points drawn from the distribution \mu . Note that C_{1}(C,\epsilon)\log(KN)\leq\log m_{1}\leq C_{2}(C,\varepsilon)\log(KN) for some constants C_{2}(C,\epsilon)\geq C_{1}(C,\epsilon)>0 . Furthermore, by Proposition 4.9 , the following inequalities hold simultaneously with probability \geq 1-4\exp\Bigl(-\frac{cm_{1}\epsilon^{2}}{KN}\Bigr)\geq 1-4e^{-mN} , for a sufficiently large constant C>0 , \displaystyle\Bigl|\|f\|_{L_{p}(\Omega,\mu)}^{p}-\|f\|_{L_{p}(\Omega_{m_{1}})}^{p}\Bigr|\leq\frac{\epsilon}{10}\|f\|_{L_{p}(\Omega,\mu)}^{p},\ \ \forall f\in X_{N}, (4.16) \displaystyle\Bigl|\|f\|_{L_{2}(\Omega,\mu)}^{2}-\|f\|_{L_{2}(\Omega_{m_{1}})}^{2}\Bigr|\leq\frac{\epsilon}{10}\|f\|_{L_{2}(\Omega,\mu)}^{2},\ \ \forall f\in X_{N}. (4.17) Let \{\Lambda_{1},\ldots,\Lambda_{m}\} be a partition of the set \{1,\ldots,m_{1}\} such that |\Lambda_{j}|=\ell_{N} for 1\leq j\leq m . Let n_{1},\ldots,n_{m} be an independent sequence of random variables that is independent of \{x_{1},\ldots,x_{m_{1}}\} such that each n_{j} is uniformly distributed in \Lambda_{j} . Define \xi^{j}=x_{n_{j}} , j=1,2,\ldots,m . Then \xi^{1},\ldots,\xi^{m}\in\Omega are IID random points with common distribution \mu . Next, we fix a set \Omega_{m_{1}} of random points x_{1},\ldots,x_{m_{1}} for which both ( 4.16 ) and ( 4.17 ) hold. Instead of dealing with functions on the entire set \Omega , we consider their restrictions on the set \Omega_{m_{1}} equipped with the uniform distribution. From the assumption X_{N}\in\textnormal{NI}_{2,\infty}(\sqrt{KN}) and by ( 4.17 ), we have \|f\|_{L_{\infty}(\Omega_{m_{1}})}\leq\sqrt{2KN}\|f\|_{L_{2}(\Omega_{m_{1}})},\ \ \forall f\in X_{N}. Thus, applying Corollary 4.8 (i) with L=1 , n=m_{1} and R=2KN , we conclude that the inequalities \Bigl|\frac{1}{m}\sum_{j=1}^{m}|f({x_{n_{j}}})|^{p}-\|f\|_{L_{p}(\Omega_{m_{1}})}^{p}\Bigr|\leq\frac{\epsilon}{10}\|f\|_{L_{p}(\Omega_{m_{1}})}^{p},\ \ \forall f\in X_{N} (4.18) hold with probability \geq 1-\exp\Bigl(-\frac{c_{p}(\epsilon)m}{KN\log^{2}(KN)}\Bigr) provided that m\geq C_{p}(\epsilon)KN\log^{3}(KN). Now, we recall that \xi^{j}=x_{n_{j}} . Clearly, ( 4.18 ) combined with ( 4.16 ) yields that (1-\epsilon)\|f\|_{L_{p}(\Omega,\mu)}^{p}\leq\frac{1}{m}\sum_{j=1}^{m}|f(\xi^{j})|^{p}\leq(1+\epsilon)\|f\|_{L_{p}(\Omega,\mu)}^{p},\ \ \forall f\in X_{N}. (4.19) To conclude the proof, we estimate the probability of the event E that ( 4.19 ) holds. Let E_{1} denote the event that both ( 4.16 ) and ( 4.17 ) hold. Note that \chi_{E_{1}} is a function of (x_{1},x_{2},\ldots,x_{m_{1}}) , and \mathbb{P}(E_{1})\geq 1-4e^{-mN} . Moreover, from the above proof, we have \displaystyle\chi_{E_{1}}\cdot\mathbb{E}[\chi_{E}|x_{1},\ldots,x_{m_{1}}] \displaystyle\geq\chi_{E_{1}}\cdot\left(1-\exp\Bigl(-\frac{c_{p}(\epsilon)m}{KN\log^{2}(KN)}\Bigr)\right), implying that \displaystyle\mathbb{E}\Bigl[\chi_{E_{1}}\cdot\mathbb{E}[\chi_{E}|x_{1},\ldots,x_{n_{1}}]\Bigr]\geq\mathbb{P}(E_{1})\cdot\left(1-\exp\Bigl(-\frac{c_{p}(\epsilon)m}{KN\log^{2}(KN)}\Bigr)\right) \displaystyle\geq 1-5\exp\Bigl(-\frac{c_{p}(\epsilon)m}{KN\log^{2}(KN)}\Bigr). Thus, if m is an integer satisfying ( 4.15 ) for some A\in\mathbb{N} , then \displaystyle\mathbb{P}(E) \displaystyle\geq\mathbb{E}[\chi_{E\cap E_{1}}]=\mathbb{E}\Bigl[\chi_{E_{1}}\cdot\mathbb{E}[\chi_{E}|x_{1},\ldots,x_{n_{1}}]\Bigr] \displaystyle\geq 1-5\exp\Bigl(-C_{p}(\epsilon)c_{p}(\epsilon)A\log(KN)\Bigr)\geq 1-(KN)^{-A} provided that the constant C_{p}(\varepsilon)>0 is sufficiently large. This completes the proof of (i). The proof of (ii) is almost identical, using Corollary 4.8 (ii) and the fact that \|f\|_{L_{2}(\Omega,\mu)}\leq\|f\|_{L_{p}(\Omega,\mu)} for p>2 . ∎ 4.4 Sampling discretization with weights The constant K in the (2,\infty) -Nikol’skii condition \textnormal{NI}_{2,\infty}(\sqrt{KN}) can grow substantially as the dimension of X_{N} increases. For instance, if X_{N} is the space of all algebraic polynomials of degree less than N on the interval [-1,1] and \mu is the probability measure on [-1,1] given by d\mu(x)=\frac{\Gamma(\lambda+1)}{\Gamma(\lambda+\frac{1}{2})\sqrt{\pi}}(1-x^{2})^{\lambda-\frac{1}{2}}\,dx for some constant \lambda>0 , then X_{N}\in\textnormal{NI}_{2,\infty}(\sqrt{KN}) with the least constant K\sim N^{2\lambda} (see, e.g., [ 50 , (7.13), (7.14)] ). In such instances, Theorem 4.12 requires a considerably larger number of random points for effectively discretizing L_{p} norms. Similar to the case of L_{2} -discretization, a change of density argument allows us to apply Theorem 4.12 to establish a weighted discretization theorem that does not require the (2,\infty) –Nikol’skii condition. The proof is similar to that of Corollary 3.8 for L_{2} -discretization. It relies on the following Lewis’ change of density lemma: Lemma 4.13 ( [ 7 , Lemma 7.1] , [ 43 ] ) . Given any 1\leq p<\infty and any N -dimensional subspace X_{N} of L_{p}(\Omega,\mu) , there exists a basis \{u_{j}\}_{j=1}^{N} of X_{N} such that the function F:=\bigl(\frac{1}{N}\sum_{j=1}^{N}|u_{j}|^{2}\bigr)^{\frac{1}{2}} has the following properties: \|F\|_{L_{p}(\Omega,\mu)}=1 , and for all scalars \{\lambda_{j}\}_{j=1}^{N}\subset\mathbb{R} , \int_{\Omega}\Bigl|\sum_{j=1}^{N}\lambda_{j}u_{j}(x)\Bigr|^{2}F(x)^{p-2}\,d\mu(x)=\sum_{j=1}^{N}\lambda_{j}^{2}. (4.20) To illustrate the idea, let F be the function as given in Lemma 4.13 . Consider the probability measure \nu(dx)=|F(x)|^{p}\mu(dx) on \Omega , and the linear mapping U:L_{p}(\Omega,\mu)\to L_{p}(\Omega,\nu) given by Uf(x)=\begin{cases}\frac{f(x)}{F(x)},\ \ &\text{if $F(x)\neq 0$};\\ 1,\ \ &\text{otherwise}.\end{cases} Since each function in X_{N} is identically zero on the set \{x\colon F(x)=0\} , we have \|Uf\|_{L_{p}(\nu)}=\|f\|_{L_{p}(\mu)},\ \ \forall f\in X_{N}. In addition, ( 4.20 ) implies that the sequence \psi_{j}:=Uu_{j} , j=1,2,\ldots,N forms an orthonormal basis of the space UX_{N} with respect to the inner product of L_{2}(\Omega,d\nu) . Moreover, we have \sum_{j=1}^{N}|\psi_{j}(x)|^{2}=N,\ \ \forall x\in\Omega, implying \|Uf\|_{L_{\infty}(\Omega)}\leq N^{\frac{1}{2}}\|Uf\|_{L_{2}(\Omega,\nu)},\ \ \forall f\in X_{N}. Thus, applying Theorem 4.12 to the space UX_{N} and the measure \nu , we deduce the following result. Corollary 4.14 . Let 1\leq p<\infty and let X_{N} be an N -dimensional space of bounded functions on \Omega associated with a function F given in Lemma 4.13 . Consider a new measure \nu given by d\nu=|F|^{p}\,d\mu. Let \{\xi^{j}\}_{j=1}^{\infty} be a sequence of IID random points drawn from the distribution \nu . Let \epsilon\in(0,1/2) . For j=1,2,\ldots,m , let \lambda_{j}:=\frac{1}{m}\frac{1}{|F(\xi^{j})|^{p}} if F(\xi^{j})\neq 0 , and \lambda_{j}=\frac{1}{m} if F(\xi^{j})=0 . (i) If 1\leq p\leq 2 , then there exists a constant C_{p}(\epsilon)\geq 1 such that for any given parameter A\geq 1 , and any integer m\geq C_{p}(\epsilon)A\cdot N\cdot\log^{3}(2N), the Marcinkiewicz-type discretization inequalities (1-\varepsilon)\|f\|_{L_{p}(\Omega,\mu)}^{p}\leq\sum_{j=1}^{m}\lambda_{j}\left|f\left(\xi^{j}\right)\right|^{p}\leq(1+\varepsilon)\|f\|_{L_{p}(\Omega,\mu)}^{p} (4.21) hold for all f\in X_{N} with probability \geq 1-N^{-A} . (ii) If 20 such that for any parameter A\geq 1 and any integer m\geq C_{p}(\epsilon)\cdot A\cdot R\Bigl[(\log R)^{3}+(\log R)^{3-\frac{p}{2}}(\log\log L)^{\frac{p}{2}}+(\log L)(\log R)\Bigr], the Marcinkiewicz-type discretization inequality (1-\epsilon)\|f\|_{L_{p}(\Omega,\mu)}^{p}\leq\frac{1}{m}\sum_{j=1}^{m}|f(\xi^{j})|^{p}\leq(1+\epsilon)\|f\|_{L_{p}(\Omega,\mu)}^{p}, holds for all f\in\bigcup_{j=1}^{L}V_{j} with probability \geq 1-R^{-A} . Theorem 5.1 can be deduced directly from Corollary 4.8 and Proposition 4.9 , following a similar approach as the proof of Theorem 4.12 . In this section, we explore universal discretization for special collections of subspaces generated by a given finite set of bounded functions on \Omega . In this context, we can improve the estimates provided in Theorem 5.1 . We introduce the general setting as follows. Let {\mathcal{D}}_{N}=\{\varphi_{i}\}_{i=1}^{N} be a fixed system of linearly independent bounded functions on \Omega satisfying \sup_{x\in\Omega}|\varphi_{j}(x)|\leq 1,\ \ j=1,2,\ldots,N. Given an integer 1\leq s\leq N , we denote by \mathcal{X}_{s}({\mathcal{D}}_{N}) the collection of all linear spaces spanned by \{\varphi_{j}\colon j\in J\} with J\subset\{1,2,\ldots,N\} and |J|=s . A function f:\Omega\to\mathbb{C} is said to be s -sparse with respect to \mathcal{D}_{N} if it belongs to a linear space from the collection \mathcal{X}_{s}({\mathcal{D}}_{N}) . We denote by \Sigma_{s}({\mathcal{D}}_{N}) the set of all s -sparse functions with respect to the dictionary \mathcal{D}_{N} ; namely, \displaystyle\Sigma_{s}({\mathcal{D}}_{N}): \displaystyle=\bigcup_{V\in{\mathcal{X}}_{s}({\mathcal{D}}_{N})}V. Recall that a finite sequence \{\xi^{j}\}_{j=1}^{m} of points in \Omega is said to provide universal discretization of the L_{p} norm for \Sigma_{s}(\mathcal{D}_{N}) , 1\leq p<\infty , with positive constants C_{1},C_{2} if C_{1}\|f\|_{L_{p}(\Omega,\mu)}^{p}\leq\frac{1}{m}\sum_{j=1}^{m}|f(\xi^{j})|^{p}\leq C_{2}\|f\|_{L_{p}(\Omega,\mu)}^{p},\ \ \forall f\in\Sigma_{s}({\mathcal{D}}_{N}). (5.1) Consider a sequence \{\xi^{j}\}_{j=1}^{m} of IID random points with common distribution \mu . Our goal is to establish an estimate for the probability that ( 5.1 ) holds in terms of the number m of random points. In the above context, we have the following result, which improves the estimates in Theorem 5.1 . Theorem 5.2 ( [ 21 ] ) . Let \mathcal{D}_{N}=\{\varphi_{j}\}_{j=1}^{N} be a set of N bounded functions on \Omega satisfying \max_{1\leq j\leq N}\|\varphi_{j}\|_{L_{\infty}(\Omega)}\leq 1. Let 1\leq s\leq N be a given integer. Assume that there exists a constant K\geq 1 such that \sum_{j\in J}|a_{j}|^{2}\leq K\Bigl\|\sum_{j\in J}a_{j}\varphi_{j}\Bigr\|^{2}_{L_{2}(\Omega,\mu)},\ \ \ \forall a_{j}\in\mathbb{C} (5.2) whenever J\subset\{1,2,\ldots,N\} with |J|=s . Let \xi^{1},\ldots,\xi^{m} be IID random points with common distribution \mu on \Omega . Then given 1\leq p\leq 2 and \epsilon\in(0,\frac{1}{2}) , there exist constants C_{p}(\varepsilon)>1 and c_{p}(\varepsilon)>0 , depending only on p and \varepsilon , such that the inequalities (1-\epsilon)\|f\|_{L_{p}(\Omega,\mu)}^{p}\leq\frac{1}{m}\sum_{j=1}^{m}|f(\xi^{j})|^{p}\leq(1+\epsilon)\|f\|_{L_{p}(\Omega,\mu)}^{p},\ \ \ \forall f\in\Sigma_{s}(\mathcal{D}_{N}) hold with probability \geq 1-2\exp\Bigl(-\frac{c_{p}(\epsilon)m}{Ks\log^{2}(2Ks)}\Bigr) provided that m\geq C_{p}(\epsilon)Ks\log N\cdot(\log(2Ks))^{2}\cdot(\log(2Ks)+\log\log N). Theorem 5.2 was proved in [ 21 ] . Note that the problem of universal discretization for some subspaces of the trigonometric polynomials was studied in [ 15 , 64 ] . The condition ( 5.2 ) is satisfied for all 1\leq s\leq N if \varphi_{1},\ldots,\varphi_{N} are linearly independent in L_{2}(\Omega,\mu) , in which case one can choose K^{-1} to be the smallest eigenvalue of the N\times N matrix \Bigl[\langle\varphi_{j},\varphi_{k}\rangle_{L_{2}(\Omega,\mu)}\Bigr]_{1\leq j,k\leq N} . In applications, we often assume that \mathcal{D}_{N} is a Riesz basis; that is, there exist constants 00 if for any \mathbf{x}\in\Sigma_{s}(\mathbb{R}^{N}) , we have C_{1}\|\mathbf{x}\|^{p}\leq\|\mathbf{Ax}\|^{p}_{\ell_{p}^{m}}\leq C_{2}\|\mathbf{x}\|^{p}. Next, let \Phi:\Omega\to\mathbb{R}^{N} be a vector-valued function on \Omega given by \Phi(\mathbf{x})=(\varphi_{1}(\mathbf{x}),\ldots,\varphi_{N}(\mathbf{x})),\ \ \mathbf{x}\in\Omega. Here and elsewhere in this section, we always treat \Phi(\mathbf{x}) as a row vector. Given a finite sequence \boldsymbol{\xi}:=\{\xi^{j}\}_{j=1}^{m}\subset\Omega of points, consider the m\times N random matrix \boldsymbol{\Phi}(\boldsymbol{\xi}):=\begin{bmatrix}\Phi(\xi^{1})\\ \Phi(\xi^{2})\\ \vdots\\ \Phi(\xi^{m})\end{bmatrix}=\begin{bmatrix}\varphi_{1}(\xi^{1})&\varphi_{2}(\xi^{1})&\cdots&\varphi_{N}(\xi^{1})\\ \varphi_{1}(\xi^{2})&\varphi_{2}(\xi^{2})&\cdots&\varphi_{N}(\xi^{2})\\ \vdots&\vdots&\vdots&\vdots\\ \varphi_{1}(\xi^{m})&\varphi_{2}(\xi^{m})&\cdots&\varphi_{N}(\xi^{m})\end{bmatrix}. (5.4) Additionally, given 1\leq p<\infty , we define the norm \|\cdot\|_{p,\Phi} on \mathbb{R}^{N} by \|\mathbf{a}\|_{p,\Phi}=\Bigl\|\sum_{j=1}^{N}a_{j}\varphi_{j}\Bigr\|_{L_{p}(\Omega,\mu)},\ \ \mathbf{a}=(a_{1},\ldots,a_{N})^{T}\in\mathbb{R}^{N}. With the above notation, we can then write the inequality ( 5.1 ) in the form C_{1}\|\mathbf{a}\|_{p,\Phi}\leq\bigl\|\boldsymbol{\Phi}(\boldsymbol{\xi})\mathbf{a}\bigr\|_{L_{p}^{m}}\leq C_{2}\|\mathbf{a}\|_{p,\Phi},\ \ \forall\mathbf{a}\in\Sigma_{s}(\mathbb{R}^{N}), which is equivalent to asserting that matrix m^{-1/p}\boldsymbol{\Phi}(\boldsymbol{\xi}) has the s -th order RIP\left(\ell^{m}_{p},\|\cdot\|_{p,\Phi}\right) with constants C_{1},C_{2}>0 . In particular, if p=2 , \epsilon\in(0,1) and \varphi_{1},\ldots,\varphi_{N} is an orthonormal system in L_{2}(\Omega,\mu) , then the universal discretization ( 5.1 ) with C_{1}=1-\epsilon and C_{2}=1+\epsilon can be formulated equivalently in terms of the RIP property of order s of the random matrix m^{-1/2}\boldsymbol{\Phi}(\boldsymbol{\xi}) : (1-\epsilon)\|z\|_{\ell_{2}^{N}}^{2}\leq m^{-1/2}\|\boldsymbol{\Phi}(\boldsymbol{\xi})z\|_{\ell_{2}^{m}}\leq(1+\epsilon)\|z\|_{\ell_{2}^{N}}^{2},\ \ \forall z\in\Sigma_{s}(\mathbb{R}^{N}). In summary, we have Theorem 5.4 . Assume that {\mathcal{D}}_{N}=\{\varphi_{1},\ldots,\varphi_{N}\} is a finite system of real valued functions on \Omega , 1\leq p<\infty and 1\leq s,m\leq N are integers. Then a sequence \boldsymbol{\xi}:=\{\xi^{j}\}_{j=1}^{m} of m points in \Omega provides the universal discretization ( 5.1 ) of the L_{p} norm for \Sigma_{s}({\mathcal{D}}_{N}) with constants C_{1},C_{2}>0 if and only if the m\times N matrix m^{-1/p}\boldsymbol{\Phi}(\boldsymbol{\xi}) , with \boldsymbol{\Phi}(\boldsymbol{\xi}) being defined in ( 5.4 ), has the s -th order RIP\left(\ell^{m}_{p},\|\cdot\|_{p,\Phi}\right) with constants C_{1},C_{2}>0 . In particular, if p=2 , \epsilon\in(0,1) and {\mathcal{D}}_{N} is an orthonormal system in L_{2}(\Omega,\mu) , then the universal discretization ( 5.1 ) with constants C_{1}=1-\epsilon and C_{2}=1+\epsilon holds if and only if the matrix m^{-1/2}\boldsymbol{\Phi}(\boldsymbol{\xi}) has the RIP property of order s with constants 1\pm\epsilon . Some applications of universal discretization and Theorem 5.4 can be found in [ 18 , 19 ] . 6 Some improved bounds in sampling discretization of integral norms Analogous to the L_{2} -discretization discussed in Section 3.3 , for any given constants C_{2}\geq 1\geq C_{1}>0 and 1\leq p<\infty , we define m(X_{N};p;C_{1},C_{2}) to be the smallest positive integer m for which there exist m points \xi^{1},\ldots,\xi^{m}\in\Omega such that C_{1}\|f\|_{L_{p}(\Omega,\mu)}^{p}\leq\frac{1}{m}\sum_{j=1}^{m}|f(\xi^{j})|^{p}\leq C_{2}\|f\|_{L_{p}(\Omega,\mu)}^{p},\ \ \forall f\in X_{N}. For simplicity, we denote this quantity by m(X_{N};p) when the specific values of the absolute constants C_{1},C_{2} are understood or not important from context. According to Theorem 4.12 , for every space X_{N} satisfying the (2,\infty) -Nikol’skii inequality \textnormal{NI}_{2,\infty}(\sqrt{KN}) , we have m(X_{N};p)\leq C_{p}\begin{cases}KN\log^{3}(KN),&\ \ \text{if $1\leq p\leq 2$};\\ (KN)^{p/2}\log^{2}(KN),&\ \ \text{if $20 is an absolute constant. It is natural to ask whether the upper bounds in ( 6.1 ) remain valid without the extra logarithmic factors under the condition X_{N}\in\textnormal{NI}_{2,\infty}(\sqrt{KN}) . For the discretization of L_{2} -norm, the answer is positive, due to the breakthrough work of A. Marcus, D. Spielman, and N. Srivastava [ 49 ] . In fact, according to Theorem 3.9 , we have m(X_{N};2;1/2,3/2)\leq CKN. For 1\leq p<2 , this remains a challenging open problem. There has been recent progress on this problem for 1\leq p<2 . It was established in [ 12 ] that for 1\leq p<2 and every X_{N}\in\textnormal{NI}_{2,\infty}(\sqrt{KN}) , the following refined upper bound holds: m(X_{N};p;1/2,3/2)\leq C_{p}\Phi_{p}(KN) , where \Phi_{p}(t):=\begin{cases}t\log t,&\ \ \text{if $p=1$, $2$},\\ t(\log t)(\log\log t)^{2},&\ \ \text{if $12 under the (p,\infty) -Nikol’skii inequality X_{N}\in\textnormal{NI}_{p,\infty}((KN)^{1/p}) was studied in [ 36 ] as well, where the results were further improved for p>3 in [ 17 ] . Combining Theorem 6.1 with Lewis’ change of density lemma (see Lemma 4.13 ), and following the proof of Corollary 4.14 , we obtain the following weighted discretization result. Corollary 6.2 . Given 1\leq p\leq 2 , 0<\epsilon\leq\frac{1}{2} and any N -dimensional subspace X_{N}\subset L_{p}(\Omega,\mu) , there are a finite set of points \{\xi^{1},\ldots,\xi^{m}\}\subset\Omega with m\leq C_{p}(\epsilon)\Phi_{p}(KN) and a set of nonnegative weights \{\lambda_{j}\}_{j=1}^{m} such that for any f\in X_{N} , {(1-\epsilon)\|f\|_{L_{p}(\Omega,\mu)}^{p}\leq\sum_{j=1}^{m}\lambda_{j}|f(\xi^{j})|^{p}\leq(1+\epsilon)\|f\|_{L_{p}(\Omega,\mu)}^{p},} where \Phi_{p} is given in ( 6.2 ), C_{p}(\epsilon)=C\epsilon^{-2} for p=1,2 , and C_{p}(\epsilon)=C_{p}\epsilon^{-2}\log^{3}\frac{1}{\epsilon} for 10 . The first results on discretization of the uniform norm were obtained by Bernstein [ 4 , 5 ] (see also [ 67 ] , Ch.10, Theorem (7.28)). In recent years this problem has been extensively studied in various settings (e.g. see [ 16 , 30 , 32 , 35 ] ). We will focus on recent progress on sampling discretization of L_{\infty} norm. We refer to the surveys [ 15 , 31 ] and the references therein for historical comments on this problem. 7.1 General bounds of m(X_{N};\infty;C) with C being independent of N We start with the following general well-known result (see, e.g., [ 30 , Theorem 1.3] ), which in particular gives the exponential upper bound m(X_{N};\infty;2)\leq 9^{N} . Theorem 7.1 . 1 1 1 One of the referees kindly pointed out that the bound in this theorem can be improved from (1+\frac{8}{\epsilon})^{N} to (1+\frac{4}{\epsilon})^{N} by working with an (\epsilon/2) -net for the set of the extreme points of the unit ball of the dual space. Let X_{N} be an N -dimensional subspace of L_{\infty}(\Omega) . Given any \epsilon\in(0,1] , there exists a sequence \left\{\xi^{j}\right\}_{j=1}^{m} of m\leq\bigl(1+\frac{8}{\epsilon}\bigr)^{N} points in \Omega satisfying \max_{x\in\Omega}|f(x)|\leq(1+\epsilon)\max_{1\leq j\leq m}\left|f\left(\xi^{j}\right)\right|,\ \ \forall f\in X_{N}. (7.2) Proof. Using ( 4.2 ), we can find a finite sequence \{f_{j}\}_{j=1}^{m}\subset B:=\{f\in X_{N}:\ \|f\|_{L_{\infty}(\Omega)}\leq 1\}\ \ \text{with}\ \ m\leq\Bigl(1+\frac{8}{\epsilon}\Bigr)^{N} such that B\subset\bigcup_{j=1}^{m}(f_{j}+\frac{\epsilon}{4}B) . For each 1\leq j\leq m , let \xi^{j}\in\Omega be such that |f_{j}(\xi^{j})|=\|f_{j}\|_{L_{\infty}(\Omega)} . For any f\in X_{N} with \|f\|_{L_{\infty}(\Omega)}=1 , we can find an integer 1\leq j\leq m such that \|f_{j}-f\|_{L_{\infty}(\Omega)}\leq\frac{\epsilon}{4} , which implies \|f\|_{L_{\infty}(\Omega)}\leq\|f_{j}\|_{L_{\infty}(\Omega)}+\frac{\epsilon}{4}\leq|f(\xi^{j})|+\frac{\epsilon}{2}\|f\|_{L_{\infty}(\Omega)}. The estimate ( 7.2 ) then follows since (1-\frac{\epsilon}{2})^{-1}\leq 1+\epsilon . ∎ Theorem 7.1 establishes an exponential upper bound in the dimension N for the number of points required to discretize the uniform norm in X_{N} . In general, the discretization ( 7.1 ) of the uniform norm in X_{N} with a constant C independent of N may not be possible unless the number m of required points grows exponentially with N (see, e.g., [ 32 ] and [ 30 , Theorem 1.2] ). More precisely, the following result (see [ 32 ] ), which complements Theorem 7.1 , shows that there exists an N -dimensional subspace X_{N}\subset C[0,2\pi] for which m(X_{N};\infty;C)\geq(N/e)e^{cN/C^{2}}\ \ \text{with $c>0$ being an absolute constant}. Theorem 7.2 ( [ 32 ] ) . Let X_{N}:=\operatorname{span}\bigl\{e^{ik_{j}x}\colon j=1,2,\ldots,N\bigr\} , where \left\{k_{j}\right\}_{j=1}^{N} is a lacunary sequence of positive integers satisfying that k_{1}=1 and k_{j+1}\geq bk_{j} , j=1,2,\ldots,N-1 for some constant b>1 . If there exist a sequence \left\{\xi^{j}\right\}_{j=1}^{m}\subset[0,2\pi) of m points and a constant C>0 such that \max_{x\in[0,2\pi]}|f(x)|\leq C\max_{j}\left|f\left(\xi^{j}\right)\right|,\quad\forall f\in X_{N}, then one must have m\geq(N/e)e^{cN/C^{2}} with a positive constant c which may only depend on b . 7.2 Estimates of m(X_{N};\infty;C_{N}) with C_{N} being dependent on N Theorems 7.1 and 7.2 provide upper and lower estimates of the number of sample points needed for the discretization inequality ( 7.1 ) with C being independent of N . We now mention some results, where the discretization constant C in ( 7.1 ) is allowed to depend on N . In the classical setting of univariate algebraic and trigonometric polynomials, this problem was extensively studied (see, e.g., [ 11 , 26 ] ). However, as is customary in this survey, our goal is to consider a more general framework of abstract finite-dimensional spaces. We start with the following result, which is well known for \ell=1 (see [ 53 , Proposition 1.2.3] ). Theorem 7.3 . Let X_{N} be an N -dimensional real subspace of \mathcal{C}(\Omega) . Given a positive integer \ell , let X_{N}(\ell):=\operatorname{span}\Bigl\{f_{1}f_{2}\ldots f_{\ell}:\ \ f_{1},\ldots,f_{\ell}\in X_{N}\Bigr\}, and N_{\ell}:=\dim X_{N}(\ell) . Then there exists a set \left\{\xi^{j}\right\}_{j=1}^{N_{\ell}} of points in \Omega such that \max_{x\in\Omega}|f(x)|\leq(N_{\ell})^{\frac{1}{\ell}}\max_{1\leq j\leq N_{\ell}}\left|f\left(\xi^{j}\right)\right|,\ \ \ \forall f\in X_{N}. Proof. Given a basis \{\varphi_{1},\ldots,\varphi_{N_{\ell}}\}\subset X_{N}(\ell) of X_{N}(\ell) , we define a function \Delta:\Omega^{N_{\ell}}\to\mathbb{R} by \Delta(x_{1},x_{2},\ldots,x_{N_{\ell}}):=\det\left[\begin{matrix}\varphi_{1}(x_{1})&\varphi_{2}(x_{1})&\cdots&\varphi_{N_{\ell}}(x_{1})\\ \varphi_{1}(x_{2})&\varphi_{2}(x_{2})&\cdots&\varphi_{N_{\ell}}(x_{2})\\ \vdots&\vdots&\cdots&\vdots\\ \varphi_{1}(x_{N_{\ell}})&\varphi_{2}(x_{N_{\ell}})&\cdots&\varphi_{N_{\ell}}(x_{N_{\ell}})\end{matrix}\right] for x_{1},\ldots,x_{N_{\ell}}\in\Omega . Since \Delta is a continuous function on the compact set \Omega^{N_{\ell}} , there must exist \xi^{1},\ldots,\xi^{N_{\ell}}\in\Omega such that \Delta(\xi^{1},\ldots,\xi^{N_{\ell}})\equiv\Delta_{N,\ell}:=\max_{x_{1},\ldots,x_{N_{\ell}}\in\Omega}\Delta(x_{1},\ldots,x_{N_{\ell}}). It is easily seen that \Delta_{N,\ell}>0 . For 1\leq j\leq N_{\ell} , define L_{j}:\Omega\to\mathbb{R} by L_{j}(x)=\frac{\Delta(\xi^{1},\ldots,\xi^{j-1},x,\xi^{j+1},\ldots,\xi^{N_{\ell}})}{\Delta_{N,\ell}},\ \ x\in\Omega. Clearly, L_{j}\in X_{N}(\ell) , L_{j}(\xi^{k})=\delta_{k,j} and \|L_{j}\|_{L_{\infty}(\Omega)}=1 for 1\leq j,k\leq N_{\ell} . Moreover, for each f\in X_{N} , we have \bigl(f(x)\bigr)^{\ell}=\sum_{j=1}^{N_{\ell}}f(\xi^{j})^{\ell}L_{j}(x),\ \ x\in\Omega. This implies that for each f\in X_{N} , \|f\|_{L_{\infty}(\Omega)}^{\ell}\leq N_{\ell}\max_{1\leq j\leq N_{\ell}}|f(\xi^{j})|^{\ell}\implies\|f\|_{L_{\infty}(\Omega)}\leq(N_{\ell})^{\frac{1}{\ell}}\max_{1\leq j\leq N_{\ell}}|f(\xi^{j})|. This completes the proof. ∎ We give a few remarks on Theorem 7.3 . Remark 7.4 . (i) Of particular interest is the case when \ell=1 , where Theorem 7.3 gives the discretization inequality with the minimum number of points: \max_{x\in\Omega}|f(x)|\leq N\max_{1\leq j\leq N}\left|f\left(\xi^{j}\right)\right|,\ \ \ \forall f\in X_{N}. (7.3) Using the notation introduced in the beginning of this section, this implies m(X_{N};\infty;N)=N . This is a well known result, for which the above proof can be found in the book of E. Novak [ 53 , Proposition 1.2.3] . (ii) For any positive integer \ell , we have N_{\ell}\leq\binom{N-1+\ell}{\ell}\leq\Bigl(\frac{e(N-1+\ell)}{\ell}\Bigr)^{\ell}. However, in many cases, this last estimate is far from being optimal. For example, if X_{N}=\Pi_{n}^{d} is the space of all algebraic polynomials of total degree at most n in d variables, and \Omega is a compact subset of \mathbb{R}^{d} with nonempty interior, then N=\dim\Pi_{n}^{d}=\binom{n+d}{d}\ \ \text{ and }\ \ N_{\ell}\leq\dim\Pi_{n\ell}^{d}. As a result, we have \frac{N_{\ell}}{N}\leq\frac{\binom{n\ell+d}{d}}{\binom{n+d}{d}}=\frac{(n\ell+d)(n\ell+d-1)\cdots(n\ell+1)}{(n+d)(n+d-1)\cdots(n+1)}=\ell^{d}\prod_{j=1}^{d}\frac{n+\frac{j}{\ell}}{n+j}\leq\ell^{d}. Assume in addition that n\geq d^{2} and d\geq 2 . Then N=\prod_{j=1}^{d}\Bigl(1+\frac{n}{j}\Bigr)\geq\Bigl(1+\frac{n}{d}\Bigr)^{d}\geq d^{d}. Now we specify the integer \ell\in\mathbb{N} such that \log N-1\leq\ell<\log N. Then \ell\geq d\log d-1 , N_{\ell}\leq\ell^{d}N\leq N(\log N)^{d}, and N_{\ell}^{\frac{1}{\ell}}\leq(\ell^{d}N)^{\frac{1}{\ell}}=\exp\Bigl(\frac{d}{\ell}\log\ell+\frac{1}{\ell}\log N\Bigr)\leq C_{1}, where C_{1}>0 is an absolute constant (independent of d ). Thus, Theorem 7.3 provides a set \{\xi^{j}\}_{j=1}^{m} of m\leq N_{\ell}\leq N(\log N)^{d} points in \Omega such that \max_{x\in\Omega}|f(x)|\leq C_{1}\max_{1\leq j\leq m}|f(\xi^{j})|,\ \ \forall f\in X_{N}=\Pi_{n}^{d}. This last estimate was previously established in [ 6 , Proposition 23] , with implicit constants depending on d . 2 2 2 We are grateful to the referee for noting that the implicit constants can be made dimension-free, rather than depending on d as they did in the previous draft. If the number of sampling points m is relaxed to be of order N rather than exactly equal to N , one can prove a refinement of the discretization inequality ( 7.3 ), in which the constant N is improved to C\sqrt{N} . We state the following result, which follows directly from the proof of Theorem 2 of [ 38 ] . Theorem 7.5 ( [ 38 , Theorem 2] ) . Given any real N -dimensional subspace X_{N} of {\mathcal{C}}(\Omega) and any \epsilon\in(0,1] , there exists a set \{\xi^{j}\}_{j=1}^{m}\subset\Omega of m\leq(1+\epsilon)(N+1) points such that \max_{x\in\Omega}|f(x)|\leq C\sqrt{N}\epsilon^{-1}\max_{1\leq j\leq m}|f(\xi^{j})|, where C>0 is an absolute constant. For completeness, we include the proof from [ 38 ] below. The argument relies on Theorem 3.12 and the following result by J. Kiefer and J. Wolfowitz [ 33 ] . Lemma 7.6 ( [ 33 ] ) . Given a real N -dimensional subspace X_{N} of \mathcal{C}(\Omega) , there exists a probability measure \mu on \Omega such that for any f\in X_{N} , \max_{x\in\Omega}|f(x)|\leq\sqrt{N}\|f\|_{L_{2}(\mu)}. Proof of Theorem 7.5 . Let X_{N+1}=\operatorname{span}\,\big(X_{N}\cup\{1\}\big) . Clearly, \dim X_{N+1}\leq N+1 . Applying Lemma 7.6 to the space X_{N+1} instead of X_{N} , we can find a probability measure \mu on X_{N+1} for which \max_{x\in\Omega}|f(x)|\leq\sqrt{N+1}\|f\|_{L_{2}(\mu)},\ \ \forall f\in X_{N+1}. By Theorem 3.12 applied to b=1+\epsilon and the space X_{N+1}\subset L_{2}(\mu) , there exist a set \{\xi^{j}\}_{j=1}^{m}\subset\Omega of m\leq(1+\epsilon)(N+1) points and a sequence \{\lambda_{j}\}_{j=1}^{m} of non-negative weights such that \|f\|_{L_{2}(\mu)}\leq\Bigl(\sum_{j=1}^{m}\lambda_{j}|f(\xi^{j})|^{2}\Bigr)^{1/2}\leq C\epsilon^{-1}\|f\|_{L_{2}(\mu)},\ \ \forall f\in X_{N+1}. Since the constant function 1 belongs to the space X_{N+1} , this implies that (\sum_{j=1}^{m}\lambda_{j})^{\frac{1}{2}}\leq C\epsilon^{-1}. It then follows from Lemma 7.6 that for any f\in X_{N} , \displaystyle\max_{x\in\Omega}|f(x)| \displaystyle\leq\sqrt{N+1}\|f\|_{L_{2}(\mu)}\leq\sqrt{N+1}\Bigl(\sum_{j=1}^{m}\lambda_{j}|f(\xi^{j})|^{2}\Bigr)^{1/2} \displaystyle\leq\sqrt{N+1}\max_{1\leq j\leq m}|f(\xi^{j})|\Bigl(\sum_{j=1}^{m}\lambda_{j}\Bigr)^{1/2}\leq C\epsilon^{-1}\sqrt{N}. ∎ Replacing Theorem 3.12 with Corollary 3.10 in the argument above yields the following result. Theorem 7.7 . Given any N -dimensional subspace X_{N} of {\mathcal{C}}(\Omega) and any \epsilon\in(0,1) , there exists a set \{\xi^{j}\}_{j=1}^{m}\subset\Omega of m\leq C\epsilon^{-2}N points such that \displaystyle\max_{x\in\Omega}|f(x)| \displaystyle\leq(1+\epsilon)\sqrt{N}\max_{1\leq j\leq m}|f(\xi^{j})|, where C>1 is an absolute constant. We point out that Theorems 7.5 and 7.7 were proved in [ 30 , Theorem 6.6] and [ 35 ] under the extra condition X_{N}\in\textnormal{NI}_{2,\infty}(H) for some constant H>0 . F. Dai Department of Mathematical and Statistical Sciences University of Alberta, Edmonton, Alberta T6G 2N8, Canada fdai@ualberta.ca E. Kosov Centre de Recerca Matemàtica, Campus de Bellaterra Edifici C 08193 Bellaterra (Barcelona), Spain. kosoved09@gmail.com V.N. Temlyakov Steklov Mathematical Institute of Russian Academy of Sciences, Moscow, Russia; Lomonosov Moscow State University; Moscow Center of Fundamental and Applied Mathematics; University of South Carolina, USA. temlyakovv@gmail.com