7 Discretization of the uniform norm and the \(L_p\)-norms
Let \(\Omega \) be an arbitrary set, \(\iota \) a finite nonempty index set with \(m = \# \iota \) elements, and \(a = (a_k)_{k \in \iota }\) a family of bounded functions \(\Omega \to \mathbb {C}\) whose coordinate functions are linearly independent. The theorem of Kiefer and Wolfowitz [ 4 ] gives a finitely supported probability measure on \(\Omega \) whose \(L_2\) norm dominates the uniform norm on the span with the constant \(\sqrt{m + \varepsilon }\) (Theorem 7.1); the complex and non-compact case is treated in [ 5 ] . Thinned with the one-sided discretization, the measure becomes \(n \geq m\) equally weighted points (Theorem 7.2), and its mixture with a probability measure \(\mu \), thinned in the same way, discretizes all \(L_p(\mu )\)-norms at once (Corollary 7.4).
Let \(\iota \) be a finite nonempty index set with \(m = \# \iota \) elements, let \(\Omega \) carry a measurable structure, let \(a = (a_k)_{k \in \iota }\) be bounded measurable functions on it with linearly independent coordinate functions, and let \(\varepsilon {\gt} 0\). Then there is a finitely supported probability measure \(\varrho = \sum _{k=1}^N w_k \delta _{x_k}\) on \(\Omega \) whose Gram matrix \(\int _\Omega a(y) a(y)^* \, d\varrho (y) = \sum _k w_k \, a(x_k) a(x_k)^*\) is positive definite and such that
for every \(y \in \Omega \) and every \(f \in \operatorname {span}\{ a_k\} \). If \(\Omega \) is a compact space whose \(\sigma \)-algebra contains the open sets and the \(a_k\) are continuous, the same holds with \(\varepsilon = 0\). In both cases \(\varrho \) can be taken with at most \(N = m^2 + 1\) atoms.
The proof is given in Section 7.1. Thinning the measure with Corollary 1.5 gives the bound with any number \(n \geq m\) of equally weighted points, the case \(p = \infty \) of Proposition 8 of [ 3 ] . For \(n = 2m\) points Krieg, Pozharska, Ullrich and Ullrich [ 5 , Theorem 2 ] prove \(\| f\| _\infty \leq 42 \bigl( \sum _{i=1}^{2m} |f(x_i)|^2 \bigr)^{1/2}\), and Proposition 8 of [ 3 ] improves the constant.
Let \(\iota \) be a finite nonempty index set with \(m = \# \iota \) elements, let \(a = (a_k)_{k \in \iota }\) be bounded functions on a set \(\Omega \) with linearly independent coordinate functions, and let \(\varepsilon {\gt} 0\). Then for every \(n \geq m\) there are points \(x_1, \dots , x_n \in \Omega \), not necessarily distinct, such that
for every \(y \in \Omega \) and every \(f \in \operatorname {span}\{ a_k\} \). If \(\Omega \) is a compact space and the \(a_k\) are continuous, the same holds with \(\varepsilon = 0\).
Give \(\Omega \) the \(\sigma \)-algebra of all its subsets, or the Borel sets in the compact case, and take the measure \(\varrho = \sum _k w'_k \delta _{x'_k}\) of Theorem 7.1, with the constant \(K = m + \varepsilon \), where \(\varepsilon = 0\) in the compact case, and positive definite Gram matrix \(G\). On the index set \(\{ 1, \dots , N\} \) the weights define the probability measure \(\sum _k w'_k \delta _k\), with respect to which the family \(k \mapsto a(x'_k)\) has Gram matrix \(G\) and \(|f(x'_k)|^2\) has integral \(\sum _k w'_k |f(x'_k)|^2 = \int _\Omega |f|^2 \, d\varrho \). Corollary 1.5 for this family gives \(n\) indices, that is points \(x_1, \dots , x_n\) of \(\varrho \), with
for every \(f \in \operatorname {span}\{ a_k\} \), and \(r {\lt} 1\) because \(n \geq m\). The bound of Theorem 7.1 finishes: \(|f(y)|^2 \leq K \int _\Omega |f|^2 \, d\varrho \leq K (1 - r)^{-2} \frac{1}{n} \sum _i |f(x_i)|^2\).
For \(n = 2m\) one has \(r {\lt} 1/\sqrt{2}\), hence \((1 - r)^{-2} / (2m) {\lt} (1 + \sqrt{2})^2 / m\), and
the uniform norm on the span is dominated by the Euclidean norm of \(2m\) sample values. Since \(r {\lt} 1/\sqrt{2}\) is strict, a small enough \(\varepsilon \) gives the constant \(1 + \sqrt{2}\) of [ 3 ] itself.
An average is at most the largest of its terms, so the same points control the uniform norm by the largest sample value. For \(n = m\) points such a bound is due to Novak [ 7 , Lemma 1.2.2 ] , a form of Auerbach’s lemma, which gives points with \(\| f\| _\infty \leq (m + \varepsilon ) \max _{1 \leq i \leq m} |f(x_i)|\).
Let \(\iota \) be a finite nonempty index set with \(m = \# \iota \) elements, let \(a = (a_k)_{k \in \iota }\) be bounded functions on a set \(\Omega \) with linearly independent coordinate functions, and let \(\varepsilon {\gt} 0\). Then for every \(n \geq m\) there are points \(x_1, \dots , x_n \in \Omega \), not necessarily distinct, such that
for every \(y \in \Omega \) and every \(f \in \operatorname {span}\{ a_k\} \). If \(\Omega \) is a compact space and the \(a_k\) are continuous, the same holds with \(\varepsilon = 0\).
Take the points of Theorem 7.2: the average \(\frac{1}{n} \sum _{i=1}^n |f(x_i)|^2\) is at most its largest term (Discretization.inv_mul_sum_le_iSup).
For \(n = 2m\) points and a small enough \(\varepsilon \) this gives the bound of [ 3 ] ,
Between \(p = 2\), Corollary 1.5, and \(p = \infty \) lie the \(L_p\)-norms, Proposition 8 of [ 3 ] . The paper takes \(n\) points for \(\mu \) and \(n\) for the measure of Theorem 7.1; the mixture \((\mu + \varrho )/2\) serves both with \(n\) points.
Let \((\Omega , \mu )\) be a probability space, let \(\iota \) be a finite nonempty set with \(m = \# \iota \) elements, and let \(a = (a_k)_{k \in \iota }\) be bounded measurable functions on \(\Omega \) with positive definite Gram matrix \(\int _\Omega a(x) a(x)^* \, d\mu (x)\). Then for every \(n \geq m\) there are points \(x_1, \dots , x_n \in \Omega \), not necessarily distinct, with
for every \(f \in \operatorname {span}\{ a_k\} \) and every \(2 \leq p \leq \infty \).
Put \(r = \sqrt{(m-1)/n}\) and \(s = 1 - r\). First, \(0 {\lt} \kappa {\lt} s\): the term \(1 - \sqrt{m/n}\) lies below \(s\) because \(m - 1 {\lt} m\), and \(1/(2m) {\lt} s\) because \(r \leq \sqrt{(m-1)/m}\) and \((1 - \frac{1}{2m})^2 = \frac{m-1}{m} + \frac{1}{4m^2}\). Put \(\varepsilon = m (s^2/\kappa ^2 - 1) {\gt} 0\), so that \(\kappa ^2 (m + \varepsilon ) = m s^2\).
The functions \(a_k\) are linearly independent on \(\Omega \): if \(f = 0\) everywhere, then \(\int _\Omega |f|^2 \, d\mu = c^* I c = 0\) by Lemma 3.1(a), so \(c = 0\). Let \(\varrho \) be the measure of Theorem 7.1 for this \(\varepsilon \), with positive definite Gram matrix and \(|f(y)|^2 \leq (m + \varepsilon ) \int _\Omega |f|^2 \, d\varrho \) at every point. The mixture \(\nu = (\mu + \varrho )/2\) is a probability measure whose Gram matrix, the mean of the two, is positive definite, and the bounded functions \(a_k\) are square-integrable for it. Corollary 1.5 for \(\nu \) gives points \(x_1, \dots , x_n\) with
For \(p = \infty \): \(\kappa ^2 |f(y)|^2 \leq \kappa ^2 (m + \varepsilon ) B \leq m s^2 (A + B) \leq m X\). For \(2 \leq p {\lt} \infty \) put \(q = p/2 - 1 \geq 0\). Since \(|f(y)|^2 \leq (m + \varepsilon ) B\) at every point, \(|f|^p \leq ((m + \varepsilon ) B)^q |f|^2\), and integration against \(\mu \) gives \(\int _\Omega |f|^p \, d\mu \leq ((m + \varepsilon ) B)^q A\). With \(B^q A \leq (A + B)^{q+1}\) and \(\kappa \leq s\),
and \(q + 1 = p/2\). In Lean the finite \(p\) are stated for the \(p\)-th powers and \(p = \infty \) at every point.
For \(n = 2m\) one has \(\kappa \geq 1 - 1/\sqrt{2}\), hence