fourierlargesymbols147

# Random points are good for universal discretization

F. Dai and V. Temlyakov 111 The first named author’s research was partially
supported by NSERC of Canada Discovery Grant RGPIN-2020-03909. The second
named author’s research was supported by the Russian Science Foundation
(project No. 23-71-30001) at the Lomonosov Moscow State University.

###### Abstract

There has been significant progress in the study of sampling discretization of
integral norms for both a designated 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. Recent sampling discretization results
typically provide existence of good sampling points for discretization. In
this paper, we show that independent and identically distributed random points
provide good universal discretization with high probability. Furthermore, we
demonstrate that a simple greedy algorithm based on those points that are good
for universal discretization provides excellent sparse recovery results in the
square norm.

Keywords and phrases: Sampling discretization, universality, recovery.

MSC classification 2000: Primary 65J05; Secondary 42A05, 65D30, 41A63.

##  1 Introduction

In this paper, we continue the discussion from [5] on universal discretization
of integral norms for collections of finite-dimensional subspaces that are
spanned by functions from a finite dictionary of uniformly bounded functions
on a domain. Let us first describe some necessary notations and concepts
related to universal discretization for the rest of this paper.

Let $\Omega$ be a locally compact Hausdorff space equipped with a Borel
probability measure $\mu$. For $1\leq p\leq\infty$, we denote by
$L_{p}(\Omega):=L_{p}(\Omega,\mu)$ the Lebesgue space $L_{p}$ defined with
respect to the measure $\mu$ on $\Omega$, and by $\|\cdot\|_{p}$ the norm of
$L_{p}(\Omega)$. Throughout the paper, we will use a slight abuse of the
notation that $L_{\infty}(\Omega)$ denotes the space of all uniformly bounded
measurable functions on $\Omega$ with norm
$\|f\|_{\infty}=\sup_{x\in\Omega}|f(x)|$. Discretization of the $L_{p}$ norm
refers to the process of replacing the measure $\mu$ with a discrete measure
$\mu_{m}$ supported on a finite subset
$\xi=\\{\xi^{j}\\}_{j=1}^{m}\subset\Omega$. This involves substituting
integration with respect to the measure $\mu$ with an appropriate sum of
evaluations of $f$ at the points $\xi^{j}$, $j=1,\cdots,m$. This approach to
discretization is commonly referred to as sampling discretization. We now
formulate explicitly both the sampling discretization problem (also known as
the Marcinkiewicz discretization problem) and the problem of universal
discretization.

The sampling discretization problem. Let $X_{N}\subset L_{p}$ be an
$N$-dimensional subspace of $L_{p}(\Omega,\mu)$ with $1\leq p<\infty$ (the
index $N$ here, usually, stands for the dimension of $X_{N}$). We shall always
assume that every function in $X_{N}$ is defined everywhere on $\Omega$, and
for every $x\in\Omega$,

$\sup\\{|f(x)|:\ \ f\in X_{N},\ \|f\|_{p}\leq 1\\}<\infty.$

We say that $X_{N}$ admits the Marcinkiewicz-type discretization theorem with
parameters $m\in{\mathbb{N}}$ and $p$ and positive constants $C_{1}\leq C_{2}$
if there exists a set $\xi:=\\{\xi^{j}\\}_{j=1}^{m}$ of $m$ points in $\Omega$
such that for any $f\in X_{N}$

$C_{1}\|f\|_{p}^{p}\leq\frac{1}{m}\sum_{j=1}^{m}|f(\xi^{j})|^{p}\leq
C_{2}\|f\|_{p}^{p}.$ (1.1)

This definition can be slightly modified to include the case $p=\infty$ as
well.

The problem of universal discretization. Let
$\mathcal{X}:=\\{X(n)\\}_{n=1}^{k}$ be a finite collection of finite-
dimensional function spaces on $\Omega$. Given $1\leq p<\infty$, we say that a
set $\xi:=\\{\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 each $n\in\\{1,\dots,k\\}$ and any
$f\in X(n)$

$C_{1}\|f\|_{p}^{p}\leq\frac{1}{m}\sum_{j=1}^{m}|f(\xi^{j})|^{p}\leq
C_{2}\|f\|_{p}^{p}.$

This definition can be slightly modified to include the case $p=\infty$ as
well. For the sake of convenience in later applications, we say a finite set
of points in $\Omega$ provides universal discretization for a collection
$\mathcal{X}$ of finite-dimensional spaces if it provides universal
discretization of the $L_{2}$ norm for the collection $\mathcal{X}$ with
constants $\frac{1}{2}$ and $\frac{3}{2}$; that is,

$\frac{1}{2}\|f\|_{2}^{2}\leq\frac{1}{m}\sum_{j=1}^{m}|f(\xi^{j})|^{2}\leq\frac{3}{2}\|f\|_{2}^{2}\quad\text{for
any}\quad f\in\bigcup_{V\in\mathcal{X}}V.$ (1.2)

Additionally, we define $m(\mathcal{X})$ to be the smallest positive integer
$m$ for which there exists a set $\xi$ of $m$ points in $\Omega$ which
provides universal discretization (1.2) for the collection $\mathcal{X}$.
222We define $m(\mathcal{X})=\infty$ if there does not exist such a finite set
$\xi$ for any positive integer $m$.

We point out that the concept of universality is well known in approximation
theory. For instance, the reader can find a discussion of universal cubature
formulas in [17], Section 6.8.

Given $x\in{\mathbb{R}}$, we use the notation $\left\lfloor x\right\rfloor$
(resp. $\left\lceil{x}\right\rceil$) to denote the largest (resp. smallest)
integer $\leq x$ (resp., $\geq x$).

In this paper, our discussion will focus on universal discretization for
special collections of subspaces generated by a finite dictionary of bounded
functions on $\Omega$. Throughout the paper, we will write our dictionary in
the form ${\mathcal{D}}_{N}=\\{\varphi_{i}\\}_{i=1}^{N}$, where
$\varphi_{1},\cdots,\varphi_{N}$ are bounded functions on $\Omega$. Given an
integer $1\leq v\leq N$, we denote by $\mathcal{X}_{v}({\mathcal{D}}_{N})$ the
collection of all linear spaces spanned by $\\{\varphi_{j}:\ \ j\in J\\}$ with
$J\subset\\{1,2,\cdots,N\\}$ and $|J|=v$. A function $f:\Omega\to{\mathbb{C}}$
is said to be $v$-sparse with respect to the dictionary ${\mathcal{D}}_{N}$ if
it belongs to a linear space from the collection
$\mathcal{X}_{v}({\mathcal{D}}_{N})$. We denote by
$\Sigma_{v}({\mathcal{D}}_{N})$ the set of all $v$-sparse functions with
respect to the dictionary ${\mathcal{D}}_{N}$. In other words, we have

$\displaystyle\Sigma_{v}({\mathcal{D}}_{N}):$
$\displaystyle=\bigcup_{V\in\mathcal{X}_{v}({\mathcal{D}}_{N})}V.$

Given $1\leq p<\infty$, we also define

$\Sigma_{v}^{p}({\mathcal{D}}_{N}):=\\{f\in\Sigma_{v}({\mathcal{D}}_{N}):\ \
\|f\|_{p}\leq 1\\},\ \ v=1,2,\cdots,N.$

A dictionary ${\mathcal{D}}_{N}:=\\{\varphi_{j}\\}_{j=1}^{N}$ is called
uniformly bounded if

$\sup_{x\in\Omega}|\varphi_{j}(x)|\leq 1,\ \ j=1,2,\cdots,N.$ (1.3)

It is called a uniformly bounded Riesz basis if (1.3) is satisfied, and there
exist constants $0<R_{1}\leq R_{2}<\infty$ such that for any
$(a_{1},\cdots,a_{N})\in{\mathbb{C}}^{N}$,

$R_{1}\left(\sum_{j=1}^{N}|a_{j}|^{2}\right)^{1/2}\leq\left\|\sum_{j=1}^{N}a_{j}\varphi_{j}\right\|_{2}\leq
R_{2}\left(\sum_{j=1}^{N}|a_{j}|^{2}\right)^{1/2}.$ (1.4)

Next, we give a brief summary of recent results on universal sampling
discretization and its various applications that were obtained in [5] and [6].
These results give some background information for the discussion in the
current paper.

Theorem A below is one of the main results of [5]. It ensures the existence of
a set of at most $Cv(\log N)^{2}(\log v)^{2}$ points which provides universal
discretization of $L_{p}$ norms of functions from
$\Sigma_{v}({\mathcal{D}}_{N})$ for $1\leq p\leq 2$ under the assumptions
(1.3) and (1.4) on the dictionary ${\mathcal{D}}_{N}$.

Theorem A.[5, Theorem 1.3] Let ${\mathcal{D}}_{N}=\\{\varphi_{j}\\}_{j=1}^{N}$
be a uniformly bounded Riesz basis satisfying (1.3) and (1.4) for some
constants $0<R_{1}\leq R_{2}$. Then for each $1\leq p\leq 2$, and any integer
$1\leq v\leq N$, there exists a set of $m$ points
$\xi^{1},\cdots,\xi^{m}\in\Omega$ with $m\leq Cv(\log N)^{2}(\log(2v))^{2}$
such that the inequalities

$\frac{1}{2}\|f\|_{p}^{p}\leq\frac{1}{m}\sum_{j=1}^{m}|f(\xi^{j})|^{p}\leq\frac{3}{2}\|f\|_{p}^{p}$
(1.5)

hold for any $f\in\Sigma_{v}({\mathcal{D}}_{N})$, where $C=C(p,R_{1},R_{2})>1$
is a constant depending only on $p$, $R_{1}$ and $R_{2}$.

Theorem A gives the following upper bound on the minimal number of points for
good universal discretization:

$m\Bigl{(}\mathbf{\mathcal{X}}_{v}({\mathcal{D}}_{N})\Bigr{)}\leq Cv(\log
N)^{2}(\log(2v))^{2}.$ (1.6)

This upper bound is linear in $v$ with extra logarithmic terms in $N$ and $v$,
and is reasonably good since the lower bound
$m\Bigl{(}\mathbf{\mathcal{X}}_{v}({\mathcal{D}}_{N})\Bigr{)}\geq v$ holds
trivially. A weaker upper bound which is quadratic in $v$ was previously
obtained. We refer to [5], [4], and [10] for historical comments.

In [6] we showed that points that provide good universal discretization can be
used for sparse recovery of multivariate smooth functions. In particular, we
used the universal discretization results for the $L_{2}$ norm for analyzing a
theoretical sparse recovery algorithm with respect to a special dictionary
${\mathcal{D}}_{N}$, and proved the Lebesgue-type inequalities for the
corresponding algorithm. See Section 5 for a more detailed description of the
results of [6].

We now proceed with a detailed description of the main results of this paper.
Our first result gives an improvement of Theorem A.

######  Theorem 1.1.

Assume that ${\mathcal{D}}_{N}=\\{\varphi_{j}\\}_{j=1}^{N}\subset
L_{\infty}(\Omega)$ is a dictionary of $N$ uniformly bounded functions on
$\Omega$ such that (1.3) is satisfied and there exists a constant $K\geq 1$
such that for any $(a_{1},\cdots,a_{N})\in\mathbb{C}^{N},$

$\sum_{j=1}^{N}|a_{j}|^{2}\leq
K\left\|\sum_{j=1}^{N}a_{j}\varphi_{j}\right\|^{2}_{2}.$ (1.7)

Let $\xi^{1},\cdots,\xi^{m}$ be independent and identically distributed random
points on $\Omega$ with the probability distribution $\mu$. Then for any
$1\leq p\leq 2$ and any integer $1\leq v\leq N$, the inequalities

$\frac{1}{2}\|f\|_{p}^{p}\leq\frac{1}{m}\sum_{j=1}^{m}|f(\xi^{j})|^{p}\leq\frac{3}{2}\|f\|_{p}^{p},\
\ \ \forall f\in\Sigma_{v}({\mathcal{D}}_{N})$ (1.8)

hold with probability $\geq
1-2\exp\Bigl{(}-\frac{cm}{Kv\log^{2}(2Kv)}\Bigr{)}$, provided that

$m\geq CKv\log N\cdot(\log(2Kv))^{2}\cdot(\log(2Kv)+\log\log N).$

where $C,c$ are positive constants depending only on $p$.

Several remarks are in order.

######  Remark 1.1.

It is easily seen that (1.7) holds for some constant $K>0$ if and only if
$\varphi_{1},\cdots,\varphi_{N}$ are linearly independent in
$L_{2}(\Omega,\mu)$, in which case we can choose $K^{-1}$ to be the smallest
eigenvalue of the $N\times N$ matrix
$\Bigl{[}\langle\varphi_{i},\varphi_{j}\rangle_{L_{2}(\mu)}\Bigr{]}_{1\leq
i,j\leq N}$.

######  Remark 1.2.

Theorem 1.1 improves Theorem A in several ways. First, the condition (1.7) is
weaker than the condition (1.4), which particularly means that estimates in
Theorem 1.1 are independent of the constant $R_{2}$ in (1.4). Second, Theorem
1.1 gives a better upper bound on the number of points:

$m\Bigl{(}\mathbf{\mathcal{X}}_{v}({\mathcal{D}}_{N})\Bigr{)}\leq Cv(\log
N)(\log(2v))^{2}(\log(2v)+\log\log N).$ (1.9)

Here we improve the dependence on $N$ from $(\log N)^{2}$ in (1.6) to $(\log
N)(\log\log N)$ at the cost of an additional factor $\log(2v)$. In particular,
we obtain from (1.9) that for each fixed $1\leq v\leq N$,

$m\Bigl{(}\mathbf{\mathcal{X}}_{v}({\mathcal{D}}_{N})\Bigr{)}\leq C_{v}(\log
N)(\log\log N).$

It is interesting to point out that this last estimate is almost optimal as
$N\to\infty$ in the sense that there exists a uniformly bounded Riesz basis
${\mathcal{D}}_{N}$ for each $N\in{\mathbb{N}}$ such that

$m\Bigl{(}\mathbf{\mathcal{X}}_{v}({\mathcal{D}}_{N})\Bigr{)}\geq c\log N,\ \
v=1,2,\cdots,N,$

where $c>0$ is an absolute constant. See Section 4 for details. Finally,
Theorem A only ensures the existence of a set of good points which provides
universal discretization, while Theorem 1.1 shows that a set of independent
random points that are identically distributed according to $\mu$ provides
good universal discretization with high probability. The step from the
existence result to the statement “with high probability for randomly chosen
points” turns out to be nontrivial.

######  Remark 1.3.

The conclusion of Theorem 1.1 remains true for each integer $1\leq v\leq N$ if
we replace the condition (1.7) with the following weaker one: for any
$(a_{1},\cdots,a_{N})\in\mathbb{C}^{N}$,

$\sum_{j\in J}|a_{j}|^{2}\leq K\left\|\sum_{j\in
J}a_{j}\varphi_{j}\right\|^{2}_{2},\ \ \ \forall J\in\mathcal{J}_{v},$ $None$

where $\mathcal{J}_{v}$ denotes the collection of all subsets $J$ of
$\\{1,2,\cdots,N\\}$ with $|J|=v$.

Theorem 1.1 has interesting applications in sparse sampling recovery. As our
next result shows, a simple greedy algorithm - Weak Orthogonal Matching
Pursuit (WOMP) - can effectively recover sparse functions by utilizing points
in Theorem 1.1 that provide good universal discretization. To formulate this
result, we need to describe some necessary notations.

Let $X=(X,\|\cdot\|)$ be a Banach space of functions on $\Omega$. Let
${\mathcal{D}}_{N}=\\{\varphi_{i}\\}_{i=1}^{N}\subset X$ be a dictionary in
$X$. For $v=1,2,\cdots$, define

$\sigma_{v}(f,{\mathcal{D}}_{N})_{X}:=\inf_{g\in\Sigma_{v}({\mathcal{D}}_{N})}\|f-g\|$

to be the best $v$-term approximation of $f\in X$ in the norm of $X$ with
respect to ${\mathcal{D}}_{N}$. Furthermore, for a function class
$\mathbf{F}\subset X$, we define

$\sigma_{v}(\mathbf{F},{\mathcal{D}}_{N})_{X}:=\sup_{f\in\mathbf{F}}\sigma_{v}(f,{\mathcal{D}}_{N})_{X},\quad
v=1,2,\cdots$

and

$\sigma_{0}(\mathbf{F},{\mathcal{D}}_{N})_{X}:=\sup_{f\in\mathbf{F}}\|f\|.$

The Weak Orthogonal Matching Pursuit (WOMP) is a greedy algorithm defined with
respect to a given dictionary ${\mathcal{D}}_{N}=\\{\varphi_{i}\\}_{i=1}^{N}$
in a Hilbert space of functions on $\Omega$ equipped with the inner product
$\langle\cdot,\cdot\rangle$ and the norm $\|\cdot\|$. It was also defined in
[13] under the name Weak Orthogonal Greedy Algorithm.

Weak Orthogonal Matching Pursuit (WOMP). Let
${\mathcal{D}}_{N}=\\{\varphi_{i}\\}_{i\in I}$ be a dictionary of countably
many nonzero elements in $H$, where $I\subset{\mathbb{N}}$. Let
$\tau:=\\{t_{k}\\}_{k=1}^{\infty}\subset(0,1]$ be a given sequence of weakness
parameters. Given $f_{0}\in H$, we define a sequence
$\\{f_{k}\\}_{k=1}^{\infty}\subset H$ of functions for $k=1,2,\cdots$
inductively as follows:

  1. (1)

$j_{k}\in I$ is any integer from the index set $I$ satisfying

$|\langle f_{k-1},\psi_{j_{k}}\rangle|\geq t_{k}\sup_{i\in I}|\langle
f_{k-1},\psi_{i}\rangle|,$

where $\psi_{i}=\varphi_{i}/\|\varphi_{i}\|$ for $i\in I$.

  2. (2)

Let $H_{k}:=\operatorname{span}\\{\varphi_{j_{1}},\dots,\varphi_{j_{k}}\\}$,
and define $G_{k}(\cdot,{\mathcal{D}})$ to be the orthogonal projection
operator from $H$ onto the space $H_{k}$ .

  3. (3)

Define the residual after the $k$th iteration of the algorithm by

$f_{k}:=f_{0}-G_{k}(f_{0},{\mathcal{D}}).$

In the case when $t_{k}=1$ for $k=1,2,\dots$, WOMP is called the Orthogonal
Matching Pursuit (OMP). In this paper we only consider the case when
$t_{k}=t\in(0,1]$ for $k=1,2,\dots$. The term weak in the definition of the
WOMP means that at step (1) we do not shoot for the optimal element of the
dictionary which attains the corresponding supremum. The obvious reason for
this is that we do not know in general if the optimal element exists. Another
practical reason is that the weaker the assumption is, the easier it is to
realize in practice. Clearly, $\varphi_{j_{k}}$ may not be unique. However,
all the results formulated below are independent of the choice of the
$\varphi_{j_{k}}$.

For the sake of convenience in later applications, we will use the notation
$\text{WOMP}\bigl{(}{\mathcal{D}};t\bigr{)}_{H}$ to denote the WOMP defined
with respect to a given weakness parameter $t\in(0,1]$ and a dictionary
${\mathcal{D}}$ in a Hilbert space $H$.

Now we are in a position to formulate our second theorem. We will consider the
Hilbert space $L_{2}(\Omega_{m},\mu_{m})$ instead of $L_{2}(\Omega,\mu)$,
where $\Omega_{m}=\\{\xi^{\nu}\\}_{\nu=1}^{m}$ is a set of points that
provides a good universal discretization, and $\mu_{m}$ is the uniform
probability measure on $\Omega_{m}$, i.e., $\mu_{m}\\{\xi^{\nu}\\}=1/m$,
$\nu=1,\dots,m$. Let ${\mathcal{D}}_{N}(\Omega_{m})$ denote the restriction of
a dictionary ${\mathcal{D}}_{N}$ on the set $\Omega_{m}$. Theorem 1.2 below
guarantees that the simple greedy algorithm WOMP gives the corresponding
Lebesgue-type inequality in the norm $L_{2}(\Omega_{m},\mu_{m})$, and hence
provides good sparse recovery.

######  Theorem 1.2.

Let ${\mathcal{D}}_{N}=\\{\varphi_{j}\\}_{j=1}^{N}$ be a uniformly bounded
Riesz basis in $L_{2}(\Omega,\mu)$ satisfying (1.3) and (1.4) for some
constants $0<R_{1}\leq R_{2}<\infty$. Let
$\Omega_{m}=\\{\xi^{1},\cdots,\xi^{m}\\}$ be a finite subset of $\Omega$ that
provides universal discretization for the collection
$\mathcal{X}_{u}({\mathcal{D}}_{N})$ and a given integer $1\leq u\leq N$.
Given a weakness parameter $0<t\leq 1$, there exists a constant integer
$c=c(t,R_{1},R_{2})\geq 1$ such that for any integer $0\leq v\leq u/(1+c)$ and
any $f_{0}\in L_{\infty}(\Omega)$, the

$\text{WOMP}\Bigl{(}{\mathcal{D}}_{N}(\Omega_{m});t\Bigr{)}_{L_{2}(\Omega_{m},\mu_{m})}$

applied to $f_{0}$ gives

$\|f_{cv}\|_{L_{2}(\Omega_{m},\mu_{m})}\leq
C\sigma_{v}(f_{0},{\mathcal{D}}_{N}(\Omega_{m}))_{L_{2}(\Omega_{m},\mu_{m})},$
(1.10)

and

$\|f_{cv}\|_{L_{2}(\Omega,\mu)}\leq
C\sigma_{v}(f_{0},{\mathcal{D}}_{N})_{\infty},$ (1.11)

where $C>1$ is an absolute constant, and $f_{k}$ denotes the residue of
$f_{0}$ after the $k$-th iteration of the algorithm.

######  Corollary 1.1.

Under the assumptions of Theorem 1.2, the

$\text{WOMP}\Bigl{(}{\mathcal{D}}_{N}(\Omega_{m});t\Bigr{)}_{L_{2}(\Omega_{m},\mu_{m})}$

recovers every $v$-sparse $f_{0}\in\Sigma_{v}({\mathcal{D}}_{N})$ exactly for
any positive integer $v$ with $(1+c)v\leq u$.

Theorem 1.2 has an interesting application in optimal sampling recovery. For a
function class $\mathbf{F}\subset{\mathcal{C}}(\Omega)$, we define

$\varrho_{m}^{o}(\mathbf{F},L_{p}):=\inf_{\Psi;\xi}\sup_{f\in\mathbf{F}}\|f-\Psi(f(\xi^{1}),\dots,f(\xi^{m}))\|_{p},$

where the infimum is taken over all mappings $\Psi:\mathbb{C}^{m}\to
L_{p}(\Omega,\mu)$, and all subsets
$\xi=\\{\xi^{\nu}\\}_{\nu=1}^{m}\subset\Omega$ of $m$ points
$\xi^{1},\cdots,\xi^{m}\in\Omega$. Here, the superscript o stands for optimal.
The reader can find some recent results on optimal sampling recovery in
Section 5. As a direct corollary of Theorem 1.2, we have:

######  Corollary 1.2.

Let ${\mathcal{D}}_{N}$ be a uniformly bounded Riesz basis in
$L_{2}(\Omega,\mu)$ satisfying (1.3) and (1.4) for some constants $0<R_{1}\leq
R_{2}<\infty$. Then there exists a constant $c=C(R_{1},R_{2})\geq 1$ depending
only on $R_{1}$ and $R_{2}$ such that for any function class
$\mathbf{F}\subset{\mathcal{C}}(\Omega)$, and any positive integers $u$ and
$m$ with $1+c\leq u\leq N$ and $m\geq m(\mathcal{X}_{u}({\mathcal{D}}_{N}))$,
we have

$\varrho_{m}^{o}(\mathbf{F},L_{2})\leq C\sigma_{\left\lfloor
u/(1+c)\right\rfloor}(\mathbf{F},{\mathcal{D}}_{N})_{\infty},$ (1.12)

where $C>1$ is an absolute constant.

The first inequality of the kind of (1.12) was obtained in the recent paper
[9] by T. Jahn, T. Ullrich, and F. Voigtlaender, where they used deep known
results from compressed sensing and applied the $\ell_{1}$ minimization
algorithm. In addition to function values at $m$ points their algorithm uses
the fact $f\in\mathbf{F}$ and the quantity
$\sigma_{v}(\mathbf{F},{\mathcal{D}}_{N})_{\infty}$. They proved an inequality
similar to (1.12) for a uniformly bounded orthonormal system
${\mathcal{D}}_{N}$ with an extra term (not important one) in the right hand
side of (1.12). Their algorithm does not provide a sparse with respect to
${\mathcal{D}}_{N}$ approximant. We improve the result from [9] in a number of
ways. First, we get rid of the extra term in the right hand side. Second, our
algorithm (WOMP) only uses the function values at $m$ points and does not use
any information about the class $\mathbf{F}$. Thus, it is universal in that
sense. Third, we prove (1.12) for a wider class of systems
${\mathcal{D}}_{N}$. Forth, our algorithm provides $cv$-sparse with respect to
${\mathcal{D}}_{N}$ approximant. Finally, for our algorithm we prove the
Lebesgue-type inequality (1.11) for individual functions.

The rest of this paper is organized as follows. In Section 2, we present a
conditional theorem, Theorem 2.1, without proof, which allows us to establish
universal sampling discretization of the $L_{p}$ norms with randomly selected
sampling points by utilizing certain entropy estimates of
$\Sigma_{v}^{p}({\mathcal{D}}_{N})$ in the uniform norm. This theorem is a
direct consequence of a more general conditional theorem, Theorem 6.1, which
we prove in Section 6. We also give several useful estimates on the entropy
numbers of the set $\Sigma_{v}^{p}({\mathcal{D}}_{N})$ in the uniform norm in
Section 2, following closely the techniques developed in [5]. In Section 3, we
prove Theorem 1.1 by utilizing the conditional Theorem 2.1 and the entropy
number estimates presented in Section 2.

After that, in Section 4 we provide an example of a uniformly bounded Riesz
system ${\mathcal{D}}=\\{\varphi_{j}\\}_{j=1}^{\infty}$ such that for
${\mathcal{D}}_{N}=\\{\varphi_{j}\\}_{j=1}^{N}$ with $N=1,2,\cdots$, we have

$m(\mathbf{\mathcal{X}}_{v}({\mathcal{D}}_{N}))\geq c\log N,\ \
v=1,2,\cdots,N,$

for some absolute constant $c>0$, meaning that universal sampling
discretization for the collection $\mathcal{X}_{v}({\mathcal{D}}_{N})$
normally requires at least $C_{v}\log N$ points. We dedicate Section 5 to
discussing applications of universal sampling discretization in sparse
sampling recovery. In particular, Theorem 1.2 and several other related
results are proved in Section 5. Finally, in Section 6, we prove a more
general version of the conditional theorem stated in Section 2, which
corresponds to the random version of Theorem 5.1 of [5].

##  2 A conditional theorem on universal sampling discretization

We first recall the definition of entropy numbers in Banach spaces. Let $A$ be
a compact subset of a Banach space $(X,\|\cdot\|)$. Given a positive number
$\varepsilon$, the covering number $N_{\varepsilon}(A,X)$ of the set $A$ in
the space $X$ is defined to be the smallest positive integer $n$ for which
there exist $n$ elements $g_{1},\cdots,g_{n}\in A$ such that

$\max_{f\in A}\min_{1\leq j\leq n}\|f-g_{j}\|\leq\varepsilon.$

We denote by $\mathcal{N}_{\varepsilon}(A,X)$ the corresponding minimal
$\varepsilon$-net of the set $A$ in $X$. The $\varepsilon$-entropy
$\mathcal{H}_{\varepsilon}(A,X)$ of the compact set $A$ in $X$ is then defined
as

$\mathcal{H}_{\varepsilon}(A,X)=\log_{2}N_{\varepsilon}(A,X),\ \
\varepsilon>0,$

whereas the entropy numbers of $A$ in the space $X$ are defined as

$\varepsilon_{k}(A,X):=\inf\\{t>0:\ \ \mathcal{H}_{t}(A,X)\leq k\\},\ \
k=0,1,2,\cdots.$

The following theorem is a direct consequence of a more general conditional
theorem that is proved in Section 6 (see Theorem 6.1).

######  Theorem 2.1.

Let $1\leq q<\infty$ and $1\leq v\leq N$. Suppose that ${\mathcal{D}}_{N}$ is
a dictionary of $N$ functions from $L_{\infty}(\Omega)$ such that the set

$\Sigma_{v}^{q}({\mathcal{D}}_{N}):=\\{f\in\Sigma_{v}({\mathcal{D}}_{N})\,:\,\|f\|_{q}\leq
1\\}$

satisfies

$\varepsilon_{k}(\Sigma_{v}^{q}({\mathcal{D}}_{N}),L_{\infty})\leq
B_{1}(v/k)^{1/q},\quad k=1,2,\cdots,$ (2.1)

and

$\|f\|_{\infty}\leq B_{2}v^{1/q}\|f\|_{q},\ \ \forall
f\in\Sigma_{v}({\mathcal{D}}_{N})$ (2.2)

for some constants $B_{1},B_{2}\geq 1$. Let $\xi^{1},\cdots,\xi^{m}\in\Omega$
be independent random points satisfying

$\frac{1}{m}\sum_{k=1}^{m}\mu_{\xi^{k}}=\mu,$ (2.3)

where $\mu_{\xi^{j}}$ denotes the probability distribution of $\xi^{j}$. If

$m\geq C(q)B_{1}^{q}v(\log(2B_{2}v))^{2},$

for some large constant $C(q)>1$ depending on $q$, then the inequalities

$\frac{3}{4}\|f\|_{q}^{q}\leq\frac{1}{m}\sum_{j=1}^{m}|f(\xi^{j})|^{q}\leq\frac{5}{4}\|f\|_{q}^{q},\
\ \forall f\in\Sigma_{v}({\mathcal{D}}_{N})$

hold with probability

$\geq 1-\exp\Bigl{[}-\frac{c_{q}m}{B_{2}^{q}v\log^{2}(2B_{2}v)}\Bigr{]}.$

Clearly, either of the following two conditions implies the condition (2.3) in
the above theorem:

  1. (i)

$\xi^{1},\cdots,\xi^{m}$ are identically distributed according to $\mu$;

  2. (ii)

there exists a partition $\\{\Lambda_{1},\cdots,\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$.

Next, we recall the following simple remark from [5].

######  Remark 2.1.

We point out that (2.1) implies

$\|f\|_{\infty}\leq 3B_{1}v^{1/q},\ \ \forall
f\in\Sigma^{q}_{v}({\mathcal{D}}_{N}).$ (2.4)

Therefore, assumption (2.2) can be dropped with $B_{2}$ replaced by $3B_{1}$
in the bound on $m$. However, in applications, the constant $B_{2}$ in (2.2)
may be significantly smaller than $3B_{1}$. For example, if
${\mathcal{D}}_{N}$ is a uniformly bounded orthonormal system with
$\max_{f\in{\mathcal{D}}_{N}}\|f\|_{\infty}=1$, then we can take $B_{2}=1$ in
the case $q=2$.

Theorem 2.1 motivates us to estimate the quantities
$\varepsilon_{k}(\Sigma_{v}^{q}({\mathcal{D}}_{N}),L_{\infty})$. Our goal for
the reminder of this section is to prove that if the dictionary
${\mathcal{D}}_{N}$ satisfies both (1.3) and ((1.7a)), and if there exist a
number $q_{v}:=q_{N,v}>2$ and a universal constant $C_{0}>1$ such that

$\|f\|_{\infty}\leq C_{0}\|f\|_{q_{v}},\ \ \forall
f\in\Sigma_{2v}({\mathcal{D}}_{N}),$ (2.5)

then we have

$\varepsilon_{k}(\Sigma_{v}^{2}({\mathcal{D}}_{N}),L_{\infty})\leq
C{q_{v}}\Bigl{(}\frac{v}{k}\Bigr{)}^{1/2},\quad k=1,2,\dots.$ (2.6)

We now recall some known general results, which will be needed in our later
proof.

######  Theorem 2.2.

([15], [17, p.331, Theorem 7.4.3]). Let $W$ be a compact subset of a Banach
space $X$ for which there exist a system ${\mathcal{D}}_{N}\subset X$ with
$|{\mathcal{D}}_{N}|=N$, and a number $r>0$ such that

$\sigma_{m}(W,{\mathcal{D}}_{N})_{X}\leq(m+1)^{-r},\quad m=0,1,\cdots,N.$

Then we have

$\varepsilon_{k}(W,X)\leq C(r)\left(\frac{\log(2N/k)}{k}\right)^{r},\ \
k=1,\cdots,N.$ (2.7)

For a given set ${\mathcal{D}}_{N}=\\{g_{j}\\}_{j=1}^{N}$ of $N$ elements in a
Banach space $X$, we introduce the generalized octahedron,

$A_{1}({\mathcal{D}}_{N}):=\left\\{f\,:\,f=\sum_{j=1}^{N}c_{j}g_{j},\quad\sum_{j=1}^{N}|c_{j}|\leq
1\right\\},$ (2.8)

and the norm $\|\cdot\|_{A}$ on
$X_{N}=\operatorname{span}\\{g_{1},\cdots,g_{N}\\}$,

$\|f\|_{A}:=\inf\left\\{\sum_{j=1}^{N}|c_{j}|\,:\,f=\sum_{j=1}^{N}c_{j}g_{j},\
\ c_{j}\in{\mathbb{C}}\right\\},\ \ f\in X_{N}.$

We now use a known general result for a smooth Banach space. For a Banach
space $X$ we define the modulus of smoothness

$\rho(X,u):=\sup_{\|x\|=\|y\|=1}\left(\frac{1}{2}(\|x+uy\|+\|x-uy\|)-1\right),\
\ u>0.$

The uniformly smooth Banach space is the one with the property

$\lim_{u\to 0+}\frac{\rho(X,u)}{u}=0.$

A Banach space $X$ is called $s$-smooth for some parameter $1<s\leq 2$ and
constant ${\gamma}>0$ if $\rho(X,u)\leq{\gamma}u^{s}$ for all $u>0$. The
following bound is a corollary of known greedy approximation results (see, for
instance [17], p.455).

######  Theorem 2.3.

([17, p. 455])  Let $X$ be an $s$-smooth Banach space for some parameter
$1<s\leq 2$ and constant ${\gamma}>0$. Let
${\mathcal{D}}_{N}=\\{g_{j}\\}_{j=1}^{N}\subset X$ be a dictionary normalized
by $\|g_{j}\|_{X}=1$ for all $1\leq j\leq N$. Then for any $1\leq m\leq N$,

$\sigma_{m}(A_{1}({\mathcal{D}}_{N}),{\mathcal{D}}_{N})_{X}\leq
C(s)\gamma^{1/s}m^{1/s-1}.$

We now proceed to a special case of $X=L_{p}$, where it is known that

$\rho(L_{p},u)\leq(p-1)u^{2}/2,\quad 2\leq p<\infty,\ \ u>0.$ (2.9)

######  Theorem 2.4.

Let ${\mathcal{D}}_{N}=\\{\varphi_{j}\\}_{j=1}^{N}\subset L_{\infty}(\Omega)$
be a dictionary satisfying the conditions (1.3), (1.7a) and (2.5) for some
constants $K\geq 1$ and $q_{v}:=q_{N,v}>2$. Then we have

$\varepsilon_{k}(\Sigma_{v}^{2}({\mathcal{D}}_{N}),L_{\infty})\leq
C\sqrt{Kq_{v}\cdot\log N}\Bigl{(}\frac{v}{k}\Bigr{)}^{1/2},\quad k=1,2,\dots.$
(2.10)

###### Proof.

First of all, for any $f=\sum_{j\in G}a_{j}\varphi_{j}$ with $|G|=v$, we have

$\|f\|_{A}\leq\sum_{j\in G}|a_{j}|\leq v^{1/2}\left(\sum_{j\in
G}|a_{j}|^{2}\right)^{1/2}\leq(Kv)^{1/2}\|f\|_{2},$ (2.11)

implying

$\Sigma_{v}^{2}({\mathcal{D}}_{N})\subset(Kv)^{1/2}\Sigma_{v}^{A}({\mathcal{D}}_{N}),$

where

$R\Sigma_{v}^{A}({\mathcal{D}}_{N}):=\\{f\in\Sigma_{v}({\mathcal{D}}_{N})\,:\,\|f\|_{A}\leq
R\\}.$

By Theorem 2.3 with $s=2$ and by (2.9), we have that for $p\in[2,\infty)$

$\sigma_{m}(\Sigma_{v}^{2}({\mathcal{D}}_{N}),{\mathcal{D}}_{N})_{L_{p}}\leq
C(Kv)^{1/2}\sqrt{p}m^{-\frac{1}{2}},\quad m=1,2,\cdots,N.$ (2.12)

Thus, Theorem 2.2 implies that for $p\in[2,\infty)$

$\varepsilon_{k}(\Sigma_{v}^{2}({\mathcal{D}}_{N}),L_{p})\leq
C(Kp\log(2N/k))^{1/2}(v/k)^{1/2},\quad k=1,2,\dots,N.$ (2.13)

Second, by (2.5) we obtain

$\varepsilon_{k}(\Sigma_{v}^{2}({\mathcal{D}}_{N}),L_{\infty})\leq
C_{0}\varepsilon_{k}(\Sigma_{v}^{2}({\mathcal{D}}_{N}),L_{q_{v}}).$ (2.14)

Combining (2.13) and (2.14) we get

$\varepsilon_{k}(\Sigma_{v}^{2}({\mathcal{D}}_{N}),L_{\infty})\leq
C\sqrt{Kq_{v}\cdot\log N}(v/k)^{1/2},\quad k=1,2,\dots,N.$ (2.15)

Finally, for $k>N$ we use the inequalities (see [17, p. 323, (7.1.6)] and [17,
p. 324, Cor 7.2.2])

$\varepsilon_{k}(W,L_{\infty})\leq\varepsilon_{N}(W,L_{\infty})\varepsilon_{k-N}(X_{N}^{\infty},L_{\infty})$

and

$\varepsilon_{n}(X_{N}^{\infty},L_{\infty})\leq 3\cdot 2^{-n/N},\qquad
2^{-x}\leq 1/x,\quad x\geq 1,$

to obtain (2.15) for all $k$. This completes the proof.

∎

In the same way as in Section 3 of [5] we derive from Theorem 2.4, which holds
for $p=2$, the following Theorem 2.5, which holds for $1\leq p\leq 2$. We do
not present this proof here.

######  Theorem 2.5.

Assume that ${\mathcal{D}}_{N}=\\{\varphi_{j}\\}_{j=1}^{N}\subset
L_{\infty}(\Omega)$ is a dictionary satisfying the conditions (1.3), (1.7a)
and (2.5) for some constants $K\geq 1$ and $q_{v}:=q_{N,v}>2$. Then for $1\leq
p\leq 2$, we have

$\varepsilon_{k}(\Sigma_{v}^{p}({\mathcal{D}}_{N}),L_{\infty})\leq
C_{p}\Bigl{(}\frac{Kq_{v}\cdot\log N\cdot v}{k}\Bigr{)}^{1/p},\quad
k=1,2,\dots.$ (2.16)

##  3 Proof of Theorem 1.1

Theorem 2.5 provides bounds on the entropy numbers
$\varepsilon_{k}(\Sigma_{v}^{p}({\mathcal{D}}_{N}),L_{\infty})$ under the
additional assumption (2.5)

$\|f\|_{\infty}\leq C_{0}\|f\|_{q_{v}},\ \ \forall
f\in\Sigma_{2v}({\mathcal{D}}_{N}).$

Thus, a combination of Theorem 2.5 with Theorem 2.1 implies the conclusion of
Theorem 1.1 for

$m\geq C(p)(Kq_{v}\cdot\log N)v(\log(2Kv))^{2}$

under the additional condition (2.5), which is not assumed in Theorem 1.1. In
this section, we will show how to drop this additional assumption.

Recall that ${\mathcal{D}}_{N}:=\\{\varphi_{j}\\}_{j=1}^{N}\subset
L_{\infty}(\Omega)$ is a dictionary satisfying the conditions (1.3) and (1.7)
for some constant $K\geq 1$. For a set $J\subset[N]:=\\{1,2,\cdots,N\\}$, we
define

$V_{J}:=\text{span}\ \Bigl{\\{}\varphi_{j}:\ \ j\in J\Bigr{\\}}\ \ \text{and}\
\ V_{J}^{p}:=\\{f\in V_{J}:\ \ \|f\|_{p}\leq 1\\}.$

Then
$\Sigma_{v}({\mathcal{D}}_{N}):=\underset{\begin{subarray}{c}J\subset[N]\\\
|J|=v\end{subarray}}{\bigcup}V_{J}$ for $1\leq v\leq N$. Furthermore, by (1.3)
and (1.7a), we have

$\|f\|_{\infty}\leq(Kv)^{\frac{1}{2}}\|f\|_{2},\ \ \forall
f\in\Sigma_{v}({\mathcal{D}}_{N}),$

which in turn implies that

$\|f\|_{\infty}\leq(Kv)^{\frac{1}{p}}\|f\|_{p},\ \ \forall
f\in\Sigma_{v}({\mathcal{D}}_{N}),\ \ 1\leq p\leq 2.$ (3.1)

We need several lemmas. The first three lemmas can be found in [1].

######  Lemma 3.1.

[1, Lemma 2.4] Let $X$ denote the space ${\mathbb{R}}^{N}$ endowed with a norm
$\|\cdot\|_{X}$, and let $B_{X}:=\\{x\in X:\ \|x\|_{X}\leq 1\\}$. Then for any
$0<\varepsilon\leq 1$,

$N\log\frac{1}{\varepsilon}\leq\mathcal{H}_{\varepsilon}(B_{X},X)\leq
N\log(1+\frac{2}{\varepsilon}).$ (3.2)

######  Lemma 3.2.

[1, Lemma 2.1] Let $\\{g_{j}\\}_{j=1}^{m}$ be independent random variables
with mean $0$ on some probability space $(\Omega,\mu)$, which satisfy

$\max_{1\leq j\leq m}\|g_{j}\|_{L_{1}(d\mu)}\leq M_{1},\ \ \max_{1\leq j\leq
m}\|g_{j}\|_{L_{\infty}(d\mu)}\leq M_{\infty}$

for some constants $M_{1}$ and $M_{\infty}$. Then for any $0<\varepsilon<1$ we
have the inequality

$\mu\Bigl{\\{}{\omega}\in\Omega:\ \
\Bigl{|}\frac{1}{m}\sum_{j=1}^{m}g_{j}({\omega})\Bigr{|}\geq\varepsilon\Bigr{\\}}\leq
2e^{-\frac{m\varepsilon^{2}}{4M_{1}M_{\infty}}}.$

######  Lemma 3.3.

[1, Lemma 2.5] Let $T:X\to Y$ be a bounded linear map from a normed linear
space $(X,\|\cdot\|_{X})$ into another normed linear space
$(Y,\|\cdot\|_{Y})$. Let $\mathcal{F}$ be an $\varepsilon$-net of the unit
ball $B_{X}:=\\{x\in X:\ \|x\|_{X}\leq 1\\}$ for some constant
$\varepsilon\in(0,1)$. Assume that there exist constants $C_{1},C_{2}>0$ such
that

$C_{1}\|x\|_{X}\leq\|Tx\|_{Y}\leq C_{2}\|x\|_{X},\ \ \ \forall
x\in\mathcal{F}.$

Then

$C_{1}(\varepsilon)\|z\|_{X}\leq\|Tz\|_{Y}\leq C_{2}(\varepsilon)\|z\|_{X},\ \
\forall z\in X,$

where

$\displaystyle C_{1}(\varepsilon):=$ $\displaystyle
C_{1}(1-\varepsilon)-C_{2}\varepsilon\frac{1+\varepsilon}{1-\varepsilon},\ \
C_{2}(\varepsilon):={C_{2}}\frac{1+\varepsilon}{1-\varepsilon}.$

From the above three lemmas, we can deduce

######  Lemma 3.4.

Let $1\leq p\leq 2$ be a fixed number. Let $\\{\xi^{j}\\}_{j=1}^{\infty}$ be a
sequence of independent random points identically distributed according to
$\mu$. Then for any $0<\varepsilon\leq\frac{1}{8}$ and any integer

$m\geq
16K\varepsilon^{-2}v^{2}\log\Bigl{(}\frac{4e}{\varepsilon}\cdot\frac{N}{v}\Bigr{)},$
(3.3)

the inequalities

$\displaystyle(1-4\varepsilon)\|f\|_{p}^{p}\leq\frac{1}{m}\sum_{j=1}^{m}|f(\xi^{j})|^{p}\leq(1+4\varepsilon)\|f\|_{p}^{p},\
\ \forall f\in\Sigma_{v}({\mathcal{D}}_{N})$ (3.4)

hold with probability $\geq
1-2\exp\Bigl{(}-\frac{m\varepsilon^{2}}{16Kv}\Bigr{)}$.

###### Proof.

By Lemma 3.1, for each $J\subset[N]$ with $|J|=v$, there exists an
$\varepsilon$-net $\mathcal{F}_{J}\subset V_{J}^{p}$ of $V_{J}^{p}$ in the
space $L_{p}$ such that
$|\mathcal{F}_{J}|\leq\Bigl{(}1+\frac{2}{\varepsilon}\Bigr{)}^{v}.$ Let
$\mathcal{F}:=\bigcup_{J\subset[N],\ |J|=v}\mathcal{F}_{J}.$ Then

$\displaystyle\log|\mathcal{F}|$
$\displaystyle\leq\log\Bigl{[}\binom{N}{v}\Bigl{(}1+\frac{2}{\varepsilon}\Bigr{)}^{v}\Bigr{]}\leq\log\Bigl{[}\Bigl{(}\frac{eN}{v}\Bigr{)}^{v}\Bigl{(}1+\frac{2}{\varepsilon}\Bigr{)}^{v}\Bigr{]}$
$\displaystyle\leq v\log\Bigl{(}\frac{4eN}{v\varepsilon}\Bigr{)}.$ (3.5)

On the other hand, (3.1) implies

$\|f\|_{\infty}^{p}\leq Kv,\ \ \forall f\in\mathcal{F}.$

Thus, using (3.5) and Lemma 3.2, 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\varepsilon\|f\|_{p}^{p},\
\ \forall f\in\mathcal{F}$ (3.6)

hold with probability

$\displaystyle\geq$ $\displaystyle
1-2|\mathcal{F}|\exp\Bigl{(}-\frac{m\varepsilon^{2}}{8Kv}\Bigr{)}=1-2\exp\Bigl{(}\log|\mathcal{F}|-\frac{m\varepsilon^{2}}{8Kv}\Bigr{)}$
$\displaystyle\geq$ $\displaystyle
1-2\exp\Bigl{(}v\log\Bigl{(}\frac{4eN}{v\varepsilon}\Bigr{)}-\frac{m\varepsilon^{2}}{8Kv}\Bigr{)}.$

Under the condition (3.3), we have

$\frac{m\varepsilon^{2}}{16Kv}\geq
v\log\Bigl{(}\frac{4eN}{v\varepsilon}\Bigr{)},$

implying that (3.6) holds with probability

$\geq 1-2\exp\Bigl{(}-\frac{m\varepsilon^{2}}{16Kv}\Bigr{)}.$

To complete the proof, we just need to note that by Lemma 3.3, (3.6) implies
(3.4).

∎

Given $\mathbf{x}=(x_{1},x_{2},\cdots,x_{m})\in\Omega^{m}$ and
$f:\Omega\to{\mathbb{R}}$, we define

$S(f,\mathbf{x}):=(f(x_{1}),f(x_{2}),\cdots,f(x_{m}))\in{\mathbb{R}}^{m}.$

We denote by $L_{p}^{m}$ the space ${\mathbb{R}}^{m}$ equipped with the
discrete norm

$\|\mathbf{z}\|_{p}:=\begin{cases}(\frac{1}{m}\sum_{j=1}^{m}|z_{j}|^{p}\Bigr{)}^{1/p},&\
\ 1\leq p<\infty,\\\ \underset{1\leq j\leq m}{\max}|z_{j}|,&\ \
p=\infty,\end{cases},\ \ \mathbf{z}=(z_{1},\cdots,z_{m})\in{\mathbb{R}}^{m}.$

Thus,

$\|S(f,\mathbf{x})\|_{p}=\Bigl{(}\frac{1}{m}\sum_{j=1}^{m}|f(x_{j})|^{p}\Bigr{)}^{1/p},\
\ \ 1\leq p<\infty,$

and

$\|S(f,\mathbf{x})\|_{\infty}=\max_{1\leq j\leq m}|f(x_{j})|.$

As usual, we identify a vector in ${\mathbb{R}}^{m}$ with a function on the
set $[m]:=\\{1,2,\cdots,m\\}$. Under this identification,
$\operatorname{span}\\{S(\varphi_{i},\mathbf{x}):\ \ 1\leq i\leq N\\}$ is a
subspace of $L_{p}^{m}$.

Now we are in a position to prove Theorem 1.1. Without loss of generality, we
may assume that $m\leq CKv^{2}\log\Bigl{(}\frac{eN}{v}\Bigr{)}$ for some large
constant $C$, since otherwise Theorem 1.1 follows directly from Lemma 3.4. Let
$\ell_{v}$ denote the smallest integer $\geq
CKv^{2}\log\Bigl{(}\frac{eN}{v}\Bigr{)}$. Let $m_{1}=m\ell_{v}$. Let
$x_{1},\cdots,x_{m_{1}}\in\Omega$ be independent random points that are
identically distributed according to $\mu$. Let
$\mathbf{x}=(x_{1},\cdots,x_{m_{1}})$. By Lemma 3.4, the inequalities

$\displaystyle\frac{4}{5}\|f\|_{p}^{p}\leq\|S(f,\mathbf{x})\|_{p}^{p}\leq\frac{6}{5}\|f\|_{p}^{p},\
\ \forall f\in\Sigma_{v}({\mathcal{D}}_{N}),$ (3.7) and $\displaystyle\ \
\frac{4}{5}\|f\|_{2}^{2}\leq\|S(f,\mathbf{x})\|_{2}^{2}\leq\frac{6}{5}\|f\|_{2}^{2},\
\ \forall f\in\Sigma_{v}({\mathcal{D}}_{N})$ (3.8)

hold simultaneously with probability

$\geq 1-4\exp\Bigl{(}-\frac{cm_{1}}{Kv}\Bigr{)}\geq 1-4e^{-mv}$

for some absolute constant $c\in(0,1)$, provided that the constant $C$ is
large enough.

Next, we fix the random points $x_{1},\cdots,x_{m_{1}}$ such that both (3.7)
and (3.8) hold. Let $\\{\Lambda_{1},\cdots,\Lambda_{m}\\}$ be a partition of
the set $[m_{1}]$ such that $|\Lambda_{j}|=\ell_{v}$ for $1\leq j\leq m$. Let
$n_{j}\in\Lambda_{j}$ denote a random variable that is uniformly distributed
in the finite set $\Lambda_{j}$. Assume in addition that
$x_{1},\cdots,x_{m_{1}},n_{1},\cdots,n_{m}$ are independent. Define
$\xi^{j}=x_{n_{j}}$ for $j=1,2,\cdots,m$. It is easily seen that
$\xi^{1},\cdots,\xi^{m}\in\Omega$ are independent random points identically
distributed according to $\mu$.

Now we consider the discrete $L_{p}^{m_{1}}$ -norm instead of the initial norm
$\|\cdot\|_{L_{p}(\Omega)}$. Let

$S({\mathcal{D}}_{N},\mathbf{x}):=\Bigl{\\{}S(\varphi_{i},\mathbf{x}):\ \
1\leq i\leq N\Bigr{\\}}\subset L_{2}^{m_{1}}.$

(3.7) and (3.8) imply that $S({\mathcal{D}}_{N},\mathbf{x})$ is a dictionary
in $L_{2}^{m_{1}}$ satisfying (1.3) and (1.7a) with constant $\frac{5}{4}K$
for the normalized counting measure on $[m_{1}]$. Moreover, by (3.1) and
(3.7), we have

$\|S(f,\mathbf{x})\|_{\infty}\leq(\frac{5}{4}Kv)^{1/p}\|S(f,\mathbf{x})\|_{p},\
\ \forall f\in\Sigma_{v}({\mathcal{D}}_{N}).$

Note that

$\log m_{1}\leq q_{v}:=C\log(2Kv)+\log\log N.$

Thus, the regular Nikolskii’s inequality of the discrete norms $L_{q}^{m_{1}}$
implies

$\|S(f,\mathbf{x})\|_{\infty}\leq e\cdot\|S(f,\mathbf{x})\|_{q_{v}},\ \
\forall f\in\Sigma_{v}({\mathcal{D}}_{N}).$

By Theorem 2.1 and Theorem 2.5 applied to the discrete norm of
$L_{p}^{m_{1}}$, we conclude that for any integer

$m\geq C_{p}Kv(\log N)(\log(2vK))^{2}(\log(2vK)+\log\log N),$

the inequalities

$\frac{3}{4}\|S(f,\mathbf{x})\|_{p}^{p}\leq\|S(f,\xi)\|_{p}^{p}\leq\frac{5}{4}\|S(f,\mathbf{x})\|_{p}^{p},\
\ \forall f\in\Sigma_{v}({\mathcal{D}}_{N})$ (3.9)

hold with probability

$\geq 1-2\exp\Bigl{(}-\frac{cm}{Kv\log^{2}(2Kv)}\Bigr{)},$

where

$\xi=(\xi^{1},\cdots,\xi^{m})=(x_{n_{1}},x_{n_{2}},\cdots,x_{n_{m}}).$

Combining (3.9) with (3.7), we obtain

$\frac{3}{5}\|f\|_{p}^{p}\leq\|S(f,\xi)\|_{p}^{p}\leq\frac{3}{2}\|f\|_{p}^{p},\
\ \forall f\in\Sigma_{v}({\mathcal{D}}_{N}).$ (3.10)

Finally, we estimate the probability of the event $E$ that (3.10) holds. Let
$E_{1}$ denote the event that both (3.7) and (3.8) hold. The above argument
then shows that ${\mathbf{P}}(E_{1})\geq 1-4e^{-mv}$ and

$\chi_{E_{1}}\cdot\mathbf{E}[\chi_{E}|x_{1},\cdots,x_{m_{1}}]=\chi_{E_{1}}\cdot\mathbf{E}_{n_{1},\cdots,n_{m}}(\chi_{E})$
$\geq\chi_{E_{1}}\left(1-2\exp\Bigl{(}-\frac{cm}{Kv\log^{2}(2Kv)}\Bigr{)}\right),$

where
$\mathbf{E}_{n_{1},\cdots,n_{m}}(\chi_{E})=\mathbf{E}[\chi_{E}|x_{1},\cdots,x_{m_{1}}]$
denotes the conditional expectation given $x_{1},\cdots,x_{m_{1}}$; that is,
the expectation computed with respect to the random variables
$n_{1},\cdots,n_{m}$, fixing the variables $x_{1},\cdots,x_{m_{1}}$. Since
$\chi_{E_{1}}$ is a function of $(x_{1},x_{2},\cdots,x_{m_{1}})$, it follows
that

$\displaystyle{\mathbf{P}}(E)$ $\displaystyle\geq{\mathbf{P}}(E\cap
E_{1})=\mathbf{E}[\chi_{E\cap
E_{1}}]=\mathbf{E}_{x_{1},\cdots,x_{n}}\Bigl{[}\chi_{E_{1}}\cdot\mathbf{E}_{n_{1},\cdots,n_{m}}(\chi_{E})\Bigr{]}$
$\displaystyle\geq\Bigl{(}1-2\exp\Bigl{(}-\frac{cm}{Kv\log^{2}(2Kv)}\Bigr{)}\Bigr{)}\cdot\mathbf{E}[\chi_{E_{1}}]$
$\displaystyle\geq\Bigl{(}1-2\exp\Bigl{(}-\frac{cm}{Kv\log^{2}(2Kv)}\Bigr{)}\Bigr{)}\Bigl{(}1-4e^{-cmv}\Bigr{)}$
$\displaystyle\geq
1-2\exp\Bigl{(}-\frac{c^{\prime}m}{Kv\log^{2}(2Kv)}\Bigr{)}.$

This completes the proof.

##  4 A lower bound for universal discretization

The goal in this section is to construct an example of a uniformly bounded
Riesz system ${\mathcal{D}}=\\{\varphi_{j}\\}_{j=1}^{\infty}$ such that for
${\mathcal{D}}_{N}=\\{\varphi_{j}\\}_{j=1}^{N}$ with $N=1,2,\cdots$ ,

$m(\mathbf{\mathcal{X}}_{v}({\mathcal{D}}_{N}))\geq c\log N,\ \
v=1,2,\cdots,N,$ (4.1)

where $c>0$ is an absolute constant. By monotonicity, it is enough to show
this last inequality for $v=1$.

Let $L_{2}[0,1]$ denote the Lebesgue $L_{2}$-space defined with respect to
usual Lebesgue measure on $[0,1]$. Let

${\mathcal{D}}:=\Bigl{\\{}\frac{1}{\sqrt{2}}\sin(\pi kx):\ \
k=1,2,\cdots\Bigr{\\}}$

and

${\mathcal{D}}_{N}:=\Bigl{\\{}\frac{1}{\sqrt{2}}\sin(\pi kx):\ \
k=1,2,\cdots,N\Bigr{\\}},\ \ N=1,2,\cdots.$

Then ${\mathcal{D}}$ is a uniformly bounded orthonormal system in
$L_{2}[0,1]$. Assume that $\\{\xi^{\nu}\\}_{\nu=1}^{m}$ is a set of $m$ points
in $[0,1]$ that provides universal sampling discretization for the collection
$\mathbf{\mathcal{X}}_{1}({\mathcal{D}}_{N})$. Thus,

$\frac{1}{2}\|g\|_{2}^{2}\leq\frac{1}{m}\sum_{\nu=1}^{m}|g(\xi^{\nu})|^{2},\ \
\forall g\in{\mathcal{D}}_{N}.$ (4.2)

We claim that (4.2) implies (4.1).

To show this claim, we need the simultaneous version of the Dirichlet’s
Theorem on diophantine approximation:

######  Lemma 4.1.

[12, p. 27, Theorem 1A] Given any $\xi^{1},\cdots,\xi^{m}\in[0,1]$ and any
positive integer $N$, there exist integers $1\leq k\leq N$ and
$a_{1},\dots,a_{m}\in{\mathbb{Z}}$ such that

$\Bigl{|}\xi^{\nu}-\frac{a_{\nu}}{k}\Bigr{|}\leq
k^{-1}N^{-1/m},\quad\nu=1,\dots,m.$ (4.3)

Now let $1\leq k\leq N$ and $a_{1},\cdots,a_{m}$ are integers as given in
Lemma 4.1. Let $g_{k}(x)=\sin(\pi kx)\in{\mathcal{D}}_{N}$. Then on one hand,
$\|g_{k}\|_{2}^{2}=2$, but on the other hand, for each $1\leq\nu\leq m$,

$\displaystyle|g_{k}(\xi^{\nu})|$ $\displaystyle=|\sin(\pi
k\xi^{\nu})|=|\sin(\pi k\xi^{\nu})-\sin(\pi a_{\nu})|\leq|\pi k\xi^{\nu}-\pi
a_{\nu}|$ $\displaystyle=\pi
k\Bigl{|}\xi^{\nu}-\frac{a_{\nu}}{k}\Bigr{|}\leq\pi N^{-1/m}.$

Thus, using (4.2), we obtain

$1=\frac{1}{2}\|g_{k}\|_{2}^{2}\leq\frac{1}{m}\sum_{\nu=1}^{m}|g_{k}(\xi^{\nu})|^{2}\leq\pi
N^{-1/m},$

implying

$m\geq\frac{\log N}{\log\pi}.$

##  5 Sparse sampling recovery

We begin this section with the observation that the universal discretization
of the $L_{2}$ norm is closely connected with the concept of Restricted
Isometry Property (RIP), which is very important in compressed sensing.

Let $U=\\{\mathbf{u}^{j}\\}_{j=1}^{N}$ be a system of column vectors from
$\mathbb{C}^{m}$. We form a matrix $\mathbf{U}:=[\mathbf{u}^{1}\
\mathbf{u}^{2}\ ...\ \mathbf{u}^{N}]$ with vectors $\mathbf{u}^{j}$ being the
columns of this matrix. We say that matrix $\mathbf{U}$ or the system $U$ has
the RIP property with parameters $D$ and $\delta\in(0,1)$ if for any subset
$J$ of indexes from $\\{1,2,\dots,N\\}$ with cardinality $|J|\leq D$, and for
any vector $\mathbf{a}=(a_{1},\dots,a_{N})\in\mathbb{C}^{N}$ supported on $J$
(i.e., $a_{j}=0,j\notin J$), we have

$(1-\delta)\|\mathbf{a}\|_{2}^{2}\leq\left\|\sum_{j\in
J}a_{j}\mathbf{u}^{j}\right\|_{2}^{2}=\|\mathbf{U}\mathbf{a}\|_{2}^{2}\leq(1+\delta)\|\mathbf{a}\|_{2}^{2}.$

Let $\Omega$ be a compact subset of ${\mathbb{R}}^{d}$ with the probability
measure $\mu$. For a dictionary
${\mathcal{D}}_{N}=\\{\varphi_{i}\\}_{i=1}^{N}$ and a set of points
$\xi:=\\{\xi^{j}\\}_{j=1}^{m}\subset\Omega$ consider the system of vectors
$G_{N}(\xi)=\\{\boldsymbol{\varphi}_{i}(\xi)\\}_{i=1}^{N}$ where

$\boldsymbol{\varphi}_{i}(\xi):=m^{-\frac{1}{2}}S(\varphi_{i},\xi)=m^{-1/2}(\varphi_{i}(\xi^{1}),\dots,\varphi_{i}(\xi^{m}))^{T},\quad
i=1,\dots,N.$

Suppose that ${\mathcal{D}}_{N}$ is an orthonormal system. On one hand, for
any $v$-sparse vector $\mathbf{a}=(a_{1},\cdots,a_{N})\in{\mathbb{C}}^{N}$
that is supported on a set $I\subset\\{1,2,\cdots,N\\}$ of cardinality $v$,
333This means that $a_{i}=0$ for $i\notin I$ and for $f=\sum_{i\in
I}a_{i}\varphi_{i}\in\Sigma_{v}({\mathcal{D}}_{N})$, we have

$\|f\|_{2}^{2}=\|\mathbf{a}\|_{2}^{2},\quad
S(f,\xi)=(f(\xi^{1}),\dots,f(\xi^{m}))^{T}=m^{1/2}\sum_{i\in
I}a_{i}\boldsymbol{\varphi}_{i}.$

On the other hand, however,

$\left\|\sum_{i\in
I}a_{i}\boldsymbol{\varphi}_{i}\right\|_{2}^{2}=\frac{1}{m}\sum_{j=1}^{m}|f(\xi^{j})|^{2}.$

Thus, the set $\xi:=\\{\xi^{j}\\}_{j=1}^{m}\subset\Omega$ provides universal
discretization of the $L_{2}$ norm for the collection
$\mathcal{X}_{v}({\mathcal{D}}_{N})$ with constants $C_{1}=1-\delta$ and
$C_{2}=1+\delta$ if and only if the the system $G_{N}(\xi)$ has the RIP
property with parameters $v$ and $\delta\in(0,1)$.

The reader can find results on the RIP properties of systems $G_{N}(\xi)$
associated with uniformly bounded orthonormal systems ${\mathcal{D}}_{N}$ in
the book [7]. For illustration we formulate the following result from [7].

######  Theorem 5.1.

[7, p. 405, Theorem 12.31] There exists a universal constant $C$ with the
following properties. Let ${\mathcal{D}}_{N}$ be uniformly bounded orthonormal
system such that $\|g_{i}\|_{\infty}\leq K$, $i=1,2,\dots,N$. Assume that
$\xi^{1}$,…,$\xi^{m}$ are independent random points that are identically
distributed according to $\mu$ on $\Omega$. Then with probability at least
$1-N^{-(\ln N)^{3}}$ the system $G_{N}(\xi)$ has the RIP property with
parameters $s$ and $\delta$ provided

$m\geq CK^{-2}\delta^{-2}s(\ln N)^{4}.$ (5.1)

We now turn to the proof of Theorem 1.2. It relies on a result from [11] (see
also [17], Section 8.7) under the following assumption on the dictionary.

UP($u,D$). ($u,D$)-unconditional property. We say that a dictionary
${\mathcal{D}}=\\{\varphi_{i}\\}_{i\in I}$ of elements in a Hilbert space
$H=(H,\|\cdot\|)$ is ($u,D$)-unconditional with constant $U>0$ for some
integers $1\leq u\leq D$ if for any $f=\sum_{i\in
T}c_{i}\varphi_{i}\in\Sigma_{u}({\mathcal{D}})$ with $T\subset I$ and $|T|=u$,
and for any $A\subset T$ and $J\subset I\setminus A$ such that $|A|+|J|\leq
D$, we have

$\Bigl{\|}\sum_{i\in A}c_{i}\varphi_{i}\Bigr{\|}\leq U\inf_{g\in
V_{J}}\Bigl{\|}\sum_{i\in A}c_{i}\varphi_{i}-g\Bigr{\|},$ (5.2)

where $V_{J}({\mathcal{D}}):=\operatorname{span}\\{\varphi_{i}:\ \ i\in J\\}$.

Recall that the notation $\text{WOMP}\bigl{(}{\mathcal{D}};t\bigr{)}_{H}$
denotes the WOMP that is defined with respect to a weakness parameter
$t\in(0,1]$ and a dictionary ${\mathcal{D}}$ in a Hilbert space $H$.

######  Theorem 5.2 ([11, Corollary I.1]).

Let ${\mathcal{D}}$ be a dictionary in a Hilbert space $H=(H,\|\cdot\|)$
having the property UP($u,D$) with constant $U>0$ for some integers $1\leq
u\leq D$. Let $f_{0}\in H$, and let $t\in(0,1]$ be a given weakness parameter.
Then there exists a positive constant $c_{\ast}:=c(t,U)$ depending only on $t$
and $U$ such that the $\text{WOMP}\bigl{(}{\mathcal{D}};t\bigr{)}_{H}$ applied
to $f_{0}$ gives

$\left\|f_{\left\lceil{c_{\ast}v}\right\rceil}\right\|\leq
C\sigma_{v}(f_{0},{\mathcal{D}})_{H},\ \
v=1,2,\cdots,\min\Bigl{\\{}u,\left\lfloor
D/{(1+c_{\ast})}\right\rfloor\Bigr{\\}},$

where $C>1$ is an absolute constant, and $f_{k}$ denotes the residue of
$f_{0}$ after the $k$-th iteration of the algorithm.

###### Proof of Theorem 1.2.

Using (1.4), we obtain that for any sets $A\subset\\{1,2,\cdots,N\\}$ and
$\Lambda\subset\\{1,\cdots,N\\}\setminus A$ , and for any sequences
$\\{x_{i}\\}_{i\in A},$ $\\{c_{i}\\}_{i\in\Lambda}\subset{\mathbb{C}}$,

$\Bigl{\|}\sum_{i\in
A}x_{i}\varphi_{i}-\sum_{i\in\Lambda}c_{i}\varphi_{i}\Bigr{\|}_{L_{2}(\Omega,\mu)}^{2}\geq
R_{1}^{2}\sum_{i\in A}|x_{i}|^{2}\geq R_{2}^{-2}R_{1}^{2}\Bigl{\|}\sum_{i\in
A}x_{i}\varphi_{i}\Bigr{\|}_{L_{2}(\Omega,\mu)}^{2},$

meaning that the dictionary ${\mathcal{D}}_{N}$ has the UP$(v,N)$ property
with constant $U_{1}=R_{2}/R_{1}$ in the space $L_{2}(\Omega,\mu)$ for any
integer $1\leq v<N$. It then follows from the discretization inequalities
(1.2) with $\mathbf{\mathcal{X}}=\mathbf{\mathcal{X}}_{u}({\mathcal{D}}_{N})$
that the dictionary ${\mathcal{D}}:={\mathcal{D}}_{N}(\Omega_{m})$, which is
the restriction of ${\mathcal{D}}_{N}$ on
$\Omega_{m}=\\{\xi^{1},\cdots,\xi^{m}\\}$, has the properties UP($v,u$) in the
space $L_{2}(\Omega_{m},\mu_{m})$ with constant $U_{2}=U_{1}3^{1/2}$ for any
integer $1\leq v\leq u$. Thus, applying Theorem 5.2 to the discretized
dictionary ${\mathcal{D}}_{N}(\Omega_{m})$ in the Hilbert space
$L_{2}(\Omega_{m},\mu_{m})$, we conclude that the algorithm

$\text{WOMP}\bigl{(}{\mathcal{D}}_{N}(\Omega_{m});t\bigr{)}_{L_{2}(\Omega_{m},\mu_{m})}$

applied to $f_{0}\Bigl{|}_{\Omega_{m}}$ gives

$\left\|f_{cv}\right\|_{L_{2}(\Omega_{m},\mu_{m})}\leq
C\sigma_{v}(f_{0},{\mathcal{D}}_{N}(\Omega_{m}))_{L_{2}(\Omega_{m},\mu_{m})}$

whenever $v+cv\leq u$, where $c=c(t,R_{1},R_{2})\in{\mathbb{N}}$. This proves
(1.10) in Theorem 1.2.

We now derive (1.11) from (1.10). Clearly,

$\sigma_{v}(f_{0},{\mathcal{D}}_{N}(\Omega_{m}))_{L_{2}(\Omega_{m},\mu_{m})}\leq\sigma_{v}(f_{0},{\mathcal{D}}_{N})_{\infty}.$

Let $f\in\Sigma_{v}({\mathcal{D}}_{N})$ be such that $\|f_{0}-f\|_{\infty}\leq
2\sigma_{v}(f_{0},{\mathcal{D}}_{N})_{\infty}$. Then (1.10) implies

$\|f-G_{cv}(f_{0},{\mathcal{D}}_{N}(\Omega_{m}))\|_{L_{2}(\Omega_{m},\mu_{m})}\leq\|f-f_{0}\|_{L_{2}(\Omega_{m},\mu_{m})}+\|f_{cv}\|_{L_{2}(\Omega_{m},\mu_{m})}$
$\leq(2+C)\sigma_{v}(f_{0},{\mathcal{D}}_{N})_{\infty}.$

Using that
$f-G_{cv}(f_{0},{\mathcal{D}}_{N}(\Omega_{m}))\in\Sigma_{u}({\mathcal{D}}_{N})$,
by discretization (1.2) we conclude that

$\|f-G_{cv}(f_{0},{\mathcal{D}}_{N}(\Omega_{m}))\|_{L_{2}(\Omega,\mu)}\leq
2^{1/2}(2+C)\sigma_{v}(f_{0},{\mathcal{D}}_{N})_{\infty}.$ (5.3)

Finally,

$\|f_{cv}\|_{L_{2}(\Omega,\mu)}\leq\|f-f_{0}\|_{L_{2}(\Omega,\mu)}+\|f-G_{cv}(f_{0},{\mathcal{D}}_{N}(\Omega_{m}))\|_{L_{2}(\Omega,\mu)}.$

This and (5.3) prove (1.11).

∎

Universal discretization also has some interesting applications in sparse
sampling recovery in the norm $L_{2}$, as was shown in [6]. To see this, we
assume that $\Omega$ is a compact domain for the sake of convenience. Given a
finite-dimensional subspace $X$ of bounded functions on $\Omega$, and a vector
$\xi=(\xi^{1},\cdots,\xi^{m})\in\Omega^{m}$, the classical least squares
recovery operator (algorithm) is defined as (see, for instance, [3])

$LS(\xi,X)(f):=\text{arg}\min_{u\in X}\|S(f-u,\xi)\|_{2},\quad$

where $S(g,\xi):=(g(\xi^{1}),\cdots,g(\xi^{m}))$, and

$\|S(g,\xi)\|_{2}:=\left(\frac{1}{m}\sum_{\nu=1}^{m}|g(\xi^{\nu})|^{2}\right)^{1/2}.$

With the help of the classical least squares algorithms, we define in [6] a
new nonlinear algorithm for a given collection
$\mathcal{X}=\\{X(n)\\}_{n=1}^{k}$ of finite-dimensional subspaces of
${\mathcal{C}}(\Omega)$:

$n(\xi,f):=\text{arg}\min_{1\leq n\leq k}\|f-LS(\xi,X(n))(f)\|_{2},$
$LS(\xi,\mathcal{X})(f):=LS(\xi,X(n(\xi,f)))(f).$ (5.4)

######  Definition 5.1.

We say that a set $\xi:=\\{\xi^{j}\\}_{j=1}^{m}\subset\Omega$ provides one-
sided universal discretization with constant $C_{1}$ for a collection
$\mathcal{X}:=\\{X(n)\\}_{n=1}^{k}$ of finite-dimensional linear subspaces of
functions on $\Omega$ if

$C_{1}\|f\|_{2}^{2}\leq\frac{1}{m}\sum_{j=1}^{m}|f(\xi^{j})|^{2}\quad\text{for
any}\quad f\in\bigcup_{n=1}^{k}X(n).$

We denote by $m(\mathcal{X},C_{1})$ the minimal positive integer $m$ such that
there exists a set $\xi$ of $m$ points, which provides one-sided universal
discretization with constant $C_{1}$ for the collection $\mathcal{X}$.

For $\xi=(\xi^{1},\cdots,\xi^{m})\in\Omega^{m}$ let $\mu_{\xi}$ denote the
probability measure

$\mu_{\xi}:=\frac{1}{2}\mu+\frac{1}{2m}\sum_{j=1}^{m}\delta_{\xi^{j}},$ (5.5)

where $\delta_{\mathbf{x}}$ denotes the Dirac measure supported at a point
$\mathbf{x}$.

We proved the following conditional theorem in [6].

######  Theorem 5.3 ([6], Theorem 1.2).

Let $v$, $N$ be given natural numbers such that $v\leq N$. Let
${\mathcal{D}}_{N}\subset{\mathcal{C}}(\Omega)$ be a dictionary of $N$
continuous functions on $\Omega$. Assume that there exists a set
$\xi:=\\{\xi^{j}\\}_{j=1}^{m}\subset\Omega$, which provides one-sided
universal discretization with constant $C_{1}$ for the collection
$\mathcal{X}_{v}({\mathcal{D}}_{N})$. Then for any function
$f\in{\mathcal{C}}(\Omega)$ we have

$\|f-LS(\xi,\mathcal{X}_{v}({\mathcal{D}}_{N}))(f)\|_{2}\leq
2^{1/2}(2C_{1}^{-1}+1)\sigma_{v}(f,{\mathcal{D}}_{N})_{L_{2}(\Omega,\mu_{\xi})}$
(5.6)

and

$\|f-LS(\xi,\mathcal{X}_{v}({\mathcal{D}}_{N}))(f)\|_{2}\leq(2C_{1}^{-1}+1)\sigma_{v}(f,{\mathcal{D}}_{N})_{\infty},$
(5.7)

where $\mu_{\xi}$ is the probability measure given in (5.5).

######  Remark 5.1.

An advantage of the algorithm $LS(\xi,\mathcal{X}_{v}({\mathcal{D}}_{N}))$
over the WOMP is that it provides in (5.6) and (5.7) the error in the
$L_{2}(\Omega,\mu)$ norm while the WOMP provides in (1.10) the error in the
discrete $L_{2}(\Omega_{m},\mu_{m})$ norm. However, a big advantage of the
WOMP over $LS(\xi,\mathcal{X}_{v}({\mathcal{D}}_{N}))$ is that it is a simple
algorithm, which is known for easy practical implementation, whereas the
$LS(\xi,\mathcal{X}_{v}({\mathcal{D}}_{N}))$ is only a theoretical algorithm,
which has the step (5.4) that may be difficult to realize. Both the algorithms
WOMP and $LS(\xi,\mathcal{X}_{v}({\mathcal{D}}_{N}))$ only use information
from $f$ and provide the error close to the best (in a certain sense). They do
not use the information that $f\in\mathbf{F}$ and automatically provide the
error bound in terms of the class $\mathbf{F}$, to which $f$ belongs. This
makes these algorithms universal.

In Theorem 1.2, the WOMP provides an error in the discrete norm
$L_{2}(\Omega_{m},\mu_{m})$ in the estimate (1.10). However, a slight
modification of the above proof of Theorem 1.2 also yields the following
corollary, where the error is measured in the $L_{2}(\Omega,\mu)$ norm rather
than the the discrete norm $L_{2}(\Omega_{m},\mu_{m})$.

######  Corollary 5.1.

Under the conditions of Theorem 1.2, we have

$\|f_{cv}\|_{L_{2}(\Omega,\mu)}\leq
C\sigma_{v}(f_{0},{\mathcal{D}}_{N})_{L_{2}(\Omega,\mu_{\xi})},$ (5.8)

where $c=c(t,R_{1},R_{2})\geq 1$ is the constant integer given in Theorem 1.2,
and $f_{k}$ is the residue of $f_{0}$ after the $k$-th iteration of the
algorithm

$\text{WOMP}\Bigl{(}{\mathcal{D}}_{N}(\Omega_{m});t\Bigr{)}_{L_{2}(\Omega_{m},\mu_{m})}.$

###### Proof.

Recall that

$\Omega_{m}=\\{\xi^{1},\cdots,\xi^{m}\\},\ \
\mu_{m}=\frac{1}{m}\sum_{j=1}^{m}\delta_{\xi^{j}}\ \ \ \text{and}\ \
\mu_{\xi}=\frac{\mu+\mu_{m}}{2}.$

For convenience, we will use the notation $\|\cdot\|_{L_{2}(\nu)}$ to denote
the norm of $L_{2}$ defined with respect to a measure $\nu$ on $\Omega$. Let
$g\in\Sigma_{v}({\mathcal{D}}_{N})$ be such that
$\|f_{0}-g\|_{L_{2}(\mu_{\xi})}\leq
2\sigma_{v}(f_{0},{\mathcal{D}}_{N})_{L_{2}(\mu_{\xi})}$. Then

$\displaystyle\|f_{cv}\|_{L_{2}(\mu)}$
$\displaystyle\leq\sqrt{2}\|f_{0}-G_{cv}(f_{0},{\mathcal{D}}_{N}(\Omega_{m}))\|_{L_{2}(\mu_{\xi})}$
$\displaystyle\leq\sqrt{2}\|f_{0}-g\|_{L_{2}(\mu_{\xi})}+\sqrt{2}\|g-G_{cv}(f_{0},{\mathcal{D}}_{N}(\Omega_{m}))\|_{L_{2}(\mu_{\xi})}$
$\displaystyle\leq
2\sqrt{2}\sigma_{v}(f_{0},{\mathcal{D}}_{N})_{L_{2}(\mu_{\xi})}+\sqrt{2}\|g-G_{cv}(f_{0},{\mathcal{D}}_{N}(\Omega_{m}))\|_{L_{2}(\mu_{\xi})}.$

Since

$g-G_{cv}(f_{0},{\mathcal{D}}_{N}(\Omega_{m}))\in\Sigma_{v+cv}({\mathcal{D}}_{N})\subset\Sigma_{u}({\mathcal{D}}_{N}),$

it follows by the universal discretization that

$\displaystyle\|g-$ $\displaystyle
G_{cv}(f_{0},{\mathcal{D}}_{N}(\Omega_{m}))\|_{L_{2}(\mu_{\xi})}\leq
C\|g-G_{cv}(f_{0},{\mathcal{D}}_{N}(\Omega_{m}))\|_{L_{2}(\mu_{m})}$
$\displaystyle\leq
C\|f_{0}-g\|_{L_{2}(\mu_{m})}+C\|f_{0}-G_{cv}(f_{0},{\mathcal{D}}_{N}(\Omega_{m}))\|_{L_{2}(\mu_{m})}$
$\displaystyle\leq
C\|f_{0}-g\|_{L_{2}(\mu_{\xi})}+C\|f_{cv}\|_{L_{2}(\mu_{m})},$

which, using Theorem 1.2, is estimated by

$\displaystyle\leq
C\sigma_{v}(f_{0},{\mathcal{D}}_{N})_{L_{2}(\mu_{\xi})}+C\sigma_{v}(f_{0},{\mathcal{D}}_{N}(\Omega_{m}))_{L_{2}(\mu_{m})}\leq
C\sigma_{v}(f_{0},{\mathcal{D}}_{N})_{L_{2}(\mu_{\xi})}.$

∎

Finally, we discuss applications of the universal discretization for the
trigonometric system in sampling recovery of periodic functions. Let
$M\in{\mathbb{N}}$ and $d\in{\mathbb{N}}$. Let $\Pi(M):=[-M,M]^{d}$ denote the
$d$-dimensional cube. Consider the system

$\mathcal{T}(M,d):=\Bigl{\\{}e^{i(\mathbf{k},\mathbf{x})}:\mathbf{k}\in\Pi(M)\cap{\mathbb{Z}}^{d}\Bigr{\\}}$

of trigonometric function on $\mathbb{T}^{d}=[0,2\pi)^{d}$. Then
$\mathcal{T}(M,d)$ is an orthonormal system in $L_{2}(\mathbb{T}^{d},\mu)$
with $\mu$ being the normalized Lebesgue measure on $\mathbb{T}^{d}$. The
cardinality of this system is $N(M):=|\mathcal{T}(M,d)|=(2M+1)^{d}$. In our
further applications we are interested in bounds on
$m(\mathcal{X}_{v}(\mathcal{T}(M,d))$ in a special case when $M\leq v^{c}$
with some constant $c$ which may depend on $d$. Here we recall that the
notation $m(\mathcal{X})$ is defined in the introduction as the minimal number
of points required for the universal discretization (1.2) for a collection
$\mathcal{X}$ of finite-dimensional linear subspaces. Theorem 1.1 gives

$m(\mathcal{X}_{v}(\mathcal{T}(v^{c},d))\leq C(c,d)v(\log(2v))^{4}.$ (5.9)

This can also be deuced from (5.1) in Theorem 5.1 on the RIP properties.
However, it is known that in the case of system $\mathcal{T}(M,d)$ the bound
(5.1) in Theorem 5.1 can be improved, which in turn can be used to improve the
bound (5.9). To be more precise, combining results of [8] and [2], and using
the argument in the beginning of this section, we get

$m(\mathcal{X}_{v}(\mathcal{T}(v^{c},d))\leq C(c,d)v(\log(2v))^{3}.$ (5.10)

We now apply Corollary 5.1 to optimal sampling recovery of periodic functions.
This discussion complements the one from [6, Section 5]. Given a positive
integer $N$, let

$\Gamma(N):=\bigl{\\{}\mathbf{k}\in\mathbb{Z}^{d}:\prod_{j=1}^{d}\max\bigl{(}|k_{j}|,1\bigr{)}\leq
N\bigr{\\}}\quad\text{--}\quad\text{a hyperbolic cross}.$

Given a finite subset $Q\subset\mathbb{Z}^{d}$, define

$\mathcal{T}(Q):=\left\\{t:t(\mathbf{x})=\sum_{\mathbf{k}\in
Q}c_{\mathbf{k}}e^{i(\mathbf{k},\mathbf{x})},\ \
c_{\mathbf{k}}\in{\mathbb{C}}\right\\}.$

For a vector $\mathbf{s}=(s_{1},\dots,s_{d})$ whose coordinates are
nonnegative integers, we define

$\rho(\mathbf{s}):=\bigl{\\{}\mathbf{k}\in\mathbb{Z}^{d}:\left\lfloor
2^{s_{j}-1}\right\rfloor\leq|k_{j}|<2^{s_{j}},\qquad j=1,\dots,d\bigr{\\}},$

and define, for $f\in L_{1}(\mathbb{T}^{d})$,

$\delta_{\mathbf{s}}(f,\mathbf{x}):=\sum_{\mathbf{k}\in\rho(\mathbf{s})}\hat{f}(\mathbf{k})e^{i(\mathbf{k},\mathbf{x})},\quad\hat{f}(\mathbf{k}):=(2\pi)^{-d}\int_{\mathbb{T}^{d}}f(\mathbf{x})e^{-i(\mathbf{k},\mathbf{x})}d\mathbf{x}.$

We also define for $f\in L_{1}(\mathbb{T}^{d})$

$f_{j}:=\sum_{\|\mathbf{s}\|_{1}=j}\delta_{\mathbf{s}}(f),\quad j=0,1,\cdots.$

The Wiener norm (the $A$-norm or the $\ell_{1}$-norm) of $f\in
L_{1}(\mathbb{T}^{d})$ is defined as

$\|f\|_{A}:=\sum_{\mathbf{k}\in{\mathbb{Z}}^{d}}|\hat{f}({\mathbf{k}})|.$

The following classes, which are convenient in studying sparse approximation
with respect to the trigonometric system, were introduced and studied in [16].
For parameters $a\in{\mathbb{R}}_{+}$ and $b\in{\mathbb{R}}$, define

$\mathbf{W}^{a,b}_{A}:=\Bigl{\\{}f:\|f_{j}\|_{A}\leq
2^{-aj}(j+1)^{(d-1)b},\quad j=0,1,\cdots\Bigr{\\}}.$

The following result was presented in [6] without proof.

######  Lemma 5.1.

There exist two constants $c(a,d)$ and $C(a,b,d)$ such that for any
$\xi\in(\mathbb{T}^{d})^{m}$ and $v\in{\mathbb{N}}$ there is a constructive
method $A_{v,\xi}$ based on greedy algorithms, which provides a $v$-term
approximant from $\mathcal{T}(\Gamma(M))$, $|\Gamma(M)|\leq v^{c(a,d)}$, with
the bound for $f\in\mathbf{W}^{a,b}_{A}$

$\|f-A_{v,\xi}(f)\|_{L_{2}(\mathbb{T}^{d},\mu_{\xi})}\leq
C(a,b,d)v^{-a-1/2}(\log v)^{(d-1)(a+b)}.$

For completeness we will give a proof of a somewhat more general statement at
the end of this section.

Let $v\in{\mathbb{N}}$ be given and let $M$ be from Lemma 5.1. Consider the
orthonormal basis
${\mathcal{D}}_{N}:=\\{e^{i(\mathbf{k},\mathbf{x})}\\}_{\mathbf{k}\in\Gamma(M)}$
of the space $\mathcal{T}(\Gamma(M))$. Then Lemma 5.1, Corollary 5.1 and the
bound (5.10) imply the following Theorem 5.4.

######  Theorem 5.4.

There exist two constants $c^{\prime}(a,d)$ and $C^{\prime}(a,b,d)$ such that
for any $v\in{\mathbb{N}}$ we have that for $a>0$, $b\in{\mathbb{R}}$,

$\varrho_{m}^{o}(\mathbf{W}^{a,b}_{A},L_{2}(\mathbb{T}^{d}))\leq
C^{\prime}(a,b,d)v^{-a-1/2}(\log v)^{(d-1)(a+b)}$ (5.11)

provided that $m$ is an integer satisfying

$m\geq c^{\prime}(a,d)v(\log(2v))^{3}.$

Theorem 5.4 gives the following bound for the classical classes
$\mathbf{W}^{r}_{p}$ of functions with bounded mixed derivative (see [17],
p.130, for their definition and [6] for some recovery results).

######  Corollary 5.2.

There exist two constants $c^{\prime}(r,d,p)$ and $C^{\prime}(r,d,p)$ such
that for any $v\in{\mathbb{N}}$ we have that for $r>1/p$ and $1<p<2$,

$\varrho_{m}^{o}(\mathbf{W}^{r}_{p},L_{2}(\mathbb{T}^{d}))\leq
C^{\prime}(r,d,p)v^{-r+1/p-1/2}(\log v)^{(d-1)(r+1-2/p)}$ (5.12)

provided that

$m\geq c^{\prime}(r,d,p)v(\log(2v))^{3}.$

The authors of [9] (see Corollary 4.16 in v2) proved the following interesting
bound for $1<p<2$, $r>1/p$ and $m\geq c(r,d,p)v(\log(2v))^{3}$,

$\varrho_{m}^{o}(\mathbf{W}^{r}_{p},L_{2}(\mathbb{T}^{d}))\leq
C(r,d,p)v^{-r+1/p-1/2}(\log v)^{(d-1)(r+1-2/p)+1/2}$ (5.13)

The bound (5.12) is better than (5.13) by the $(\log v)^{-1/2}$ factor. The
proof of (5.13) in [9] is based on known results from [16] on sparse
trigonometric approximation in the uniform norm. We proved (5.12) by using
inequality (5.8) and estimating the sparse trigonometric approximation in the
norm $L_{2}(\mathbb{T}^{d},\mu_{\xi})$, which is weaker than the uniform norm.

We conclude this section with a proof of Lemma 5.1. Indeed, we shall prove a
somewhat more general result, where the trigonometric system is replaced by a
more general system
${\mathcal{D}}=\\{g_{\mathbf{k}}\\}_{\mathbf{k}\in\mathbb{Z}^{d}}$ uniformly
bounded functions on a domain $\Omega$:

$|g_{\mathbf{k}}(\mathbf{x})|\leq
1,\quad\mathbf{x}\in\Omega,\quad\mathbf{k}\in\mathbb{Z}^{d}.$ (5.14)

As in the trigonometric case, for

$f=\sum_{\mathbf{k}\in{\mathbb{Z}}^{d}}a_{\mathbf{k}}g_{\mathbf{k}}\ \ \text{
with }\ \ \sum_{\mathbf{k}\in{\mathbb{Z}}^{d}}|a_{\mathbf{k}}|<\infty,$ (5.15)

we define

$\delta_{\mathbf{s}}(f,{\mathcal{D}}):=\sum_{\mathbf{k}\in\rho(\mathbf{s})}a_{\mathbf{k}}g_{\mathbf{k}},\
\
f_{j}:=\sum_{\|\mathbf{s}\|_{1}=j}\delta_{\mathbf{s}}(f,{\mathcal{D}}),j=0,1,\cdots.$

and

$\|f\|_{A({\mathcal{D}})}:=\sum_{\mathbf{k}\in{\mathbb{Z}}^{d}}|a_{\mathbf{k}}|.$

For parameters $a\in{\mathbb{R}}_{+}$, $b\in{\mathbb{R}}$ define
$\mathbf{W}^{a,b}_{A}({\mathcal{D}})$ to be the class of all functions $f$
with a representation (5.15) satisfying

$\|f_{j}\|_{A({\mathcal{D}})}\leq 2^{-aj}(\bar{j})^{(d-1)b},\quad
j=0,1,\cdots,$ (5.16)

where $\bar{j}=\max\\{j,1\\}$. Given a finite set $Q$ of points in
$\mathbb{Z}^{d}$, we denote

${\mathcal{D}}(Q):=\left\\{\sum_{\mathbf{k}\in
Q}a_{\mathbf{k}}g_{\mathbf{k}}:\ \ a_{\mathbf{k}}\in{\mathbb{C}},\ \
\mathbf{k}\in Q\right\\}.$

######  Lemma 5.2.

There exist two constants $c(a,d)$ and $C(a,b,d)$ such that for any
$\xi\in\Omega^{m}$ and $v\in{\mathbb{N}}$ there is a constructive method
$A_{v,\xi}$ based on greedy algorithms, which provides a $v$-term approximant
from ${\mathcal{D}}(\Gamma(M))$, $|\Gamma(M)|\leq v^{c(a,d)}$, with the bound
for $f\in\mathbf{W}^{a,b}_{A}({\mathcal{D}})$

$\|f-A_{v,\xi}(f)\|_{L_{2}(\Omega,\mu_{\xi})}\leq C(a,b,d)v^{-a-1/2}(\log
v)^{(d-1)(a+b)}.$

###### Proof.

We prove the lemma for $v\asymp 2^{n}n^{d-1}$, $n\in{\mathbb{N}}$. Let

$f=\sum_{\mathbf{k}}a_{\mathbf{k}}g_{\mathbf{k}}$

be a representation of $f\in\mathbf{W}^{a,b}_{A}({\mathcal{D}})$ satisfying
(5.16). We approximate $f_{j}$ in $L_{2}(\Omega,\mu_{\xi})$ by a $v_{j}$-term
approximant from
${\mathcal{D}}(Q_{j}):=\cup_{\|\mathbf{s}\|_{1}=j}\rho(\mathbf{s})$. The
sequence $\\{v_{j}\\}$ will be defined later. Since $L_{2}(\Omega,\mu_{\xi})$
is a Hilbert space and by (5.14)

$\|g_{\mathbf{k}}\|_{L_{2}(\Omega,\mu_{\xi})}\leq\sup_{\mathbf{x}\in\Omega}|g_{\mathbf{k}}(\mathbf{x})|\leq
1,\ \mathbf{k}\in Q_{j},$ (5.17)

using Theorem 2.19 of [14, p. 93], we deduce from (5.16) that for every $j$
there exists an $h_{j}\in\Sigma_{v_{j}}({\mathcal{D}}(Q_{j}))$ (provided by a
greedy algorithm – Orthogonal Matching Pursuit) such that

$\|f_{j}-h_{j}\|_{L_{2}(\Omega,\mu_{\xi})}\leq
v_{j}^{-1/2}2^{-aj}(\bar{j})^{(d-1)b}.$

We take $\beta\in(0,a)$ (for instance, $\beta=a/2$) and specify

$v_{j}:=[2^{n-\beta(j-n)}j^{d-1}],\quad j=n,n+1,\dots.$

It is clear that there exists $j(\beta,d)$ such that $v_{j}=0$ for $j\geq
j(\beta,d)n$. For $j\geq j(\beta,d)n$ we set $h_{j}=0$. In addition to
$\\{h_{j}\\}_{j=n}^{j(\beta,d)n}$ we include in the approximant

$S_{n}(f,{\mathcal{D}}):=\sum_{\|\mathbf{s}\|_{1}<n}\delta_{\mathbf{s}}(f,{\mathcal{D}}).$

Define

$A_{v}(f,\beta):=S_{n}(f,{\mathcal{D}})+\sum_{j\geq
n}h_{j}=S_{n}(f,{\mathcal{D}})+\sum_{j=n}^{j(\beta,d)n}h_{j}.$

Then, we have built a $v$-term approximant of $f$ with

$v\ll 2^{n}n^{d-1}+\sum_{j\geq n}v_{j}\ll 2^{n}n^{d-1}.$

The error of this approximation in $L_{2}(\Omega,\mu_{\xi})$ is bounded from
above by

$\|f-A_{m}(f,p,\beta)\|_{L_{2}(\Omega,\mu_{\xi})}\leq\sum_{j\geq
n}\|f_{j}-h_{j}\|_{L_{2}(\Omega,\mu_{\xi})}\leq C\sum_{j\geq
n}(\bar{v}_{j})^{-1/2}2^{-aj}j^{(d-1)b}$ $\leq C\sum_{j\geq
n}2^{-1/2(n-\beta(j-n))}j^{-(d-1)/2}2^{-aj}j^{(d-1)b}\leq
C2^{-n(a+1/2)}n^{(d-1)(b-1/2)}.$

This completes the proof of lemma.

∎

##  6 A more general version of the conditional theorem

Our goal in this section is to prove the following conditional theorem, which
is the random version of Theorem 5.1 of [5].

######  Theorem 6.1.

Let ${\mathcal{W}}\subset L_{\infty}(\Omega)$ and let
${\mathcal{W}}_{p}:=\\{f\in{\mathcal{W}}:\ \ \|f\|_{p}\leq 1\\}$ for some
$1\leq p<\infty$. Assume that ${\lambda}\cdot{\mathcal{W}}={\mathcal{W}}$ for
any ${\lambda}>0$, and ${\mathcal{W}}_{p}$ is a compact subset of
$L_{\infty}$. Let

$R:=\sup_{f\in{\mathcal{W}}_{p}}\sup_{x\in\Omega}|f(x)|.$

Let $\xi^{1},\cdots,\xi^{m}$ be independent random points on $\Omega$
satisfying

$\frac{1}{m}\sum_{k=1}^{m}\mu_{\xi^{k}}=\mu,$ (6.1)

where $\mu_{\xi^{j}}$ denotes the probability distribution of $\xi^{j}$. Then
there exist positive constants $C_{p},c_{p}$ depending only on $p$ such that
for any $\varepsilon\in(0,1)$ and any integer

$m\geq
C_{p}\varepsilon^{-5}\left(\int_{c_{p}\varepsilon^{1/p}}^{R}u^{\frac{p}{2}-1}\Bigl{(}\int_{u}^{R}\frac{\mathcal{H}_{c_{p}\varepsilon
t}({\mathcal{W}}_{p},L_{\infty})}{t}\,dt\Bigr{)}^{\frac{1}{2}}du\right)^{2},$
(6.2)

the inequalities,

$(1-\varepsilon)\|f\|_{p}^{p}\leq\frac{1}{m}\sum_{j=1}^{m}|f(\xi^{j})|^{p}\leq(1+\varepsilon)\|f\|_{p}^{p},\
\ \forall f\in{\mathcal{W}}_{p},$ (6.3)

hold with probability

$\geq
1-\varepsilon\exp\Bigl{(}-\frac{cm\varepsilon^{4}}{R^{p}(\log\frac{R}{\varepsilon})^{2}}\Bigr{)}.$

It can be easily seen that either of the following two conditions implies the
condition (6.1):

  1. (i)

$\xi^{1},\cdots,\xi^{m}$ are identically distributed according to $\mu$;

  2. (ii)

there exists a partition $\\{\Lambda_{1},\cdots,\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$.

The proof of Theorem 6.1 follows along the same line as that of Theorem 5.1 of
[5]. We sketch it as follows.

###### Proof of Theorem 6.1.

Let

${\mathcal{S}}_{p}:=\\{f/{\|f\|_{p}}:\ \ f\in{\mathcal{W}},\ \
\|f\|_{p}>0\\}\subset{\mathcal{W}}_{p}.$

Let $c^{\ast}=c_{p}^{\ast}\in(0,\frac{1}{2})$ be a sufficiently small constant
depending only on $p$. Let $a:=c^{\ast}\varepsilon$. Let $J,j_{0}$ be two
integers such that $j_{0}<0\leq J$,

$(1+a)^{J-1}\leq R<(1+a)^{J}\ \ \text{and}\ \
(1+a)^{j_{0}p}\leq\frac{1}{10}\varepsilon\leq(1+a)^{(j_{0}+1)p}.$ (6.4)

For $j\in{\mathbb{Z}}$, let

$\mathcal{A}_{j}:=\mathcal{N}_{2a(1+a)^{j}}({\mathcal{S}}_{p},L_{\infty})\subset{\mathcal{S}}_{p}$

denote the minimal $2a(1+a)^{j}$-net of ${\mathcal{S}}_{p}$ in the norm of
$L_{\infty}$. For $f\in{\mathcal{S}}_{p}$, we define $A_{j}(f)$ to be the
function in ${\mathcal{A}}_{j}$ such that $\|A_{j}(f)-f\|_{\infty}\leq
2a(1+a)^{j}$.

For $f\in{\mathcal{S}}_{p}$ and $j>j_{0}$, let
$U_{j}(f):=\\{\mathbf{x}\in\Omega:|A_{j}(f)(\mathbf{x})|\geq(1+a)^{j-1}\\},$
and $D_{j}(f):=U_{j}(f)\setminus\underset{k>j}{\bigcup}U_{k}(f).$ Define

$h(f,\mathbf{x}):=\sum_{j=j_{0}+1}^{J}(1+a)^{j}\chi_{D_{j}(f)}(\mathbf{x}).$
(6.5)

It can be easily verified that

$(1-\frac{\varepsilon}{8})|f(\mathbf{x})|^{p}\leq|h(f,\mathbf{x})|^{p}\leq(1+\frac{\varepsilon}{8})|f(\mathbf{x})|^{p},$
(6.6)

if $\mathbf{x}\in\bigcup_{j_{0}<j\leq J}D_{j}(f)$, and
$|f(\mathbf{x})|^{p}\leq\frac{\varepsilon}{8}$ otherwise 444For details, we
refer to the proof of Theorem 5.1 in [5]. . As a result, for any probability
measure $\nu$ on $\Omega$, and any $f\in{\mathcal{S}}_{p}$, we have

$\Bigl{|}\|h(f)\|_{L_{p}(\nu)}^{p}-\|f\|_{L_{p}(\nu)}^{p}\Bigr{|}\leq\frac{\varepsilon}{8}\|f\|_{L_{p}(\nu)}^{p}+\frac{\varepsilon}{8}.$
(6.7)

Now for $j_{0}+1\leq j\leq J$, let

${\mathcal{F}}_{j}^{p}:=\left\\{M_{j}\cdot\chi_{D_{j}(f)}:\
f\in{\mathcal{S}}_{p}\right\\},\ \ \ \text{ where $M_{j}:=(1+a)^{pj}$.}$

Let $\\{\varepsilon_{j}\\}_{j=j_{0}+1}^{J}$ be a sequence of positive numbers
satisfying $\sum_{j=j_{0}+1}^{J}\varepsilon_{j}\leq\varepsilon/4$, which will
be specified later. By (6.6), for each $j_{0}<j\leq J$,

$\|M_{j}\chi_{D_{j}(f)}\|_{1}\leq\|h(f)\|_{p}^{p}\leq(1+\frac{\varepsilon}{8})\|f\|_{p}^{p}\leq
2.$

Thus, using (6.1) and Lemma 3.2, we conclude that the inequalities ,

$\displaystyle\sup_{\varphi\in\mathcal{F}_{j}^{p}}\Bigl{|}\frac{1}{m}\sum_{k=1}^{m}\varphi(\xi^{k})-\int_{\Omega}\varphi(x)\,d\mu(x)\Bigr{|}\leq\varepsilon_{j},\
\ \ j_{0}<j\leq J,$ (6.8)

hold simultaneously with probability

$\displaystyle\geq
1-\sum_{j=j_{0}+1}^{J}|{\mathcal{F}}_{j}^{p}|\exp\Bigl{(}-\frac{m\varepsilon_{j}^{2}}{16M_{j}}\Bigr{)}.$
(6.9)

Now we fix a set of random points $\xi^{1},\cdots,\xi^{m}$ for which (6.8) is
satisfied. Using (6.5), (6.8) and the triangle inequality, we then deduce

$\displaystyle\sup_{f\in{\mathcal{S}}_{p}}\Bigl{|}\frac{1}{m}\sum_{j=1}^{m}|h(f,\xi^{j})|^{p}-\|h(f)\|_{p}^{p}\Bigr{|}\leq\sum_{j=j_{0}+1}^{J}\varepsilon_{j}<\frac{\varepsilon}{4}.$

This together with (6.7) implies that for any $f\in{\mathcal{S}}_{p}$,

$\displaystyle\Bigl{|}\frac{1}{m}\sum_{j=1}^{m}|f(\xi^{j})|^{p}-1\Bigr{|}\leq\frac{3}{8}\varepsilon+\frac{\varepsilon}{8}\cdot\frac{1}{m}\sum_{j=1}^{m}|f(\xi^{j})|^{p},$

from which the desired inequality (6.3) follows.

Thus, to complete the proof, it remains to construct a sequence of positive
numbers $\\{\varepsilon_{j}\\}_{j=j_{0}+1}^{J}$ such that

$\sum_{j=j_{0}+1}^{J}\varepsilon_{j}\leq\varepsilon/4,$ (6.10)

and

$\displaystyle\sum_{j=j_{0}+1}^{J}|{\mathcal{F}}_{j}^{p}|\exp\Bigl{(}-\frac{m\varepsilon_{j}^{2}}{16M_{j}}\Bigr{)}\leq
C\varepsilon\exp\Bigl{(}-\frac{cm\varepsilon^{4}}{R^{p}(\log\frac{R}{\varepsilon})^{2}}\Bigr{)}.$
(6.11)

Since ${\mathcal{S}}_{p}\subset{\mathcal{W}}_{p}$, we can estimate the
cardinalities of the sets $\mathcal{F}_{j}^{p}$ as follows:

$|{\mathcal{F}}_{j}^{p}|\leq|\mathcal{A}_{j}|\times\cdots\times|\mathcal{A}_{J}|\leq\prod_{k=j}^{J}N_{a(1+a)^{k}}({\mathcal{W}}_{p},L_{\infty})=:L_{j}.$
(6.12)

A straightforward calculation shows that

$\displaystyle\log L_{j}$
$\displaystyle=\sum_{k=j}^{J}\mathcal{H}_{a(1+a)^{k}}({\mathcal{W}}_{p},L_{\infty})\leq
C\varepsilon^{-1}\int_{(1+a)^{j-1}}^{R}\mathcal{H}_{at}({\mathcal{W}}_{p},L_{\infty})\frac{dt}{t}.$
(6.13)

Now we specify the numbers $\varepsilon_{j}$ as follows:

$\varepsilon_{j}:={\delta}+\tau_{j},\ \ j_{0}<j\leq J,$

where ${\delta}:=\frac{\varepsilon}{8(J-j_{0})}$, and $\tau_{j}>0$ is defined
by

$\displaystyle 2\log L_{j}=\frac{m\tau_{j}^{2}}{16M_{j}},\ \ \ \text{that is}\
\ \tau_{j}:=4\sqrt{2}\sqrt{\frac{M_{j}\cdot\log L_{j}}{m}}.$ (6.14)

We have

$\displaystyle\sum_{j=j_{0}+1}^{J}\varepsilon_{j}$
$\displaystyle=4\sqrt{2}m^{-1/2}\sum_{j=j_{0}+1}^{J}(M_{j}\log
L_{j})^{\frac{1}{2}}+\frac{\varepsilon}{8},$

which, by (6.13) and straightforward calculations, is estimated above by

$\displaystyle\leq\frac{\varepsilon}{8}+Cm^{-\frac{1}{2}}\varepsilon^{-\frac{3}{2}}\int_{4^{-1}(10^{-1}\varepsilon)^{1/p}}^{R}u^{\frac{p}{2}-1}\Bigl{(}\int_{u}^{R}\mathcal{H}_{c_{p}\varepsilon
t}({\mathcal{W}}_{p},L_{\infty})\frac{dt}{t}\Bigr{)}^{\frac{1}{2}}du.$

Thus, to ensure (6.10), it is enough to assume that

$m\geq
C\varepsilon^{-5}\Bigg{[}\int_{4^{-1}(10^{-1}\varepsilon)^{1/p}}^{R}u^{\frac{p}{2}-1}\Bigl{(}\int_{u}^{R}\mathcal{H}_{c_{p}\varepsilon
t}({\mathcal{W}}_{p},L_{\infty})\frac{dt}{t}\Bigr{)}^{\frac{1}{2}}du\Bigg{]}^{2}$

with $C=C_{p}$ being a large constant depending only on $p$.

Finally, we estimate the sum

$S:=\sum_{j=j_{0}+1}^{J}|{\mathcal{F}}_{j}^{p}|\exp\Bigl{(}-\frac{m\varepsilon_{j}^{2}}{16M_{j}}\Bigr{)}.$

Since $\varepsilon_{j}^{2}\geq\tau_{j}^{2}+{\delta}^{2}$, we obtain from
(6.12) that

$\displaystyle S$ $\displaystyle\leq\sum_{j=j_{0}+1}^{J}\exp\Bigl{(}\log
L_{j}-\frac{m\tau_{j}^{2}}{16M_{j}}-\frac{m{\delta}^{2}}{16M_{j}}\Bigr{)}\leq\exp\Bigl{(}-\frac{m{\delta}^{2}}{16M_{J}}\Bigr{)}\sum_{j=j_{0}+1}^{J}\frac{1}{L_{j}}.$

Using (6.4), we have

$\frac{m{\delta}^{2}}{16M_{J}}=m\cdot\Bigl{(}\frac{\varepsilon}{8(J-j_{0})}\Bigr{)}^{2}\cdot\frac{1}{16M_{J}}\geq\frac{cm\varepsilon^{4}}{R^{p}(\log\frac{R}{\varepsilon})^{2}}.$

Since

$L_{j}\geq N_{a(1+a)^{j}}({\mathcal{W}}_{p},L_{\infty}),$

this implies

$\displaystyle S$
$\displaystyle\leq\exp\Bigl{(}-\frac{cm\varepsilon^{4}}{R^{p}(\log\frac{R}{\varepsilon})^{2}}\Bigr{)}\sum_{j=j_{0}+1}^{J}\frac{1}{N_{a(1+a)^{j}}({\mathcal{W}}_{p},L_{\infty})}.$

On the other hand, from the proof of Theorem 5.1 in [5], we know that

$N_{t}({\mathcal{W}}_{p},L_{\infty})\geq\frac{R}{4t},\ \ \ \forall 0<t<R.$
(6.15)

It follows that

$\displaystyle
S\leq\exp\Bigl{(}-\frac{cm\varepsilon^{4}}{R^{p}(\log\frac{R}{\varepsilon})^{2}}\Bigr{)}\cdot
4c_{\ast}R^{-1}\varepsilon\sum_{j=j_{0}+1}^{J}(1+a)^{j}\leq\varepsilon\exp\Bigl{(}-\frac{cm\varepsilon^{4}}{R^{p}(\log\frac{R}{\varepsilon})^{2}}\Bigr{)},$

which is as desired. This completes the proof.

∎

Acknowledgment. The authors thank Tino Ullrich for bringing to their attention
the paper [8]. They would also like to express their gratitude to the referee
for carefully reading this paper and providing valuable suggestions and
comments.

## References

  * [1] J. Bourgain, J. Lindenstrauss and V. Milman, Approximation of zonoids by zonotopes, Acta Math., 162 (1989), 73–141.
  * [2] J. Bourgain, An improved estimate in the restricted isometry problem, In Geometric Aspects of Functional Analysis, volume 2116 of Lecture Notes in Mathematics, pages 65–70. Springer, 2014.
  * [3] A. Cohen and G. Migliorati, Optimal weighted least-squares methods, SMAI J. Computational Mathematics 3 (2017), 181–203.
  * [4] F. Dai, A. Prymak, V.N. Temlyakov, and S.U. Tikhonov, Integral norm discretization and related problems, Russian Math. Surveys 74:4 (2019), 579–630. Translation from Uspekhi Mat. Nauk 74:4(448) (2019), 3–58; arXiv:1807.01353v1.
  * [5] F. Dai and V. Temlyakov, Universal sampling discretization, arXiv:2107.11476v1 [math.FA] 23 Jul 2021. Constr Approx (2023). https://doi.org/10.1007/s00365-023-09644-2
  * [6] F. Dai and V. Temlyakov, Universal discretization and sparse sampling recovery, arXiv:2301.05962v1 [math.NA] 14 Jan 2023.
  * [7] S. Foucart and H. Rauhut, A Mathematical Introduction to Compressive Sensing, Birkhäuser, 2013.
  * [8] I. Haviv and O. Regev, The restricted isometry property of subsampled Fourier matrices, In Geometric aspects of functional analysis, volume 2169 of Lecture Notes in Math., pages 163–179. Springer, Cham, 2017.
  * [9] T. Jahn, T. Ullrich, and F. Voigtlaender, Sampling numbers of smoothness classes via $\ell^{1}$-minimization, arXiv:2212.00445v1 [math.NA] 1 Dec 2022.
  * [10] B. Kashin, E. Kosov, I. Limonova, and V. Temlyakov, Sampling discretization and related problems, Journal of Complexity, 71 (2022), 101653; arXiv:2109.07567v1 [math.FA] 15 Sep 2021.
  * [11] E. Livshitz and V. Temlyakov, Sparse approximation and recovery by greedy algorithms, IEEE Transactions on Information Theory, 60 (2014), 3989–4000; arXiv: 1303.3595v1 [math.NA] 14 Mar 2013.
  * [12] W. M. Schmidt, Diophantine approximation. Lecture Notes in Mathematics 785, Springer, 1980.
  * [13] V.N. Temlyakov, Weak greedy algorithms, Adv. Comput. Math. 12 (2000), 213–227.
  * [14] V.N. Temlyakov, Greedy Approximation, Cambridge University Press, 2011.
  * [15] V.N. Temlyakov, An inequality for the entropy numbers and its application, J. Approx. Theory , 173 (2013), 110–121.
  * [16] V.N. Temlyakov, Constructive sparse trigonometric approximation and other problems for functions with mixed smoothness, arXiv: 1412.8647v1 [math.NA] 24 Dec 2014, 1–37; Matem. Sb., 206 (2015), 131–160.
  * [17] V. Temlyakov, Multivariate Approximation, Cambridge University Press, 2018.

F. Dai,  Department of Mathematical and Statistical Sciences
University of Alberta
Edmonton, Alberta T6G 2G1, Canada
E-mail<EMAIL_ADDRESS>
V.N. Temlyakov, University of South Carolina,
Steklov Institute of Mathematics,
Lomonosov Moscow State University,
and Moscow Center for Fundamental and Applied Mathematics.
E-mail<EMAIL_ADDRESS>