| Russian Mathematical Surveys |
|
|
|
|
|
One-sided discretization inequalities and sampling recovery I. V. Limonovaabc, Yu. V. Malykhinab, V. N. Temlyakovabcd a Steklov Mathematical Institute of Russian Academy of Sciences, Moscow b Lomonosov Moscow State University c Moscow Center for Fundamental and Applied Mathematics d University of South Carolina, Columbia, SC, USA
Russian version:
Uspekhi Matematicheskikh Nauk, 2024, Volume 79, Issue 3(477), DOI: https://doi.org/10.4213/rm10175 
Bibliographic databases:
   1. IntroductionThere has been a significant progress in the study of the sampling discretization of integral norms for both a fixed finite-dimensional function space and a finite collection of such function spaces (universal discretization). Sampling discretization results turn out to be very useful in various applications, particularly in sampling recovery. For recent results on sampling recovery we refer the reader to [4], [27], [28], [34], [45], [3], [18], [48], [30], [17], [14], [9]–[11], [1], [25], [26], [46], [24], [47], and [40]. The systematic study of sampling discretization of the $L_p$-norms of functions in finite-dimensional subspaces begun in 2017 in [42] and [43]. First results in this direction were obtained in the 1930s and go back to Bernstein, Marcinkiewicz, and Zygmund. At the moment, this area has developed into a vast and actively growing field of research with deep connections with other important areas of research. There are two survey papers [7] and [20] on the topic. The paper [7] covers results on exact weighted discretization, discretization of the uniform norm of multivariate trigonometric polynomials, and some results on universal discretization. The paper [20] covers recent results on sampling discretization and discusses in detail their connections with other areas of research, in particular, with the theory of moments of random vectors, the theory of submatrices with good properties, embedding of finite-dimensional subspaces, sparse approximation, learning theory, and sampling recovery. Recently, in a number of papers it was understood that results on sampling discretization and universal sampling discretization can be used successfully in the problem of sampling recovery. Moreover, it turns out that it is sufficient to only have a one-sided discretization inequality for some of these applications. This motivated us to write the present paper on one-sided discretization inequalities and their applications to sampling recovery. In this sense our paper complements the survey papers [7] and [20]. Let $(\Omega,\mu)$ be a probability space. We consider measurable functions that are defined at each point of $\Omega$, and we do not identify functions which are different on a set of zero measure (see [20], § 2, for a justification). By the $L_p$-norm, $1\leqslant p< \infty$, we understand
$$
\begin{equation*}
\|f\|_p:=\|f\|_{L_p(\Omega,\mu)}:= \biggl(\int_\Omega |f|^p\,d\mu\biggr)^{1/p}.
\end{equation*}
\notag
$$
By the $L_\infty$-norm we understand the uniform norm of bounded functions and with some abuse of notation we write occasionally $L_\infty(\Omega)$ for the space $\mathcal{B}(\Omega)$ of bounded functions on $\Omega$. In §§ 5 and 6 it is convenient for us to assume that $\Omega$ is a compact subset of $\mathbb{R}^d$ and to consider the space $\mathcal{C}(\Omega)$ of continuous functions instead.We also consider the discrete space $L_p^m$ of vectors $\mathbf{x}=(x_1,\dots,x_m)\in\mathbb{R}^m$ (or $\mathbb C^m$) with the norm
$$
\begin{equation}
\|{\mathbf x}\|_p:=\begin{cases} \biggl(\dfrac{1}{m}\displaystyle\sum_{j=1}^m|x_j|^p\biggr)^{1/p},& 1\leqslant p<\infty, \\ \displaystyle\max_{1\leqslant j\leqslant m}|x_j|,& p=\infty. \end{cases}
\end{equation}
\tag{1.1}
$$
This norm is less frequently used than the $\ell_p^m$-norm (without weights $1/m$) but it is more convenient in our context. Given a sequence of points $\xi^1,\dots,\xi^m\in\Omega$, we can associate with any function $f$ defined on $\Omega$ the sampling vector The previous papers on discretization were focused on two-sided inequalities, which establish that the discrete norm of a sample vector is bounded below and above by the integral $L_p$-norm of the function (multiplied by some constants). Inequalities of this type are also known under the name of Marcinkiewicz–Zygmund inequalities. Let us describe them in more detail. The Marcinkiewicz-type discretization problemLet $(\Omega,\mu)$ be a probability space. We say that a linear subspace $X_N$ (here the index $N$ usually denotes the dimension of $X_N$) of $L_p(\Omega,\mu)$, $1\leqslant p < \infty$, admits the Marcinkiewicz-type discretization theorem with parameters $m\in \mathbb{N}$ and $p$ and positive constants $C_1\leqslant C_2$ if there exists a set $\{\xi^j\}_{j=1}^m\subset\Omega$ such that for any $f\in X_N$ we have
$$
\begin{equation}
C_1\|f\|_p^p \leqslant \frac{1}{m} \sum_{j=1}^m |f(\xi^j)|^p \leqslant C_2\|f\|_p^p.
\end{equation}
\tag{1.3}
$$
The following problem is considered: for which $m$ does a given subspace $X_N$ admit the Marcinkiewicz-type discretization inequality (1.3)? The Bernstein-type discretization problemIn the case $p=\infty$ we define $L_\infty$ as the space of bounded functions on $\Omega$, and we ask for the following inequality to hold:
$$
\begin{equation}
C_1\|f\|_\infty \leqslant \max_{1\leqslant j\leqslant m} |f(\xi^j)| \leqslant \|f\|_\infty \quad \forall\,f\in X_N.
\end{equation}
\tag{1.4}
$$
Recently it was established that results on sampling discretization and on universal sampling discretization of the square norm are useful in sampling recovery (see [45]) and in sparse sampling recovery (see [9] and [11]) with error measured in the square norm. It was discovered that in some cases it is sufficient to impose a one-sided sampling discretization assumption to prove the corresponding sampling recovery results. Inequality (1.3) consists of two one-sided inequalities: the left discretization inequality (LDI) and the right discretization inequality (RDI). In this paper we concentrate separately on LDI and on RDI. Clearly, the Bernstein-type discretization problem is an example of a one-sided discretization inequality, namely, an LDI. The RDI in (1.4) is trivial. Note that other names for one-sided inequalities are also used in the literature. For instance, Lubinsky calls RDI forward inequalities and LDI converse inequalities (see [31], for example). In this paper we focus on more general one-sided discretization inequalities between the integral $L_p$-norm of a function $f$ and the discrete $L_q^m$-norm (or weighted $\ell_q$-norm) of the vector $S(f,\xi)$. We stress that the parameters $p$ and $q$ can be different. We consider the following settings. One-sided discretization problemsGiven a probability space $(\Omega,\mu)$, a set $X$ of functions defined on $\Omega$, and parameters $1\leqslant p,q\leqslant \infty$, $D>0$, $m\in\mathbb{N}$, we are interested in the following properties.
In the case $q=\infty$ the discrete norm in (1.5) or (1.6) is understood as usual; see (1.1). Note that in the definitions of LDI and RDI we allow some of the points $\xi^1,\dots,\xi^m$ to coincide. By some abuse of notation we will write $\xi = \{\xi^j\}_{j=1}^m$ bearing in mind that some elements of this set can coincide. The problem we consider here is to find the smallest integer $m\in\mathbb{N}$ such that LDI/RDI hold true for a given $N$-dimensional subspace $X_N$ or for a collection of subspaces $X_N$. One can formulate LDI/RDI in terms of the sampling operator $S(\,\cdot\,,\xi)$ acting from $L_p$ to $L_q^m$ (see (1.2)). The RDI is just the norm bound $\|S f\|_q \leqslant D\|f\|_p$ for all $f\in X$ and the LDI is the bound $\|f\|_p \leqslant D\|S f\|_q$ for all $f\in X$. We can write $\mathrm{RDI}(p,q)$ or $\mathrm{LDI}(p,q)$ if we want to emphasize the dependence on parameters. For the sake of brevity in the case $p=q$ we often use just one parameter, for example, $\mathcal{LD}(m,p,D)$ or $\mathrm{RDI}(p)$. The above inequalities (1.5) and (1.6) are formulated in the case of discretization with equal weights $1/m$ for each sample point $\xi^j$, $j=1,\dots,m$. In the case of general weights (weight $\lambda_j$ for the sample point $\xi^j$, $j=1,\dots,m$) we obtain analogues of LDI and RDI for weighted discretization, which we call WLDI:
$$
\begin{equation*}
\|f\|_p \leqslant D\biggl(\,\sum_{j=1}^m \lambda_j|f(\xi^j)|^q\biggr)^{1/q}\quad \forall\,f \in X,
\end{equation*}
\notag
$$
and WRDI:
$$
\begin{equation*}
\biggl(\,\sum_{j=1}^m \lambda_j|f(\xi^j)|^q\biggr)^{1/q} \leqslant D \|f\|_p\quad \forall\,f \in X.
\end{equation*}
\notag
$$
The $\mathcal{LD}$ and $\mathcal{RD}$ properties are almost monotone in the number of sampling points in the following sense. If $X\in\mathcal{LD}(m,p,q,D)$, then $X\in\mathcal{LD}(km,p,q,D)$ (each point is repeated $k$ times) for each $k\in\mathbb N$; moreover, $X\in\mathcal{LD}(m',p,q,2^{1/q}D)$ for all $m'>m$. In fact, if $m'\leqslant 2m$, then consider $m$ points ensuring the membership relation $X\in\mathcal{LD}(m,p,q,D)$ and repeat $m'-m$ of them. Then the $l_q^m$-norms of functions do not decrease and the normalizing factor $1/m^{1/q}$ reduces with coefficient $(m'/m)^{1/q}\leqslant 2^{1/q}$; we obtain $X\in\mathcal{LD}(m',p,q,2^{1/q}D)$. The general case reduces to this in view of the first observation. The same holds for RDI. Hence if we do not care about multiplicative absolute constants, then there is no difference between, say, the property
$$
\begin{equation*}
`X\in\mathcal{LD}(m,p,q,C_2)\quad\text{for some } m\leqslant C_1N\log N\text{'}
\end{equation*}
\notag
$$
and (in the last expression we even allow the noninteger first parameter $C_1N\log N$ and assume that the number of points is $[C_1N\log N]$). The structure of the paperNow we present a brief description of our results. In § 2 we mostly study the right discretization inequality. We focus on lower bounds for $m$ such that $\mathcal{RD}(m,p, q, D)$ is possible. In Proposition 2.1 we discuss the case when $2<p<\infty$ and $1\leqslant q<\infty$ and obtain a lower bound on $m$ for an RDI to hold under certain assumptions on the subspace $X_N$. As a corollary of this lower bound (see Corollary 2.1), we establish that for a subspace $\mathcal{T}(\Lambda_N)$ spanned by a lacunary trigonometric system of size $N$ to have the RDI in the case $2<q<\infty$ it is necessary to use at least $N^{q/2}$ points in the sense of order. We show (see Remark 2.2) that for an LDI to hold for the subspace $\mathcal{T}(\Lambda_N)$ it is sufficient to use points in amount of order $N$. Also, we prove (see Proposition 2.3) that if the sampling operator is injective, then there is no universal bound on $m$ in terms of $N$, which guarantees RDI for all $N$-dimensional subspaces. In § 3 we discuss LDI. We show that a weighted LDI with non-negative weights implies an LDI (see Proposition 3.1). As a consequence, we obtain (see Proposition 3.2) that for any $N$-dimensional subspace the $\mathrm{LDI}(2)$ holds for the number $m$ of points being of order $N$. We also formulate an open problem. In § 4 we discuss a connection between sampling discretization problems and known settings on finding submatrices of small size with certain good properties. In particular, we explain that the $\mathrm{RDI}(2)$ with $m=N$ points is a corollary of Lunin’s result on matrices. In § 5 we discuss the problem of sampling recovery. It is mostly a survey of known results with simple comments on their improvements. Here the case $p\ne q$ is important. For instance, it turns out that some of the sampling recovery results which were proved using the $\mathrm{LDI}(p,p)$ can also be proved under the weaker assumption $\mathrm{LDI}(p,\infty)$, namely,
$$
\begin{equation}
\|f\|_p \leqslant D \max_{1\leqslant j \leqslant m} |f(\xi^j)|,
\end{equation}
\tag{1.7}
$$
where $p\in[1,\infty)$ (see Theorem 5.2). Also, we show in § 5 how known results on the discretization of the uniform norm can be combined with a result due to Kiefer and Wolfowitz [22] to obtain results on LDI. In § 6 we present a brief survey of the very recent results from [9]–[11]. In addition, in the same way as in § 5 we demonstrate that some of those results can be improved by replacing the assumption of an LDI with parameter $p$ by the weaker assumption of an $\mathrm{LDI}(p,\infty)$, $p\geqslant1$; see (1.7). In § 7 we discuss sampling discretization of the uniform norm. By its nature, sampling discretization of the uniform norm is an LDI problem because the corresponding RDI is trivial in this case. In § 7 we focus on lower bounds on $m$ for the sampling discretization result to hold. Theorem 7.1 is a new result, which extends the previously known result for the trigonometric system to the case of more general systems. Then we discuss an application of Theorem 7.1 to the case when the system in question is a Sidon system. We often use the concept of Nikol’skii’s inequality. For the reader’s convenience we formulate it here. Other definitions and notations are introduced in the text below. Nikol’skii-type inequalitiesLet $1\leqslant p\leqslant q\leqslant\infty$ and $X_N\subset L_q(\Omega)$. The inequality is called Nikol’skii’s inequality for the pair $(p,q)$ with constant $M$. We will also use a brief form of this relation, $X_N \in \mathrm{NI}(p,q,M)$. Typically, $M$ depends on $N$, for instance, $M$ can be of order $N^{1/p-1/q}$.2. Right discretization inequalities (RDI)In this section we mostly discuss necessary conditions on $m$ for RDI and WRDI to hold. We begin with weighted discretization. Lemma 2.1. Let $2<p<\infty$ and $1\leqslant q<\infty$, and let $X_N\in\mathrm{NI}(2,p,M)$ for some constant $M$. Assume that $\{\xi^j\}_{j=1}^m\subset \Omega$ and non-negative weights $\{\lambda_j\}_{j=1}^m$ are such that for any $f\in X_N$ Then for any orthonormal basis $\{u_i\}_{i=1}^N$ of $X_N$ and any $j\in \{1,\dots,m\}$ we have Proof. It is well known and easy to check that for any $\omega\in\Omega$
$$
\begin{equation}
\biggl(\,\sum_{i=1}^N|u_i(\omega)|^2\biggr)^{1/2}= \sup_{f\in X_N\colon\|f\|_2\leqslant 1}|f(\omega)|.
\end{equation}
\tag{2.2}
$$
Using the trivial bound $\lambda_j|f(\xi^j)|^q \leqslant \sum_{k=1}^m\lambda_k |f(\xi^k)|^q$, from (2.2) we obtain
$$
\begin{equation*}
\lambda_j\biggl(\,\sum_{i=1}^N |u_i(\xi^j)|^2\biggr)^{q/2} \leqslant \sup_{f\in X_N\colon\|f\|_2\leqslant 1}\,\sum_{k=1}^m \lambda_k|f(\xi^k)|^q.
\end{equation*}
\notag
$$
By (2.1) and our assumption about Nikol’skii’s inequality we see that the right-hand side is at most
$$
\begin{equation*}
\sup_{f\in X_N\colon\|f\|_2\leqslant 1}(D\|f\|_p)^q \leqslant (DM)^q.
\end{equation*}
\notag
$$
This completes the proof of Lemma 2.1. $\Box$ Remark 2.1. In Lemma 2.1 we assume that all weights are non-negative. But discretization with negative weights also makes sense. For instance, it was noted in [29] that even for $p=2$ there exist subspaces such that for the minimum number $m$ of points providing for each $f\in X_N$ the equality (exact discretization) we need some $\lambda_j$, $j=1,\dots, m$, to be negative. The following proposition is a direct corollary of Lemma 2.1. Proposition 2.1. Let $2<p<\infty$ and $1\leqslant q<\infty$, and let $X_N\in\mathrm{NI}(2,p,M)$ for some constant $M$. Suppose that $X_N$ has an orthonormal basis $\{u_i\}_{i=1}^N$ with the property Assume that $X_N\in\mathcal{RD}(m,p,q,D)$. Then Corollary 2.1. Let $\Lambda_N = \{k_i\}_{i=1}^N$ be a lacunary sequence: $k_{i+1}\geqslant bk_i$, $b>1$, $i=1,\dots,N-1$. Set Remark 2.2. In contrast to the RDI case, for lacunary polynomials an LDI with $2<p<\infty$ and $2<q<\infty$ can be satisfied by using $m=O(N)$ points. Indeed, by Theorem 1.1 from [42] there are $m \leqslant CN$ points $\xi^1,\dots,\xi^m$ that provide $L_2$-discretization and this immediately implies an LDI: Proposition 2.2. Let $2<p<\infty$, and let $X_N\in\mathrm{NI}(2,p,M)$ for some constant $M$. Assume that $\{\xi^j\}_{j=1}^m\subset \Omega$, and let $\{\lambda_j\}_{j=1}^m$ be non-negative weights such that for each $f\in X_N$ Then where $K_p$ is the constant from Khinchin’s inequality. Proof. Let $\{u_i\}_{i=1}^N$ be an orthonormal basis of $X_N$. Consider the functions
$$
\begin{equation*}
f(\omega,\theta):=\sum_{i=1}^N r_i(\theta)u_i(\omega),
\end{equation*}
\notag
$$
where $\{r_i(\theta)\}_{i=1}^N$ are the Rademacher functions defined on $[0,1]$. Then by our assumption (2.3), for $\theta\in [0,1]$ we obtain
$$
\begin{equation}
D_1^{-p} N^{p/2}=D_1^{-p}\|f(\,\cdot\,,\theta)\|_2^p \leqslant \sum_{j=1}^m \lambda_j |f(\xi^j,\theta)|^p.
\end{equation}
\tag{2.4}
$$
Integrating (2.4) with respect to $\theta$ and using Khinchin’s inequality we see that
$$
\begin{equation*}
D_1^{-p} N^{p/2} \leqslant \int_0^1\sum_{j=1}^m \lambda_j|f(\xi^j,\theta)|^p\,d\theta \leqslant K_p^p\sum_{j=1}^m\lambda_j\biggl(\,\sum_{i=1}^N |u_i(\xi^j)|^2\biggr)^{p/2}.
\end{equation*}
\notag
$$
Applying Lemma 2.1 for $q=p$ we find that Remark 2.3. In the case $2<p<\infty$ the condition is weaker than the two related conditions RDI with injective sampling operatorNow we make a simple observation that in the case of an injective sampling operator $f\mapsto S(f,\xi)$ there is no a priori upper bound for the number of points $m$ that provide an RDI. Given $a\in(0,1/2]$, we define a function $f_a\in C[0,1]$ by
$$
\begin{equation*}
f_a(x):=\begin{cases} 1, & 0\leqslant x\leqslant a; \\ 2-\dfrac{x}{a}\,, & a\leqslant x\leqslant 2a; \\ 0, & 2a \leqslant x\leqslant 1. \end{cases}
\end{equation*}
\notag
$$
Proposition 2.3. Let $p,q\in[1,\infty)$, and let $X_N$ be a linear subspace of $C[0,1]$ that contains the functions $f_a$ and $f_{a/2}$ for some $a\in(0,1/2]$. Suppose that a set $\{\xi^j\}_{j=1}^m\subset\Omega$ provides the property $X_N\in\mathcal{RD}(m,p,q,D)$ with injective sampling operator, that is, Then Proof. We apply the injectivity of the sampling operator to the function $f_{a/2}$ and obtain that at least one point among the $\xi^j$, $j=1,\dots, m$, lies in the interval $[0,a]$. Therefore, the $\mathrm{RDI}(p,q)$ for $f_a$ implies that The required inequality follows. $\Box$ We can take $a$ in (2.5) to be arbitrarily small and obtain arbitrarily large lower bounds for $m$. Hence there is also no upper bound for the number of points $m$ that provide Marcinkiewicz-type discretization (1.3). Note that Proposition 2.3 gives the solution to Open Problem 1 in [20]. In terms of [20] this means that for each $1\leqslant p<\infty$ and any positive constants $C_1$ and $C_2$ we have $sd(N,p,C_1,C_2) =\infty$. Note that each subspace $X_N$ admits the $\mathrm{RDI}(2,2)$ with $m=N$ points (see Proposition 4.1). This means that the injectivity condition for RDI is essential. The $\mathrm{LDI}(2,2)$ also holds with $m=O(N)$ points for each $X_N$ (see Proposition 3.2). However, we cannot guarantee both an LDI and an RDI with a common set of points of any size bounded by $m(N)$. Otherwise we would obtain an RDI with injective sampling operator, and this would contradict Proposition 2.3. Proposition 3.2 from [15] implies lower bounds on the number of points for RDI for subspaces with Nikol’skii’s inequality. We refer the reader to [15] for the construction and for the result in the case when $X_N\in \mathrm{NI}(1,\infty, (1+\varepsilon)N)$. Theorem 2.A ([15]). For any $1\leqslant q<2$ and $N\in\mathbb{N}$ there exists an $N$-dimensional subspace $X_N\subset L_1([0,1])$ with the following properties: (a) $X_N\in \mathrm{NI}(q,\infty, K_q^{-1}N^{1/q})$; (b) if $m\in\mathbb{N}$ and $t_j, j=1,\dots, m$, are such that $\sum_{j=1}^m|f(t_j)|^q>0$ for all $f\in X_N\setminus \{0\}$, then there exists $f\in X_N$ such that In particular, it follows from (2.6) that the $\mathrm{RDI}(q)$ with injective sampling operator is not true for $m=o(N^{2-q/2})$. A comment on WRDILet $2\leqslant r<p<\infty$, $X_N\in\mathrm{NI}(2,p,M)$, and let the points $\xi^1,\dots,\xi^m\in\Omega$ and weights $\lambda_1,\dots,\lambda_m\in\mathbb{R}_+$, $\lambda_1+\dots+\lambda_m=1$, be such that
$$
\begin{equation*}
\biggl(\,\sum_{j=1}^{m} \lambda_j|f(\xi^j)|^p\biggr)^{1/p}\leqslant D\|f\|_p \quad \forall\,f\in X_N.
\end{equation*}
\notag
$$
Then setting $\lambda_j = \lambda_j^{1-r/p}\lambda_j^{r/p}$, from Hölder’s inequality we obtain
$$
\begin{equation*}
\begin{aligned} \, \sum_{j=1}^{m} \lambda_j|f(\xi^j)|^r&\leqslant \biggl(\,\sum_{j=1}^{m} \lambda_j|f(\xi^j)|^p\biggr)^{r/p} \\ &\leqslant D^r\|f\|_p^r\leqslant D^r M^r\|f\|_2^r\leqslant D^r M^r\|f\|_r^r. \end{aligned}
\end{equation*}
\notag
$$
Thus, the $\mathrm{NI}(2,p, M)$ and $\mathrm{WRDI}(p)$ with a constant $D$ imply the $\mathrm{WRDI}(r)$ with the constant $DM$.
3. Left discretization inequalities (LDI)We will prove that a WLDI with non-negative weights implies an LDI if the sum of weights is bounded above. This extra property of weights is true, for example, when we have the two-sided weighted discretization. We begin with a slightly more general observation than the one in [45]. Remark 3.1. Let $\mathcal F$ be a collection of finite-dimensional subspaces such that if $X_N\in \mathcal F$, then Proposition 3.1. Let $X$ be a set of functions in $L_p(\Omega,\mu)$, and let the points $\xi^1,\dots,\xi^m \in\Omega$ and non-negative weights $\lambda_1,\dots,\lambda_m$ be such that $\lambda_1+\dots+\lambda_m\leqslant C$ and Then there exists $m_0\leqslant (C^2+1)m$ such that Proof. Set $m_0:=\sum_{i=1}^m ([\lambda_iCm]+1)$, then
$$
\begin{equation*}
m_0\leqslant \sum_{i=1}^m \lambda_iCm+m\leqslant (C^2+1)m.
\end{equation*}
\notag
$$
We construct a new set of points. We repeat each point $\xi^j$, $j=1,\dots, m$, $[\lambda_jCm]+1$ times and denote all these points by $\xi_0^j$, $j=1,\dots, m_0$. Then
$$
\begin{equation*}
\begin{aligned} \, \biggl(\,\sum_{j=1}^{m_0}\frac{1}{m_0}\,|f(\xi_0^j)|^q\biggr)^{1/q}&= \biggl(\,\sum_{j=1}^{m}\frac{[\lambda_jCm]+1}{m_0}\, |f({\xi}^j)|^q\biggr)^{1/q} \\ &\geqslant \biggl(\,\sum_{j=1}^{m} \frac{\lambda_jCm}{(C^2+1)m}\, |f({\xi}^j)|^q\biggr)^{1/q}\geqslant \frac{1}{D}\|f\|_p\biggl(\frac{C}{C^2+1}\biggr)^{1/q}. \ \Box \end{aligned}
\end{equation*}
\notag
$$
Let us apply this technique to some known theorems on discretization. Proposition 3.2. Let $1\leqslant p<\infty$. Then there exist positive constants $C_1(p)$ and $C_2(p)$ such that each $N$-dimensional subspace $X_N \subset L_p(\Omega,\mu)$ satisfies the property $X_N\in\mathcal{LD}(m, p, C_2)$, that is, there is a set of points $\{\xi^j\}_{j=1}^m$ such that where Proof. In the case $p=2$ we use the following result (see [6], Theorem 6.4): there exist three absolute constants $C_1'$, $c_0$, $C_0$, a set of $m\leqslant C_1'N$ points $\xi^1,\dots, \xi^m\in\Omega$, and a set of non-negative weights $\lambda_j$, $j=1,\dots, m$, such that
$$
\begin{equation*}
c_0\|f\|_2^2\leqslant \sum_{j=1}^m \lambda_j |f(\xi^j)|^2 \leqslant C_0\|f\|_2^2\quad \text{for all }f\in X_N.
\end{equation*}
\notag
$$
This WLDI, Remark 3.1, and Proposition 3.1 imply the required LDI.
Other cases are also covered by known discretization results: see [20], D.20. An upper bound, for $p>2$ and [5], Corollaries 1.1 and 1.2, for $1 \leqslant p < 2$. $\Box$ Remark 3.2. Note that in the papers cited discretization results are often formulated for subspaces of continuous functions $X_N\subset C(\Omega)$. However, it is always possible to discretize properly any subspace $X_N\subset L_p$ by using an appropriate amount of points (see, for example, Proposition 4.A) and pass to a subspace of functions defined on a discrete set. These functions are continuous by definition. So, the results we have cited work in the general setting. We have discovered that Proposition 3.2 for $p=2$, that is, the $\mathrm{LDI}(2,2)$
$$
\begin{equation}
\|f\|_2 \leqslant C_2\biggl(\,\sum_{j=1}^{m}\frac{1}{m}\,|f({\xi}^j)|^2\biggr)^{1/2}\quad \text{for all }f\in X_N,\quad m\leqslant C_1N,
\end{equation}
\tag{3.2}
$$
was also obtained independently in the recent paper [1], Theorem 6.2, by using a different method (see also [26], Lemma 11). Open Problem 3.1. Under what condition on $m$ does each $N$-dimensional subspace $X_N \subset \mathcal{C}(\Omega)$ have the property $X_N\in\mathcal{LD}(m,p,\infty,D)$, where $2<p<\infty$ and $D=D(p)$: with an appropriate set of points $\{\xi^j\}_{j=1}^m$? Comment 3.1. Theorem 1.3 in [19] on the discretization of the uniform norm implies that in Open Problem 3.1 we can always take $m=9^N$, which means an exponential growth in $N$. Theorem 1.2 in [19] shows that for the subspace $\mathcal{T}(\Lambda_N)$ (see Corollary 2.1) we need $(N/e)e^{CN/D^2}$ points for the $\mathrm{LDI}(\infty)$ to hold. Proposition 3.2 for $p=2$ guarantees that we can take $m$ of order $N$ in the case $p\leqslant 2$. From Proposition 3.2 it follows that we can take $m\leqslant C N^{p/2}\log{N}$ for $p>2$ and $m\leqslant CN^{p/2}$ for even $p$. The following theorem from [26] is the $\mathrm{LDI}(p,2)$. Theorem 3.1 ([26], Theorem 13). Let $2\leqslant p\leqslant \infty$. Then there exist positive constants $C_1=4$ and $C_2=83$ such that each $N$-dimensional subspace $X_N \subset \mathcal{C}(\Omega)$ satisfies the property $X_N\in\mathcal{LD}(C_1N,p,2,C_2 N^{1/2-1/p})$, that is, there is a set of $m\leqslant C_1N$ points $\{\xi^j\}_{j=1}^m$ such that Also see some results on LDI in § 5: Theorems 5.C, 5.F, 5.5, and 5.G. 4. Matrix settingThe following proposition from [15] guarantees that for any subspace $X_N$ we can find a sufficiently large number $m_0\in\mathbb{N}$ such that $X_N\in\mathcal{LD}(m_0,p,K_1)$ and $X_N\in\mathcal{RD}(m_0,p,K_2)$. Proposition 4.A ([15], Proposition 6.1). Let $1\leqslant p<\infty$, and let $X_N\subset L_p(\Omega,\mu)$ be an $N$-dimensional subspace, where $(\Omega, \mu)$ is a probability space. Then for each $\varepsilon>0$ there exists $m_0\in\mathbb{N}$ such that if $M\geqslant m_0$ and $\{\xi^j\}_{j=1}^M\subset\Omega$ are independent random samples, then with probability at least $1-\varepsilon$ By Proposition 4.A the problem of finding the smallest $m$ for which $X_N\in \mathcal{LD}(m,p,D)$ or $X_N\in\mathcal{RD}(m,p,D)$ can be reformulated in the matrix setting. Note that results similar to Proposition 4.A with extra conditions on $X_N$ were obtained in [6], Theorem 2.2. Assume that $X_N\in\mathcal{LD}(m_0,p,K_1)$:
$$
\begin{equation*}
\|f\|_p \leqslant K_1 \|S(f,\xi)\|_p,\quad \xi=\{\xi^j\}_{j=1}^{m_0}, \quad \text{for all }f\in X_N.
\end{equation*}
\notag
$$
Consider the space of sampling vectors in $\mathbb{R}^{m_0}$ with the $L_p^{m_0}$-norm (see (1.1)). If we obtain an LDI for this space:
$$
\begin{equation}
\biggl(\frac{1}{m_0}\sum_{j=1}^{m_0}|y_j|^p\biggr)^{1/p} \leqslant D\biggl(\frac{1}{m}\sum_{j=1}^m |y_{i_j}|^p\biggr)^{1/p}\quad \text{for all }{\mathbf y}=(y_1,\dots,y_{m_0})\in\widetilde{X}_N,
\end{equation}
\tag{4.2}
$$
then we obtain an LDI for the original space:
$$
\begin{equation*}
\|f\|_p \leqslant K_1 \|S(f,\xi)\|_p \leqslant K_1 D \biggl(\frac{1}{m} \sum_{j=1}^m|f(\xi^{i_j})|^p\biggr)^{1/p}\quad \text{for all }f\in X_N;
\end{equation*}
\notag
$$
hence $X_N\in\mathcal{LD}(m,p,K_1D)$. The RDI case is analogous. If $X_N\in\mathcal{RD}(m_0,p,K_2)$:
$$
\begin{equation}
\|S(f,\xi)\|_p \leqslant K_2 \|f\|_p \quad \text{for all }f\in X_N, \quad\text{where } \xi=\{\xi^j\}_{j=1}^{m_0},
\end{equation}
\tag{4.3}
$$
then an RDI for the space $\widetilde{X}_N$ provides an RDI for the original space. Therefore, it is enough to study the LDI and RDI problems for discrete systems, which can be formulated in the matrix setting. It was pointed out in the survey [20], M.1, that in that the right-hand inequality in the Marcinkiewicz-type discretization theorem (which is an RDI) for an arbitrary finite-dimensional subspace of $L_2$ follows from the paper [32] by Lunin. We show below (see Proposition 4.1) how to prove this. Recall that for spaces satisfying Nikol’skii’s inequality (1.8) for $p=2$ and $q=\infty$ both an RDI and an LDI were obtained in [30] by using some deep results from [33]. It is convenient to write the space of sampling vectors in the form
$$
\begin{equation*}
\widetilde{X}_N=\{A{\mathbf x}\colon{\mathbf x}\in\mathbb{R}^N\}
\end{equation*}
\notag
$$
with an appropriate $m_0\times N$ matrix $A$. There is a natural way to find such a matrix. Assume that a system $\{u_i\}_{i=1}^N$ forms a basis of $X_N$. Let $A$ be the matrix with columns $(u_i(\xi^1), \dots, u_i(\xi^{m_0}))^\top$, $i=1,\dots,N$. Then for $f=x_1u_1+\dots+x_Nu_N$, $\mathbf{x}=(x_1,\dots,x_N)\in\mathbb{R}^N$, we have $S(f,\xi) = A\mathbf{x}$. Let $A_1$ be an $m\times N$ submatrix of $A$ that consists of the rows with some indices $i_1,\dots,i_m$ (here we assume that the $i_j$ are distinct). Then (4.2) takes the following form:
$$
\begin{equation}
\|A{\mathbf x}\|_p\leqslant D \|A_1{\mathbf x}\|_p \quad \forall\,{\mathbf x}=(x_1,\dots,x_N)\in \mathbb{R}^N.
\end{equation}
\tag{4.4}
$$
Thus, to obtain an LDI for a discrete system it is sufficient to find a row- submatrix $A_1$ that satisfies inequality (4.4), called a pointwise estimate (see [20], § 3). The only difference between the discretization problem (4.2) and the matrix pointwise estimate (4.4) is that submatrices consist of distinct rows $i_j$ and in discretization we allow the repetition of $i_j$. Similarly, an RDI for a discrete system is essentially equivalent to the problem of finding a row-submatrix $A_1$ of the smallest possible size for which the following pointwise estimate holds
$$
\begin{equation}
\|A_1{\mathbf x}\|_p\leqslant D\|A{\mathbf x}\|_p \quad \text{for all }{\mathbf x}=(x_1,\dots,x_N)\in \mathbb{R}^N.
\end{equation}
\tag{4.5}
$$
We stress that in (4.4) and (4.5) we consider discrete $L_p^m$-norms (1.1) which are related to the usual $\ell_p^m$-norms by
$$
\begin{equation*}
\|{\mathbf z}\|_p=m^{-1/p}\|{\mathbf z}\|_{\ell_p^m}.
\end{equation*}
\notag
$$
Proposition 4.1. Let $X_N$ be an $N$-dimensional subspace of $L_2(\Omega,\mu)$, then $X_N \in \mathcal{RD}(N,2,C)$ for an absolute positive constant $C$. Proof. By Proposition 4.A inequality (4.3) holds for $p=2$, for some $m_0$ and $K_2=2$. Without loss of generality we may assume that $\dim\widetilde{X}_N=N$: see (4.1) (if the dimension is less than $N$, then we obtain an even stronger RDI with fewer points). Let $\widetilde{X}_N = \{A\mathbf{x}\colon \mathbf{x}\in\mathbb{R}^N\}$. One can take a matrix $A$ with columns orthonormal in $L_2^{m_0}$. In order to obtain an RDI we prove (4.5). By Theorem 2 in [32] there is an $N\times N$ submatrix $A_1$ of the matrix $A$ such that
$$
\begin{equation*}
\sup_{\|{\mathbf x}\|_2=1}\|A_1{\mathbf x}\|_2\leqslant C \sup_{\|{\mathbf x}\|_2=1}\|A{\mathbf x}\|_2
\end{equation*}
\notag
$$
for some absolute positive constant $C$. Using that in our case for any $\mathbf{x}\in\mathbb{R}^N$ we obtain: Therefore, $X_N\in\mathcal{RD}(N,2,2C)$. The proposition is proved. Corollary 4.1. Let $p\in\mathbb{N}$ be an even integer; then $X_N \in \mathcal{RD}(N^{p/2},p,C^{2/p})$. We define the operator $(r,p)$-norm of a matrix $A$ of size $M\times N$ by
$$
\begin{equation*}
\|A\|_{(r,p)}=\sup_{\|{\mathbf x}\|_{\ell_r^N}\leqslant 1} \|A{\mathbf x}\|_{\ell_p^M}.
\end{equation*}
\notag
$$
We note that (4.5) implies that
$$
\begin{equation}
\|A_1\|_{(r,p)}^p\leqslant D^p\,\frac{m}{m_0}\,\|A\|_{(r,p)}^p\quad\text{for}\ \ r\geqslant 1.
\end{equation}
\tag{4.6}
$$
The first results of that type were obtained by Kashin in 1980 for the operator $(2,q)$-norms of matrices in the case $1\leqslant q\leqslant 2$ (see [20], § 3, for details). If we know that (4.6) fails for each $m\times N$ submatrix $A_1$, then (4.5) does not hold. So there is a chance that there will be some negative results on the norms of submatrices that could help one to establish lower bounds on $m$ in discretization.
5. An application to sampling recoveryWe begin with a general problem of the recovery of functions in some class and describe some characteristics of optimal recovery. Recall the notion of the sampling operator (1.2). Given a fixed $m$ and a set of points $\xi^1,\dots,\xi^m\in\Omega$, we associate with a function $f\in\mathcal{C}(\Omega)$ the vector
$$
\begin{equation*}
S(f,\xi):=(f(\xi^1),\dots,f(\xi^m)) \in {\mathbb C}^m.
\end{equation*}
\notag
$$
Each linear operator $\Phi\colon {\mathbb C}^m\to L_p(\Omega,\mu)$ specifies a linear algorithm of sampling recovery: For a class of functions ${\mathbf F}\subset L_p(\Omega,\mu)$ set
$$
\begin{equation*}
\varrho_m({\mathbf F},L_p):=\inf_{\xi;\, \text{linear}\,\Phi}\, \sup_{f\in {\mathbf F}}\|f-\Phi(S(f,\xi))\|_p.
\end{equation*}
\notag
$$
This recovery procedure is linear; the following modification of it is also of interest. We allow any mapping $\Phi\colon \mathbb{C}^m \to X_m \subset L_p(\Omega,\mu)$, where $X_m$ is a linear subspace of dimension $m$, and set
$$
\begin{equation*}
\varrho_m^*({\mathbf F},L_p):=\inf_{\xi; \Phi; X_m}\, \sup_{f\in {\mathbf F}}\|f-\Phi(S(f,\xi))\|_p.
\end{equation*}
\notag
$$
In both cases above we build an approximant, which comes from a linear subspace of dimension at most $m$. It is natural to compare the quantities $\varrho_m(\mathbf{F},L_p)$ and $\varrho_m^*(\mathbf{F},L_p)$ with Kolmogorov widths of ${\mathbf F}$ in $L_p$:
$$
\begin{equation*}
d_m({\mathbf F}, L_p):=\inf_{X_m\subset L_p}\,\sup_{f\in {\mathbf F}}\, \inf_{g\in X_m}\|f-g\|_p.
\end{equation*}
\notag
$$
In the definition of Kolmogorov widths, given $f\in \mathbf{F}$, we take an approximating element of the $m$-dimensional subspace $X_m$ that is an element of best approximation to $f$. This means that, in general (that is, for $p\ne 2$), this method of approximation is nonlinear. We have the following obvious inequalities
$$
\begin{equation*}
d_m ({\mathbf F}, L_p)\leqslant \varrho_m^*({\mathbf F},L_p)\leqslant \varrho_m({\mathbf F},L_p).
\end{equation*}
\notag
$$
The characteristics $\varrho_m$, $\varrho_m^*$, and their variants are well studied for many particular classes of functions. For an exposition of the known results we refer to the books [49], [35], [13], [44], [36]–[38], and the references there. The characteristics $\varrho_m^*$ and $\varrho_m$ are inspired by the concepts of Kolmogorov width and linear width. Probably, $\varrho_m^*$ was introduced in [12], $\varrho_m$ in [41], and a variant of $\varrho_m^*$ without the condition of mapping to a linear subspace was introduced in [49]. We turn to concrete methods of recovery. Throughout the rest of the section $\Omega$ is a compact subset of $\mathbb{R}^d$; we recover continuous functions $f\in \mathcal{C}(\Omega)$ and let $X_N$ denote an $N$-dimensional subspace of ${\mathcal C}(\Omega)$. We also consider the discrete norms
$$
\begin{equation*}
\|S(f,\xi)\|_p:=\biggl(\frac{1}{m}\sum_{j=1}^m|f(\xi^j)|^p\biggr)^{1/p},\qquad 1\leqslant p<\infty,
\end{equation*}
\notag
$$
and For a positive weight $\mathbf{w}:=(w_1,\dots,w_m)\in \mathbb{R}^m$ consider the seminorm
$$
\begin{equation*}
\|S(f,\xi)\|_{p,{\mathbf w}}:= \biggl(\,\sum_{j=1}^m w_j |f(\xi^j)|^p\biggr)^{1/p},\qquad 1\leqslant p<\infty.
\end{equation*}
\notag
$$
We define the best approximation of $f\in L_p(\Omega,\mu)$, $1\leqslant p\leqslant \infty$, by elements of $X_N$ by Theorem 5.A below was proved in [45] under the following assumptions. Condition A1 (discretization). Let $1\leqslant p\leqslant \infty$. Suppose that $\xi:=\{\xi^j\}_{j=1}^m\subset \Omega$ provides the WLDI, that is, for any $u\in X_N$ in the case $p<\infty$ we have and in the case $p=\infty$ we have for some positive constant $D$. Condition A2 (weights). Suppose that there exists a positive constant $W$ such that $\sum_{j=1}^m w_j \leqslant W$. Consider the following well-known recovery operator (algorithm):
$$
\begin{equation*}
\begin{gathered} \, \ell p{\mathbf w}(\xi)(f):=\ell p{\mathbf w}(\xi,X_N)(f):= \arg\,\min_{u\in X_N}\|S(f-u,\xi)\|_{p,{\mathbf w}},\qquad 1\leqslant p<\infty, \\ \ell \infty(\xi)(f):=\ell \infty(\xi,X_N)(f):= \arg\,\min_{u\in X_N}\|S(f-u,\xi)\|_{\infty} \end{gathered}
\end{equation*}
\notag
$$
(see, for instance, [4]). Note that the above algorithm $\ell p\mathbf{w}(\xi)$ only uses the values $f(\xi^j)$, $j=1,\dots,m$, of the function. In the case $p=2$ it is a linear algorithm, that is, an orthogonal projection with respect to the seminorm $\|\,{\cdot}\,\|_{2,\mathbf{w}}$. Therefore, in the case $p=2$ the error of approximation by the algorithm $\ell\,2\mathbf{w}(\xi)$ gives us an upper bound for the recovery characteristic $\varrho_m(\,\cdot\,, L_2)$. In the case $p\ne 2$ the error of approximation by the algorithm $\ell p\mathbf{w}(\xi)$ gives us an upper bound for the recovery characteristic $\varrho_m^*(\,\cdot\,, L_p)$. Theorem 5.A (see [45], Theorem 2.1). Under Conditions A1 and A2, for any $f\in \mathcal{C}(\Omega)$ and $1\leqslant p<\infty$ We now prove a version of Theorem 5.A for the error $\|f-\ell p\mathbf{w}(\xi)(f)\|_{\infty}$ under the extra condition of the validity of Nikol’skii’s inequality. Theorem 5.1. Let $1\leqslant p<\infty$. Under Conditions A1 and A2 and the extra assumption $X_N\in \mathrm{NI}(p,\infty,M)$, for any $f\in \mathcal{C}(\Omega)$ Proof. The proof is simple and goes along the lines of the proof of Theorem 5.A. Let $u:= \ell p\mathbf{w}(\xi)(f)$. For an arbitrary $g \in X_N$ we have the following chain of inequalities
$$
\begin{equation*}
\begin{aligned} \, \|f-u\|_\infty &\leqslant \|f-g\|_\infty+\|g-u\|_\infty \leqslant \|f-g\|_\infty +M\|g-u\|_p \\ &\leqslant \|f-g\|_\infty+MD\|S(g-u,\xi)\|_{p,{\mathbf w}} \\ &\leqslant \|f-g\|_\infty+MD\bigl(\|S(f-g,\xi)\|_{p,{\mathbf w}}+ \|S(f-u,\xi)\|_{p,{\mathbf w}}\bigr) \\ &\leqslant \|f-g\|_\infty+2MD\|S(f-g,\xi)\|_{p,{\mathbf w}} \\ &\leqslant \|f-g\|_\infty+2MDW^{1/p}\|S(f-g,\xi)\|_{\infty} \leqslant (1+ 2MDW^{1/p})\|f-g\|_\infty. \end{aligned}
\end{equation*}
\notag
$$
Minimizing over $g\in X_N$ we complete the proof. Here we prove the following analogue of Theorem 5.A under the weaker assumption (5.1) instead of A1. Theorem 5.2. Let $p\in [1,\infty)$. Assume that a subspace $X_N\subset \mathcal{C}(\Omega)$ has the property $X_N\in\mathcal{LD}(m,p,\infty,D)$ provided by a set $\xi=\{\xi^j\}_{j=1}^m$: for each $u\in X_N$ Then for any $f\in \mathcal{C}(\Omega)$ Proof. Let $h\in X_N$ be an element of best $L_\infty$-approximation to $f$ from $X_N$. We have Clearly,
$$
\begin{equation}
\|S(f-h,\xi)\|_\infty \leqslant \|f-h\|_\infty=d(f, X_N)_\infty.
\end{equation}
\tag{5.3}
$$
By the definition of the algorithm $\ell \infty(\xi)$ we have
$$
\begin{equation}
\|S(f-\ell \infty(\xi)(f),\xi)\|_{\infty} \leqslant \|S(f-h,\xi)\|_{\infty} \leqslant d(f, X_N)_\infty.
\end{equation}
\tag{5.4}
$$
Bounds (5.3) and (5.4) imply that
$$
\begin{equation*}
\|S(h-\ell \infty(\xi)(f),\xi)\|_{\infty} \leqslant 2d(f,X_N)_\infty.
\end{equation*}
\notag
$$
The discretization assumption (5.1) implies that
$$
\begin{equation}
\|h-\ell \infty(\xi)(f)\|_{p} \leqslant 2D d(f, X_N)_\infty.
\end{equation}
\tag{5.5}
$$
Combining bounds (5.2) and (5.5) we conclude that which completes the proof. $\Box$ Theorems 5.A and 5.2 provide the following inequalities for any compact subset $\mathbf{F} \subset \mathcal{C}(\Omega)$ and any probability measure $\mu$ on $\Omega$:
$$
\begin{equation}
\varrho_{m}^*({\mathbf F},L_p(\Omega,\mu)) \leqslant Cd_N({\mathbf F},L_\infty), \qquad C=2DW^{1/p}+1, \quad 1\leqslant p<\infty.
\end{equation}
\tag{5.6}
$$
Here $m$ is such that, in the case of Theorem 5.A, Conditions A1 and A2 and, in the case of Theorem 5.2, condition (5.1) are satisfied for any $N$-dimensional subspace of $\mathcal{C}(\Omega)$. For $p=2$ the following inequality is known (see [45]): there exist two positive absolute constants $b$ and $B$ such that for any compact subset $\Omega$ of $\mathbb{R}^d$, any probability measure $\mu$ on it, and any compact subset $\mathbf{F}$ of $\mathcal{C}(\Omega)$
$$
\begin{equation}
\varrho_{bn}({\mathbf F},L_2(\Omega,\mu)) \leqslant Bd_n({\mathbf F},L_\infty).
\end{equation}
\tag{5.7}
$$
It is known (see [20], D.20. A lower bound) and it follows from Corollary 2.1 that for the discretization of the $L_p$-norm of functions in an $N$-dimensional subspace, $2<p<\infty$, we need at least $m> CN^{p/2}$ points. Thus, we can expect that using an argument similar to Theorem 5.A will not allow us to obtain $m$ better than of order $N^{p/2}$ in inequality (5.6) for $2<p<\infty$. Condition (5.1) is weaker than the combination of Conditions A1 and A2. Therefore, there is a hope that we can obtain $m$ better than of order $N^{p/2}$ in inequality (5.6) by using Theorem 5.2 if we solve Open Problem 3.1. Open Problem 5.1. Let $2<p<\infty$. What is the minimal growth of $m(N)$ on $N$ that guarantees the following property: for any compact subset $\mathbf{F} \subset \mathcal{C}(\Omega)$ and any probability measure $\mu$ on $\Omega$ Open Problem 5.2. Let $2<p<\infty$. What is the minimal growth of $m(N)$ on $N$ that guarantees the following property: for any compact subset $\mathbf{F} \subset \mathcal{C}(\Omega)$ and any probability measure $\mu$ on $\Omega$ Note that it is known from [45] (see (5.7)) that in the case $p=2$ (and therefore for all $1\leqslant p\leqslant 2$) one can take $m(N)\leqslant CN$. Theorem 5.2 and Proposition 3.2 for $p=2$ imply the following unconditional result. Theorem 5.3. There exist two absolute positive constants $C_1$ and $C_2$ such that for any $N$-dimensional subspace $X_N \subset \mathcal{C}(\Omega)$ there exists a set of points $\{\xi^j\}_{j=1}^m$, $m\leqslant C_1N$, with the following property: for any $f\in \mathcal{C}(\Omega)$ Note that Proposition 3.2 and Theorem 5.A for $p=2$ imply the following result. Theorem 5.4. There exist absolute positive constants $C_1$ and $C_2$ such that for each $N$-dimensional subspace $X_N \subset \mathcal{C}(\Omega)$ there exists a set of points $\{\xi^j\}_{j=1}^m$, $m\leqslant C_1N$, with the following property: for any $f\in \mathcal{C}(\Omega)$ A comment on sampling recovery in the uniform normIt is well known that results on sampling discretization in the $L_2$-norm imply some results on sampling discretization in the $L_\infty$-norm. We illustrate this phenomenon using some known examples. Probably, the first example of this type is multivariate trigonometric polynomials. Let $Q$ denote a finite subset of $\mathbb{Z}^d$ and $|Q|$ denote the cardinality of $Q$. Let
$$
\begin{equation*}
{\mathcal T}(Q):=\biggl\{f\colon f(\mathbf x)= \sum_{{\mathbf k}\in Q}c_{\mathbf k} e^{i({\mathbf k},{\mathbf x})},\ c_{\mathbf k}\in\mathbb{C}\biggr\}.
\end{equation*}
\notag
$$
The following theorem was proved in [42]. Theorem 5.B ([42], Theorem 1.1). There exist three absolute positive constants $C_1$, $C_2$, and $C_3$ with the following properties: for any $d\in \mathbb{N}$ and each $Q\subset \mathbb{Z}^d$ there exists a set of $m \leqslant C_1|Q| $ points $\xi^j\in \mathbb{T}^d$, $j=1,\dots,m$, such that for $f\in \mathcal{T}(Q)$ In [7] it was shown how Theorem 5.B implies a result on sampling discretization of the $L_\infty$-norm. Namely, the following theorem was proved. Theorem 5.C (see [7], Theorem 2.9). Let two positive absolute constants $C_1$ and $C_2$ be as in Theorem 5.B. Then for any $d\in \mathbb{N}$ and each $Q\subset \mathbb{Z}^d$ there exists a set $\xi$ of $m \leqslant C_1|Q|$ points $\xi^j\in \mathbb{T}^d$, $j=1,\dots,m$, such that for any $f\in \mathcal{T}(Q)$ Proof. For the reader’s convenience we present here the one-line proof from [7]. We use the set of points provided by Theorem 5.B. Then $m\leqslant C_1|Q|$, and for any $f\in\mathcal{T}(Q)$ we have The theorem is proved. We point out that in the above proof, in addition to the sampling discretization result — Theorem 5.B — we used Nikol’skii’s inequality $\|f\|_\infty \leqslant |Q|^{1/2}\|f\|_2$. The following two sampling discretization results show that Nikol’skii’s inequality guarantees good discretization inequalities for general subspaces. Theorem 5.D (see [30], Theorem 1.1). Let $\Omega\subset \mathbb{R}^d$ be a non-empty set with probability measure $\mu$. Let $X_N$ be a subspace in $\mathrm{NI}(2,\infty, tN^{1/2})$. Then there is an absolute constant $C_1$ such that there exists a set $\{\xi^j\}_{j=1}^m\subset \Omega$ of $m \leqslant C_1 t^2 N$ points with the following property: for any $f\in X_N$ where $C_2$ and $C_3$ are absolute positive constants. Theorem 5.E (see [30], Theorem 1.2). If $X_N$ is an $N$-dimensional subspace of the complex space $L_2(\Omega,\mu)$, then there exist three absolute positive constants $C_1'$, $c_0'$, and $C_0'$, a set of $m\leqslant C_1'N$ points $\xi^1,\dots, \xi^m\in\Omega$, and a set of non-negative weights $\lambda_j$, $j=1,\dots, m$, such that Note that Theorem 5.E is a generalization to the complex case of an earlier result from [6] established for the real case. In [19] it was shown how Theorem 5.E implies a result on the sampling discretization of the $L_\infty$-norm. Namely, the following theorem was proved there. Theorem 5.F ([19], Theorem 6.6). There exist two absolute constants $C_1$ and $C_2$ such that for any subspace $X_N \in \mathrm{NI}(2,\infty, M)$ there exists a set of $m\leqslant C_1N$ points $\xi^1,\dots, \xi^m\in\Omega$ with the following property: for any $f\in X_N$ Note that in the special case when $M=tN^{1/2}$ the proof of Theorem 5.F given in [19] shows that Theorem 5.D implies the following result on simultaneous sampling discretization of the $L_\infty$- and $L_2$-norms. Theorem 5.5. Let $\Omega\subset \mathbb{R}^d$ be a non-empty set with probability measure $\mu$. Assume that $X_N \in \mathrm{NI}(2,\infty, tN^{1/2})$. Then there exist three absolute positive constants $C_1$, $C_2$, and $C_3$ (which are from Theorem 5.D) such that there exists a set $\{\xi^j\}_{j=1}^m\subset \Omega$ of cardinality $m \leqslant C_1 t^2 N$ with the following property: for any $f\in X_N$ Moreover, for any $f\in X_N$ Theorems 5.F and 5.5 are conditional results: they hold under the assumption of the validity of Nikol’skii’s inequality. Recently it was understood how those conditional results can be converted into unconditional ones (see [26]). This progress was based on a result of Kiefer and Wolfowitz [22] which guarantees that for any finite-dimensional subspace $X_N$ of $\mathcal{C}(\Omega)$ there exists a probability measure $\mu$ on $\Omega$ such that for all $f\in X_N$ we have
$$
\begin{equation}
\|f\|_\infty \leqslant N^{1/2}\|f\|_{L_2(\Omega,\mu)}.
\end{equation}
\tag{5.9}
$$
In other words, for any subspace $X_N$ of $\mathcal{C}(\Omega)$ we have $X_N \in\mathrm{NI}(2,\infty, N^{1/2})$ for some probability measure $\mu$. It was observed in [26] (see Remark 6 there) that the “Kiefer–Wolfowitz result presents itself as a missing piece” in the known results proved under the assumption of Nikol’skii’s inequality $X_N \in \mathrm{NI}(2,\infty, CN^{1/2})$. The following result was proved in [26]. Theorem 5.G ([26], Theorem 2). There is an absolute constant $C$ such that for any subspace $X_N$ of $\mathcal{C}(\Omega)$ there exists a set $\{\xi^j\}_{j=1}^m\subset \Omega$ of $m \leqslant 2 N$ points with the following property: for any $f\in X_N$ The authors of [26] proved (5.10) using the Kiefer–Wolfowitz result (5.9) (they also proved a novel version of it which is actually the $\mathrm{WLDI}(\infty,2)$) and the $\mathrm{LDI}(2,2)$ (see (3.2)) with $m=2N$ points. They also mention that the $\mathrm{LDI}(\infty,2)$ property (5.10) implies the following $\mathrm{LDI}(\infty,\infty)$:
$$
\begin{equation}
\|f\|_\infty \leqslant C_2N^{1/2}\max_{1\leqslant j\leqslant m}|f(\xi^j)|, \qquad m\leqslant C_1N.
\end{equation}
\tag{5.11}
$$
Note that inequality (5.11) was presented in [23] without proof. It is a direct corollary of Theorem 5.F and the Kiefer–Wolfowitz result. Remark 5.1. The Kiefer–Wolfowitz result (5.9) makes the first half of Theorem 5.5 (inequalities (5.8)) for $t=1$ unconditional (valid for any $X_N\subset \mathcal{C}(\Omega)$) because (5.8) does not depend on the measure $\mu$. In addition, Theorem 5.5 (for $t=1$) provides the following useful discretization of the $L_2$-norm for $\mu$ satisfying $X_N \in \mathrm{NI}(2,\infty, N^{1/2})$ (in particular, for $\mu$ from (5.9)) Let us now discuss the sampling recovery in the uniform norm. Inequality (5.11) provides Condition A1 of discretization in the case $p=\infty$ for $D = C_2N^{1/2}$. Therefore, Theorem 5.A implies that for each subspace $X_N$ of $\mathcal{C}(\Omega)$, for any $f\in \mathcal{C}(\Omega)$ we have
$$
\begin{equation*}
\|f-\ell\infty(\xi)(f)\|_\infty \leqslant (2C_2N^{1/2}+1)d(f,X_N)_\infty.
\end{equation*}
\notag
$$
In turn, this inequality implies that for any compact set $\mathbf{F} \subset \mathcal{C}(\Omega)$ we have
$$
\begin{equation}
\varrho_{bn}^*({\mathbf F},L_\infty) \leqslant Bn^{1/2}d_n({\mathbf F},L_\infty),
\end{equation}
\tag{5.12}
$$
for some positive absolute constants $b$ and $B$. Now we apply Theorem 5.1 to $p=2$. We use Theorem 5.E and Remark 3.1 to satisfy Conditions A1 and A2 and use the Kiefer–Wolfowitz result (5.9) to satisfy the assumption of the validity of Nikol’skii’s inequality. As a result, instead of (5.12) we obtain its linear version
$$
\begin{equation}
\varrho_{bn}({\mathbf F},L_\infty) \leqslant Bn^{1/2}d_n({\mathbf F},L_\infty).
\end{equation}
\tag{5.13}
$$
Note that inequality (5.13) was formulated in [26]. We point out that inequalities (5.12) and (5.13) are direct corollaries of some known results which are based on the theorems in [30] on the sampling discretization of the $L_2$-norm, and of the Kiefer–Wolfowitz result (5.9). Remark 5.2. It was pointed out in [23], § 6, that Theorem 5.E and Theorem 5.F hold for $m\leqslant bN$, where $b\in (1,2]$ is arbitrary and $c_0'$, $C_0'$, and $C_2$ are allowed to depend on $b$. This implies that inequalities (5.11), (5.12), and (5.13) hold for each $C_1\in (1,2]$ and $b\in (1,2]$, where $C_2$ is allowed to depend on $C_1$ and $B$ to depend on $b$. 6. Universal discretization and nonlinear recoveryIn this section we obtain some results related directly to the very recent results from [9]–[11]. Recall the definition of the concept of $v$-term approximation with respect to a given system $\mathcal{D}=\{g_i\}_{i=1}^\infty$ in a Banach space $X$. Given an integer $v\in\mathbb{N}$, we denote by $\mathcal{X}_v(\mathcal{D})$ the collection of all linear spaces spanned by the $g_j$, $j\in J$, where $J\subset \mathbb{N}$ and $|J|=v$, and we denote by $\Sigma_v(\mathcal{D})$ the set of all $v$-term approximants with respect to $\mathcal{D}$:
$$
\begin{equation*}
\Sigma_v({\mathcal D}):=\bigcup_{V\in\mathcal X_v({\mathcal D})} V.
\end{equation*}
\notag
$$
Let
$$
\begin{equation*}
\sigma_v(f,{\mathcal D})_X:=\inf_{g\in\Sigma_v({\mathcal D})}\|f-g\|_X
\end{equation*}
\notag
$$
denote the best $v$-term approximation of $f\in X$ in the $X$-norm with respect to $\mathcal{D}$, and set
$$
\begin{equation*}
\sigma_v({\mathbf F},{\mathcal D})_X:= \sup_{f\in{\mathbf F}} \sigma_v(f,{\mathcal D})_X\quad\text{and}\quad \sigma_0({\mathbf F},{\mathcal D})_X:=\sup_{f\in{\mathbf F}}\|f\|_X.
\end{equation*}
\notag
$$
for a class of functions $\mathbf{F}\subset X$. In this paper we only consider finite systems $\mathcal{D}_N=\{g_i\}_{i=1}^N$. Now we describe results obtained in [10]. The following two algorithms were studied in [10]. Set
$$
\begin{equation*}
\ell p(\xi,L):=\ell p{\mathbf w}_m(\xi,L),\quad\text{where}\quad {\mathbf w}_m:=\biggl(\frac{1}{m}\,,\dots,\frac{1}{m}\biggr).
\end{equation*}
\notag
$$
Algorithm $\ell p$. Given a system $\mathcal{D}_N$ and a set of points $\xi:=\{\xi^j\}_{j=1}^m\subset\Omega$, we define the following algorithm: Algorithm $\ell p^s$. Given a system $\mathcal{D}_N$ and a set of points $\xi:=\{\xi^j\}_{j=1}^m\subset \Omega$, we define the following algorithm: Here index $\mathrm{s}$ stands for sample to stress that this algorithm only uses the sample vector $S(f,\xi)$. Clearly, $\ell p^{\rm s}(\xi,\mathcal{X}_v(\mathcal{D}_N))(f)$ is the best $v$-term approximation of $f$ with respect to $\mathcal{D}_N$ in the space $L_p(\xi)$ with the norm $\|S(f,\xi)\|_p$. So
$$
\begin{equation}
\|f-\ell p^{\rm s}(\xi,\mathcal X_v({\mathcal D}_N))(f)\|_{L_p(\xi)}= \sigma_v(f,{\mathcal D}_N)_{L_p(\xi)}.
\end{equation}
\tag{6.3}
$$
Note that $\ell p^{\rm s}(\xi,\mathcal{X}_v(\mathcal{D}_N))(f)$ may not be unique. In this paper we discuss Algorithm $\ell p^{\rm s}$ and the following version of Algorithm $\ell p$. Algorithm $\ell(p,\infty)$. Given a system $\mathcal{D}_N$ and a set of points $\xi:=\{\xi^j\}_{j=1}^m\subset \Omega$, we define the following algorithm: In [10] the following one-sided universal discretization condition on a family of subspaces was used. Definition 6.1 (see [10]). Let $1\leqslant p <\infty$. We say that a set $\xi:= \{\xi^j\}_{j=1}^m \subset \Omega$ provides one-sided $L_p$-universal discretization with parameter $D\geqslant 1$ for a collection $\mathcal{X}:= \{X(n)\}_{n=1}^k$ of finite-dimensional linear subspaces $X(n)$ if we have In our terms condition (6.5) means that and the points $\{\xi^j\}_{j=1}^m$ provide the property in question. So we say that the set $\xi$ provides the universal $\mathrm{LDI}(p)$.In this paper we use the following slightly weaker condition. Definition 6.2. Let $1\leqslant p <\infty$. We say that a set $\xi:= \{\xi^j\}_{j=1}^m \subset \Omega $ provides the universal $\mathrm{LDI}(p,\infty)$ with parameter $D\geqslant 1$ for a collection $\mathcal{X}:= \{X(n)\}_{n=1}^k$ of finite-dimensional linear subspaces $X(n)$ if $\xi$ provides the property $\bigcup_{n=1}^k X(n)\in \mathcal{LD}(m,p,\infty,D)$, that is, The following two Lebesgue-type inequalities were proved in [10] for Algorithms $\ell p$ and $\ell p^{\rm s}$. We only formulate those parts of these theorems from [10] which are related to our results. Theorem 6.A. Let $m$, $v$, and $N$ be natural numbers such that $v\leqslant N$. Let $\mathcal{D}_N\subset \mathcal{C}(\Omega)$ be a system of $N$ elements. Assume that there exists a set $\xi:= \{\xi^j\}_{j=1}^m \subset \Omega$ which provides the universal $\mathrm{LDI}(p)$-property (6.5) for $1\leqslant p<\infty$ for the collection $\mathcal{X}_v(\mathcal{D}_N)$. Then for any function $f \in \mathcal{C}(\Omega)$ Theorem 6.B. Let $m$, $v$, and $N$ be natural numbers such that $2v\leqslant N$. Let $\mathcal{D}_N\subset \mathcal{C}(\Omega)$ be a system of $N$ elements. Assume that there exists a set $\xi:= \{\xi^j\}_{j=1}^m \subset \Omega $ which provides the universal $\mathrm{LDI}(p)$-property (6.5) for $1\leqslant p<\infty$ for the collection $\mathcal{X}_{2v}(\mathcal{D}_N)$. Then for any function $ f \in \mathcal{C}(\Omega)$ We prove two conditional theorems here: Theorem 6.1 for Algorithm $\ell(p,\infty)$ and Theorem 6.2 for Algorithm $\ell\infty^s$. Theorem 6.1. Let $m$, $v$, and $N$ be natural numbers such that $v\leqslant N$. Let $\mathcal{D}_N\subset \mathcal{C}(\Omega)$ be a system of $N$ elements. Assume that there exists a set $\xi:= \{\xi^j\}_{j=1}^m \subset \Omega$, which provides the universal $\mathrm{LDI}(p,\infty)$ property (6.6) with $1\leqslant p<\infty$ for the collection $\mathcal{X}_v(\mathcal{D}_N)$. Then for any function $f \in \mathcal{C}(\Omega)$ we have Proof. Suppose that a set $\xi:= \{\xi^j\}_{j=1}^m \subset \Omega$ provides the universal $\mathrm{LDI}(p,\infty)$ for the collection $\mathcal{X}_v(\mathcal{D}_N)$. Then condition (5.1) for the same $D$ holds for all the $X(n)$ in the family $\mathcal{X}_v(\mathcal{D}_N)$. Thus, we can apply Theorem 5.2 with the same set of points $\xi$ to each subspace $X(n)$. This yields the inequality for all $n=1,\dots,k$, $k=\binom{N}{v}$,
We prove the following analogue of Theorem 6.1 for Algorithm $\ell\infty^s$ that only uses the values of the function at the points $\xi^1,\dots,\xi^m$. Theorem 6.2. Let $m$, $v$ and $N$ be natural numbers such that $2v\leqslant N$. Let $\mathcal{D}_N\subset \mathcal{C}(\Omega)$ be a system of $N$ elements. Assume that there exists a set $\xi:= \{\xi^j\}_{j=1}^m \subset \Omega$, that provides the universal $\mathrm{LDI}(p,\infty)$ property (6.6) for $1\leqslant p<\infty$ for the collection $\mathcal{X}_{2v}(\mathcal{D}_N)$. Then for any function $f \in \mathcal{C}(\Omega)$ Proof. We derive (6.12) from (6.3). Clearly,
$$
\begin{equation*}
\sigma_v(f,{\mathcal D}_N)_{L_\infty(\xi)} \leqslant \sigma_v(f,{\mathcal D}_N )_\infty.
\end{equation*}
\notag
$$
For brevity set $u:=\ell \infty^{\rm s}(\xi,\mathcal X_v({\mathcal D}_N))(f)$, and let $h$ be the best $L_\infty$-approximation to $f$ from $\Sigma_v(\mathcal{D}_N)$. Then (6.3) implies that
$$
\begin{equation*}
\|h-u\|_{L_\infty(\xi)} \leqslant \|f-h\|_{L_\infty(\xi)}+ \|f-u\|_{L_\infty(\xi)} \leqslant 2\sigma_v(f,{\mathcal D}_N)_\infty.
\end{equation*}
\notag
$$
Using that $h - u \in \Sigma_{2v}(\mathcal{D}_N)$, by discretization (6.6) we conclude that
$$
\begin{equation}
\|h-u\|_{L_p(\Omega,\mu)} \leqslant 2D \sigma_v(f,{\mathcal D}_N)_\infty.
\end{equation}
\tag{6.13}
$$
Finally,
$$
\begin{equation*}
\|f-u\|_{L_p(\Omega,\mu)} \leqslant \|f-h\|_{L_p(\Omega,\mu)}+\|h-u\|_{L_p(\Omega,\mu)}.
\end{equation*}
\notag
$$
This and (6.13) prove (6.12). $\Box$ We now discuss an application of Theorem 6.2 to optimal sampling recovery. We allow any mapping $\Psi\colon \mathbb{C}^m \to L_p(\Omega,\mu)$, and for a class of functions $\mathbf{F}\subset \mathcal{C}(\Omega)$, set
$$
\begin{equation*}
\varrho_m^{\rm o}({\mathbf F},L_p):=\inf_{\xi}\,\inf_{\Psi}\, \sup_{f\in {\mathbf F}}\|f-\Psi(f(\xi^1),\dots,f(\xi^m))\|_p.
\end{equation*}
\notag
$$
Here the index ${\rm o}$ stands for optimal. The following theorem is a direct corollary of Theorem 6.2. Theorem 6.3. Let $m$, $v$, and $N$ be natural numbers such that $2v\leqslant N$. Let $1\leqslant p<\infty$. Assume that a system $\mathcal{D}_N \subset \mathcal{C}(\Omega)$ is such that there exists a set $\xi:= \{\xi^j\}_{j=1}^m \subset \Omega$ that provides the universal $\mathrm{LDI}(p,\infty)$, (6.6), for the collection $\mathcal{X}_{2v}(\mathcal{D}_N)$. Then for any compact subset $\mathbf{F}$ of $\mathcal{C}(\Omega)$ 7. Some remarks on the discretization of the uniform normDiscretization of the uniform norm is an actively developing area of research; the reader can find recent results in the papers [19], [23], [46], and [26]. Let $\Phi:=\{\varphi_i\}_{i=1}^N$ be a real linearly independent system satisfying the condition For we define the vector $A(f)$ by Let $X_N := \operatorname{span}\{\varphi_1,\dots,\varphi_N\}$ and
$$
\begin{equation*}
B_\Phi(L_\infty):=\{A(f)\colon f\in X_N, \ \|f\|_\infty \leqslant 1\} \subset \mathbb{R}^N.
\end{equation*}
\notag
$$
We present here some results similar to the ones in [21] (see also [44], pp. 344 and 345). We begin with the following conditional statement. Theorem 7.1. Assume that the system $\Phi$ satisfies (7.1) and has the following properties: Proof. We use the following result of Gluskin [16]. Here $\langle\mathbf{x}^1,\mathbf{x}^2\rangle=\sum x^1_ix^2_i$ is the usual scalar product and $|\mathbf{x}|=|\langle\mathbf{x},\mathbf{x}\rangle|^{1/2}$ is the Euclidean norm.
Theorem 7.A. Let $Y=\{\mathbf{y}^1,\dots,\mathbf{y}^S\} \subset \mathbb{R}^N$, $|\mathbf{y}^j|=1$, $j=1,\dots,S$, $S\geqslant N$, and Then By the assumption (7.3) we have $m\geqslant N$ and
$$
\begin{equation}
\{A(f)\colon f\in X_N,\ |f(\xi^j)|\leqslant D^{-1},\ j=1,\dots,m\} \subseteq B_\Phi(L_\infty).
\end{equation}
\tag{7.4}
$$
Further, for any $\omega\in \Omega$
$$
\begin{equation*}
|f(\omega)|=|\langle A(f),{\mathbf z}(\omega)\rangle|,\qquad {\mathbf z}(\omega):=(\varphi_1(\omega),\dots,\varphi_N(\omega)) \in \mathbb{R}^N.
\end{equation*}
\notag
$$
Note that $|\mathbf{z}(\omega)|\leqslant(Nt^2)^{1/2}$ by (7.1). It is clear that the condition
$$
\begin{equation*}
|f(\omega)| \leqslant D^{-1}\quad \text{for all }\omega\in\{\xi^j\}_{j=1}^m
\end{equation*}
\notag
$$
is satisfied if
$$
\begin{equation*}
|\langle A(f),{\mathbf z}(\xi^j)\rangle| \leqslant D^{-1}, \qquad j=1,\dots,m.
\end{equation*}
\notag
$$
Now let
$$
\begin{equation*}
{\mathbf y}^j:=\frac{{\mathbf z}(\xi^j)}{|{\mathbf z}(\xi^j)|}\,,\qquad Y:=\{{\mathbf y}^j,\ j=1,\dots, m\}.
\end{equation*}
\notag
$$
By Theorem 7.A, for $S=m$ we obtain
$$
\begin{equation}
\operatorname{vol}(W(Y))^{1/N} \geqslant C\biggl(1+\ln \frac{S}{N}\biggr)^{-1/2}.
\end{equation}
\tag{7.5}
$$
The condition
$$
\begin{equation*}
|\langle A(f),{\mathbf y}^j\rangle|\leqslant N^{-1/2}t^{-1}D^{-1}, \qquad j=1,\dots,m,
\end{equation*}
\notag
$$
implies that
$$
\begin{equation*}
\begin{aligned} \, |\langle A(f),{\mathbf z}(\xi^j)\rangle|&= |\langle A(f),{\mathbf y}^j\rangle|\, |{\mathbf z}(\xi^j)| \\ &\leqslant (Nt^2)^{1/2} N^{-1/2}t^{-1}D^{-1}=D^{-1}, \qquad j=1,\dots,m. \end{aligned}
\end{equation*}
\notag
$$
Therefore, from (7.4) and (7.5) we obtain
$$
\begin{equation*}
\operatorname{vol}(B_\Phi(L_\infty))^{1/N} \geqslant C'N^{-1/2}t^{-1}D^{-1}\biggl(1+\ln\frac{m}{N}\biggr)^{-1/2}.
\end{equation*}
\notag
$$
We now use our assumption (7.2) and conclude that
$$
\begin{equation*}
tKD \geqslant C'\biggl(1+\ln \frac{m}{N}\biggr)^{-1/2}. \quad\Box
\end{equation*}
\notag
$$
Now we discuss a corollary to Theorem 7.1. Let $\Phi:=\{\varphi_i\}_{i=1}^N$ be a uniformly bounded Sidon system:
$$
\begin{equation}
\beta\sum_{i=1}^N |a_i| \leqslant \biggl\|\,\sum_{i=1}^N a_i\varphi_i\biggr\|_\infty \qquad \forall\,\{a_i\}_{i=1}^N;\quad \|\varphi_i\|_\infty \leqslant B,\quad i=1,\dots,N.
\end{equation}
\tag{7.6}
$$
Corollary 7.1. Assume that the system $\Phi$ satisfies (7.6) and $X_N\in\mathcal{LD}(m,\infty,D)$. Then there exists an absolute positive constant $c $ such that Proof. Condition (7.6) implies that the system $\Phi$ satisfies (7.1) for $t=B$ and
$$
\begin{equation*}
\operatorname{vol}(B_\Phi(L_\infty))^{1/N} \leqslant C_1\beta^{-1}N^{-1}
\end{equation*}
\notag
$$
for an absolute constant $C_1$. Applying Theorem 7.1 for $t=B$, $K=C_1\beta^{-1}N^{-1/2}$, and $D$ we complete the proof. $\Box$ The Sidon property is connected with other interesting properties of functional systems. This provides more examples of systems with poor $L_\infty$-discretization. Recall the sub-Gaussian norm
$$
\begin{equation*}
\|\varphi\|_{\psi_2}:=\inf\biggl\{C>0\colon \int_\Omega\exp\biggl\{\frac{\varphi^2}{C^2}\biggr\}\,d\mu\leqslant 2\biggr\}.
\end{equation*}
\notag
$$
We call a system $\varphi_1,\dots,\varphi_n$ sub-Gaussian if
$$
\begin{equation*}
\biggl\|\,\sum_{k=1}^n a_k \varphi_k\biggr\|_{\psi_2}\leqslant C\biggl(\,\sum_{k=1}^n a_k^2\biggr)^{1/2}
\end{equation*}
\notag
$$
for all coefficients and some fixed $C$. Example 7.1. For any uniformly bounded orthonormal sub-Gaussian system $\{\varphi_i\}_{i=1}^N$ the space $X_N := \operatorname{span}\{\varphi_i\}_{i=1}^N$ requires an exponential number of points for $L_\infty$-discretization. Indeed, it was proved in [2], Theorem 1.7, that such a system has a Sidon subsystem of size $cN$. Recall some probabilistic notation: $\mathsf{E}$ means expectation and $\mathcal N(0,1)$ is the standard normal distribution. Example 7.2. For any uniformly bounded orthonormal system $\{\varphi_i\}_{i=1}^N$ that is randomly Sidon: the space $X_N := \operatorname{span}\{\varphi_i\}_{i=1}^N$ requires an exponential number of points for $L_\infty$- discretization. Indeed, it was proved in [39] that the random Sidon property for $\Phi:=\{\varphi_i\}_{i=1}^N$ implies the sidonicity of the system $\Phi^{(4)} := \{\varphi_i(x^1)\cdots\varphi_i(x^4)\}_{i=1}^N$. If some points $\{\xi^j\}_{j=1}^m$ discretize $\operatorname{span}\Phi$, then the points $\{(\xi^{j_1},\xi^{j_2})\}$ discretize $\operatorname{span}\Phi^{(2)}$:
$$
\begin{equation*}
\begin{aligned} \, \biggl|\,\sum_{k=1}^N a_k \varphi_k(x)\varphi_k(y)\biggr| &=\biggl|\,\sum_{k=1}^N(a_k\varphi_k(y))\varphi_k(x)\biggr| \\ &\leqslant D \max_{1\leqslant j\leqslant m} \biggl|\,\sum_{k=1}^N(a_k\varphi_k(y))\varphi_k(\xi^j)\biggr| \\ &=D\max_{1\leqslant j\leqslant m} \biggl|\,\sum_{k=1}^N (a_k\varphi_k(\xi^j))\varphi_k(y)\biggr| \\ &\leqslant D^2\max_{1\leqslant j\leqslant m}\,\max_{1\leqslant l\leqslant m} \biggl|\,\sum_{k=1}^N a_k\varphi_k(\xi^j)\varphi_k(\xi^l)\biggr|. \end{aligned}
\end{equation*}
\notag
$$
Further, the points $\{(\xi^{j_1},\xi^{j_2},\xi^{j_3},\xi^{j_4})\}$ discretize the Sidon system $\operatorname{span}\Phi^{(4)}$, so the number of points is exponential in $N$. The third-named author is grateful to D. Krieg for bringing the paper [22] to his attention.
Citation in format AMSBIB
\Bibitem{LimMalTem24} |
|
|||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|
Contact us: |
Terms of Use
|
Registration to the website |
Logotypes |
|