| Sbornik: Mathematics |
|
|
|
|
|
This article is cited in 4 scientific papers (total in 4 papers) Sparse sampling recovery in integral norms on some function classes V. N. Temlyakovabcd a Steklov Mathematical Institute of Russian Academy of Sciences, Moscow, Russia b Lomonosov Moscow State University, Moscow, Russia c Moscow Center of Fundamental and Applied Mathematics, Moscow, Russia d University of South Carolina, Columbia, SC, USA
Bibliographic databases:
    § 1. IntroductionThis paper is a followup of the recent paper [18]. We formulate here the results from [18] that we use in our analysis. The reader can find in [18] a discussion of the previous results connected directly with the ones in [18] and in this paper. Results on discretization can be found in the recent survey papers [2] and [10]. We begin with a brief description of some necessary concepts on sparse approximation. Let $X$ be a Banach space with the norm $\|\,{\cdot}\,\|:=\|\,{\cdot}\,\|_X$, and let $\mathcal{D}=\{g_i\}_{i=1}^\infty $ be a given (countable) system of elements of $X$. Given a finite subset $J\subset \mathbb{N}$, we define $V_J(\mathcal{D}):=\operatorname{span}\{g_j\colon j\in J\}$. For a positive integer $v$, we denote by $\mathcal{X}_v(\mathcal{D})$ the collection of all linear spaces $V_J(\mathcal{D})$ with $|J|=v$, and denote by $\Sigma_v(\mathcal{D})$ the set of all $v$-term approximants with respect to $\mathcal{D}$, that is, $\Sigma_v(\mathcal D):=\bigcup_{V\in\mathcal X_v(\mathcal D)} V$. Given $f\in X$, we set
$$
\begin{equation*}
\sigma_v(f,\mathcal D)_X:=\inf_{g\in\Sigma_v(\mathcal D)}\|f-g\|_X, \qquad v=1,2,\dots\,.
\end{equation*}
\notag
$$
Moreover, for a function class $\mathbf{F}\subset X$, we define
$$
\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
$$
In this paper we consider the case when $X=L_p(\Omega,\mu)$, $1\leqslant p<\infty$. More precisely, let $\Omega$ be a compact subset of $\mathbb{R}^d$ with the probability measure $\mu$ on it. By the $L_p$-norm, $1\leqslant p< \infty$, of a complex-valued function defined on $\Omega$, we understand
$$
\begin{equation*}
\|f\|_p:=\|f\|_{L_p(\Omega,\mu)}:=\biggl(\int_\Omega |f|^p\,d\mu\biggr)^{1/p}.
\end{equation*}
\notag
$$
In the case when $X=L_p(\Omega,\mu)$ we sometimes write for brevity $\sigma_v(\,{\cdot}\,{,}\,{\cdot}\,)_p$ instead of $\sigma_v(\,{\cdot}\,{,}\,{\cdot}\,)_{L_p(\Omega,\mu)}$. We study systems that have the universal sampling discretization property. Definition 1.1. Let $1\leqslant p<\infty$. We say that a set $\xi:= \{\xi^j\}_{j=1}^m \subset \Omega$ provides $L_p$-universal sampling discretization for the collection $\mathcal{X}:= \{X(n)\}_{n=1}^k$ of finite-dimensional linear subspaces $X(n)$ if We will use the brief form $L_p$-usd for $L_p$-universal sampling discretization (1.1). We let $C$, $C'$ and $c$, $c'$ denote various positive constants. Their arguments indicate the parameters they can depend on. Normally, these constants do not depend on the function $f$ or the running parameters $m$, $v$ and $u$. We use the following symbols for brevity. For two nonnegative sequences $a=\{a_n\}_{n=1}^\infty$ and $b=\{b_n\}_{n=1}^\infty$ the relation $a_n\ll b_n$ means that there is a number $C(a,b)$ such that for all $n$ we have $a_n\leqslant C(a,b)b_n$. The relation $a_n\gg b_n$ means that $b_n\ll a_n$, and $a_n\asymp b_n$ means that $a_n\ll b_n$ and $a_n \gg b_n$. For a real number $x$ we denote by $[x]$ the integer part of $x$, and $\lceil x\rceil$ is the smallest integer greater than or equal to $x$. For a set $\xi$ of $m$ points in $\Omega$ we put
$$
\begin{equation}
\Omega_m:=\xi:=\{\xi^1,\dots, \xi^m\}\subset \Omega, \qquad\mu_m:=\frac1{m}\sum_{j=1}^m \delta_{\xi^j} \quad\text{and}\quad\mu_\xi:= \frac{\mu+\mu_m}{2},
\end{equation}
\tag{1.2}
$$
where $\delta_\mathbf{x}$ denotes the Dirac measure supported at a point $\mathbf{x}$. For convenience we will use the notation $\|\,{\cdot}\,\|_{L_p(\nu)}$ to denote the norm in $L_p$ with respect to the measure $\nu$ on $\Omega$. Sometimes we use the notation $\|\,{\cdot}\,\|_{p}$. The main goal of this paper is to study optimal recovery on specific classes of multivariate functions. For a function class $\mathbf{F}\subset \mathcal{C}(\Omega)$ we define (see [19])
$$
\begin{equation*}
\varrho_m^{\rm o}({\mathbf F},L_p):=\inf_{\xi } \inf_{\mathcal M} \sup_{f\in {\mathbf F}}\|f-\mathcal M(f(\xi^1),\dots,f(\xi^m))\|_p,
\end{equation*}
\notag
$$
where $\mathcal{M}$ ranges over all mappings $\mathcal{M}\colon \mathbb{C}^m \to L_p(\Omega,\mu)$ and $\xi$ ranges over all subsets $\{\xi^1,\dots,\xi^m\}$ of $m$ points in $\Omega$. Here we use the index ‘o’ to indicate optimality. In [18] we studied the behaviour of $\varrho_m^{\rm o}(\mathbf{F},L_p)$ for a new kind of classes, $\mathbf{A}^r_\beta(\Psi)$. We obtained the order of $\varrho_m^{\rm o}(\mathbf{A}^r_\beta(\Psi),L_p)$ (up to a factor logarithmic in $m$) in the case $1\leqslant p\leqslant 2$ for the class of uniformly bounded orthonormal systems $\Psi$. We give a definition of the classes $\mathbf{A}^r_\beta(\Psi)$. Given $p$, $1\leqslant p\leqslant \infty$, let $\Psi =\{\psi_{\mathbf{k}}\}_{\mathbf{k} \in \mathbb{Z}^d}$, $\psi_\mathbf{k} \in \mathcal{C}(\Omega)$, $\|\psi_\mathbf{k}\|_p \leqslant B$, $\mathbf{k}\in\mathbb{Z}^d$, be a system in the space $L_p(\Omega,\mu)$. We consider functions representable in the form of an absolutely convergent series:
$$
\begin{equation}
f=\sum_{{\mathbf k}\in\mathbb Z^d} a_{\mathbf k}(f)\psi_{\mathbf k}, \qquad \sum_{{\mathbf k}\in\mathbb Z^d} |a_{\mathbf k}(f)|<\infty.
\end{equation}
\tag{1.3}
$$
For $\beta \in (0,1]$ and $r>0$ consider the class $\mathbf{A}^r_\beta(\Psi)$ of functions $f$ that have representations (1.3) satisfying the following conditions:
$$
\begin{equation}
\biggl(\sum_{[2^{j-1}]\leqslant \|{\mathbf k}\|_\infty <2^j} |a_{\mathbf k}(f)|^\beta\biggr)^{1/\beta} \leqslant 2^{-rj}, \qquad j=0,1,\dots\, .
\end{equation}
\tag{1.4}
$$
In the special case when $\Psi$ is the trigonometric system $\mathcal{T}^d := \{e^{i(\mathbf{k},\mathbf{x})}\}_{\mathbf{k}\in \mathbb{Z}^d}$ we proved the following lower bound in [18] (see Theorem 4.6 there):
$$
\begin{equation}
\varrho_m^{\rm o}({\mathbf A}^r_\beta(\mathcal T^d),L_1) \gg m^{1/2-1/\beta-r/d}.
\end{equation}
\tag{1.5}
$$
In [18] we complemented this lower bound by the following upper bound. Assume that $\Psi$ is a uniformly bounded orthonormal system: $\|\psi_\mathbf{k}\|_\infty \leqslant B$, $\mathbf{k}\in\mathbb{Z}^d$. Let ${1\leqslant p\leqslant 2}$, $\beta \in (0,1]$ and $r>0$; then
$$
\begin{equation}
\begin{aligned} \, \notag \varrho_{m}^{\rm o}({\mathbf A}^r_\beta(\Psi),L_p(\Omega,\mu)) &\leqslant \varrho_{m}^{\rm o}({\mathbf A}^r_\beta(\Psi),L_2(\Omega,\mu)) \\ &\ll (m(\log(m+1))^{-5})^{1/2 -1/\beta-r/d}. \end{aligned}
\end{equation}
\tag{1.6}
$$
It was noted in [18] that $(\log(m+1))^{-5}$ in (1.6) can be replaced by $(\log(m+1))^{-4}$. Bounds (1.5) and (1.6) show that, generally, for uniformly bounded orthonormal systems $\Psi$, for instance, for the trigonometric system $\mathcal{T}^d$, the gap between the upper and lower bounds is in terms of an extra factor logarithmic in $m$. In this paper, alike [18], we study the special case when $\Psi$ satisfies certain restrictions. We formulate these restrictions in the form of conditions imposed on $\Psi$. Condition A. Assume that $\Psi$ is a uniformly bounded system. Namely, assume that $\Psi:=\{\varphi_j\}_{j=1}^\infty$ is a system of uniformly bounded functions on $\Omega \subset \mathbb{R}^d$ such that Condition B2. Assume that $\Psi$ is a Riesz system, that is, for each $N\in\mathbb{N}$ and any $(a_1,\dots, a_N) \in\mathbb{C}^N$, where $0< R_1 \leqslant R_2 <\infty$. Condition B3. Assume that $\Psi$ is a Bessel system, that is, there exists a constant $K>0$ such that for all $N\in\mathbb{N}$ and any $(a_1,\dots, a_N) \in\mathbb{C}^N$, Clearly, Condition B1 implies Condition B2 for $R_1=R_2=1$. Condition B2 implies Condition B3 for $K=R_1^{-2}$. In the case $2<p<\infty$ the following upper bounds were proved in [18] (see Theorem 4.2 and Remark 6.1 there). Theorem 1.1 ([18]). Assume that $\Psi$ is a uniformly bounded Riesz system (in the space $L_2(\Omega,\mu)$) satisfying (1.7) and (1.8) for some constants ${0<R_1\leqslant R_2<\infty}$. Let $2<p<\infty$, $\beta \in (0,1]$ and $r>0$. Then there exist constants $c'=c'(r,\beta,p,R_1,R_2,d)$ and $C'=C'(r,\beta,p,d)$ such that for each $v\in\mathbb{N}$ we have the bound for any $m$ satisfying In the proof of Theorem 1.1 known results about universal $L_p$-discretization played an important role. We formulate the corresponding result. Theorem 1.2 ([3]). Assume that $\mathcal{D}_N=\{\varphi_j\}_{j=1}^N$ is a uniformly bounded Riesz system satisfying (1.7) and (1.8) for some constants $0<R_1\leqslant R_2<\infty$. Let $2<p<\infty$, and let $1\leqslant u\leqslant N$ be an integer. Then for a sufficiently large constant $C=C(p,R_1,R_2)$ and any $\varepsilon\in (0, 1)$ there exist $m$ points $\xi^1,\dots, \xi^m\in \Omega$, where such that for each $f\in \Sigma_u(\mathcal{D}_N)$, For a uniformly bounded Riesz system $\Psi$ Theorem 1.1 gives the following upper bound:
$$
\begin{equation}
\varrho_{m}^{\rm o}({\mathbf A}^r_\beta(\Psi),L_p(\Omega,\mu)) \ll \biggl(\frac{m}{(\log m)^2}\biggr)^{(2/p)(1/2 -1/\beta -r/d)} .
\end{equation}
\tag{1.12}
$$
In this paper we improve (1.12). For a uniformly bounded Riesz system $\Psi$ Corollary 5.1 (see below) gives for $2\leqslant p<\infty$ the inequality
$$
\begin{equation}
\varrho_{m}^{\rm o}({\mathbf A}^r_\beta(\Psi),L_p(\Omega,\mu)) \ll \biggl(\frac{m}{(\log m)^4}\biggr)^{1-1/p -1/\beta -r/d} .
\end{equation}
\tag{1.13}
$$
Moreover, the bound (1.13) is provided by a simple greedy algorithm, the Weak Orthogonal Matching Pursuit (see the definition below). The upper bound (5.11) and the lower bound from Proposition 5.1 give us the following inequalities in the special case of the $d$-variate trigonometric system $\mathcal{T}^d$:
$$
\begin{equation}
m^{1-1/p -1/\beta -r/d}\ll \varrho_{m}^{\rm o}({\mathbf A}^r_\beta(\mathcal T^d),L_p) \ll \biggl(\frac{m}{(\log m)^3}\biggr)^{1-1/p -1/\beta -r/d} .
\end{equation}
\tag{1.14}
$$
A further discussion can be found in § 6. § 2. PreliminariesThe Weak Orthogonal Matching Pursuit (WOMP) is a greedy algorithm defined with respect to a given dictionary (system) $\mathcal{D}=\{g\}$ in a Hilbert space equipped with an inner product $\langle\,\cdot\,{,}\,\cdot\,\rangle$ and a norm $\|\,{\cdot}\,\|_H$. It is also known under the name of the Weak Orthogonal Greedy Algorithm (see, for instance, [15]). The Weak Orthogonal Matching Pursuit (WOMP)Let $\mathcal{D}=\{g\}$ be a system of nonzero elements of $H$ such that $\|g\|_H\leqslant 1$. 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 residuals for $k=1,2,\dots$ recursively as follows.
In the case when $t_k=1$ for $k=1,2,\dots$ the 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 delivers the corresponding supremum. The obvious reason for this is that we do not know in general if an optimal element exists. Another practical reason is that the weaker the assumption, the easier it is to realize in practice. Clearly, $g_k$ may not be unique. However, all results formulated below are independent of the choice of the $g_k$. For the sake of convenience in applications that follow we use the notation $\mathrm{WOMP}(\mathcal{D}; t)_H$ to denote the WOMP defined with respect to a given weakness parameter $t\in (0, 1]$ and a system $\mathcal{D}$ in a Hilbert space $H$. $\mathbf{UP}(u,D)$: the $(u,D)$-unconditional propertyWe say that a system $\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\leqslant u\leqslant D$ if for each $f=\sum_{i\in A} c_i \varphi_i\in \Sigma_u(\mathcal{D})$, where $A\subset I$, and each $J\subset I\setminus A$ such that $|A|+|J| \leqslant D$ we have
$$
\begin{equation}
\biggl\|\sum_{i\in A} c_i \varphi_i\biggr\|\leqslant U\inf_{g\in V_J(\mathcal D)}\biggl \|\sum_{i\in A} c_i \varphi_i-g\biggr\|,
\end{equation}
\tag{2.1}
$$
where $ V_J(\mathcal{D}):=\operatorname{span}\{\varphi_i\colon i\in J\}$. We gave the above definition for a countable (or finite) system $\mathcal{D}$. A similar definition can also be given for any system $\mathcal{D}$. Theorem 2.1 ([11], Corollary 1.1). Let $\mathcal{D}$ be a dictionary in a Hilbert space $H=(H, \|\,{\cdot}\,\|)$ having the property $\mathbf{UP}(u,D)$ with constant $U>0$ for some integers $1\leqslant u\leqslant 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 $\mathrm{WOMP}(\mathcal{D}; t)_H$, as applied to $f_0$, gives where $C>1$ is an absolute constant and $f_k$ denotes the residual of $f_0$ after the $k$th iteration of the algorithm. 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 providing good universal discretization, and $\mu_m$ is the uniform probability measure on $\Omega_m$, that is, $\mu_m\{\xi^\nu\}=1/m$, $\nu=1,\dots,m$. Let $\mathcal{D}_N(\Omega_m)$ denote the restriction of the system $\mathcal{D}_N$ to the set $\Omega_m$. Theorem 2.2 below guarantees that the simple greedy algorithm WOMP gives us the corresponding Lebesgue-type inequality in the norm $L_2(\Omega_m,\mu_m)$, and therefore provides good sparse recovery. Theorem 2.2 ([4]). Let $\mathcal{D}_N=\{\varphi_j\}_{j=1}^N$ be a uniformly bounded Riesz basis in $L_2(\Omega, \mu)$ satisfying (1.7) and (1.8) for some constants $0<R_1\leqslant R_2<\infty$. Let $\Omega_m=\{\xi^1,\dots, \xi^m\}$ be a finite subset of $\Omega$ providing $L_2$-universal discretization (1.1) for the collection $\mathcal{X}_u(\mathcal{D}_N)$ and the given integers $1\leqslant u\leqslant N$. Given a weakness parameter $0<t\leqslant 1$, there exists a constant integer $c=c(t,R_1,R_2)\geqslant 1$ such that for any integer $0\leqslant v\leqslant u/(1+c)$ and any $f_0\in \mathcal{C}(\Omega)$ the Recall that the modulus of smoothness of a Banach space $X$ is defined by
$$
\begin{equation}
\eta(w):=\eta(X,w):=\sup_{x,y\in X\colon \|x\|=\|y\|=1}\biggl[\frac{\|x+wy\|+\|x-wy\|}{2} -1\biggr], \qquad w>0,
\end{equation}
\tag{2.4}
$$
and that $X$ is said to be uniformly smooth if $\eta(w)/w\to 0$ as $w\to 0+$. It is well known that for $1< p<\infty$ the $L_p$-space is a uniformly smooth Banach space with
$$
\begin{equation}
\eta(L_p,w)\leqslant \begin{cases} \dfrac{(p-1)w^2}2, & 2\leqslant p <\infty, \\ \dfrac{w^p}p,& 1\leqslant p\leqslant 2. \end{cases}
\end{equation}
\tag{2.5}
$$
§ 3. New results on upper boundsIn addition to the conditions on a system $\Psi$ formulated in the introduction (§ 1) we need one more property of the system $\Psi$. The $u$-term Nikol’skii inequalityLet $1\leqslant q\leqslant p\leqslant \infty$, and let $\Psi$ be a system in $L_p:=L_p(\Omega,\mu)$. For a natural number $u$ we say that the system $\Psi$ satisfies the $u$-term Nikol’skii inequality for the pair $(q,p)$ with constant $H$ if the following inequality holds:
$$
\begin{equation}
\|f\|_p \leqslant H\|f\|_q \quad \forall\, f\in \Sigma_u(\Psi).
\end{equation}
\tag{3.1}
$$
In such a case we write $\Psi \in \mathrm{NI}(q,p,H,u)$. Note, that obviously $H\geqslant 1$. Theorem 3.1. Let $\mathcal{D}_N=\{\varphi_j\}_{j=1}^N$ be a uniformly bounded Riesz system in $L_2(\Omega, \mu)$ satisfying (1.7) and (1.8) for some constants $0<R_1\leqslant R_2<\infty$. Let $\Omega_m=\{\xi^1,\dots, \xi^m\}$ be a finite subset of $\Omega$ that provides $L_2$-universal discretization for the collection $\mathcal{X}_u(\mathcal{D}_N)$, $1\leqslant u\leqslant N$. Assume, in addition, that $\mathcal{D}_N \in \mathrm{NI}(2,p,H,u)$ for some $p\in [2,\infty)$. Then, given a weakness parameter $0<t\leqslant 1$, there exists a constant integer $c=c(t,R_1,R_2)\geqslant 1$ such that for any integer $0\leqslant v\leqslant u/(1+c)$ and any $f_0\in \mathcal{C}(\Omega)$, the Proof. We begin with inequality (3.2). It follows from (2.2) in Theorem 2.2. For completeness we give its simple proof here. Using (1.8) we obtain that for any sets $A\subset \{1,2,\dots, N\}$ and $\Lambda\subset \{1,\dots, N\}\setminus A$ and any sequences $\{x_i\}_{i\in A}$ and $\{c_i\}_{i\in\Lambda}\subset\mathbb{C}$,
$$
\begin{equation*}
\biggl\|\sum_{i\in A}x_i\varphi_i-\sum_{i\in\Lambda}c_i\varphi_i\biggr\|_{L_2(\Omega,\mu)}^2 \geqslant R_1^2 \sum_{i\in A} |x_i|^2 \geqslant R_2^{-2} R_1^2\biggl \|\sum_{i\in A}x_i\varphi_i \biggr\|_{L_2(\Omega,\mu)}^2,
\end{equation*}
\notag
$$
meaning that the system $\mathcal{D}_N$ has the $\mathbf{UP}(v,N)$ property with constant $U_1 = R_2/R_1$ in the space $L_2(\Omega,\mu)$ for any integer $1\leqslant v< N$. Then it follows from the discretization inequalities (1.1) for $\mathbf{\mathcal{X}}=\mathbf{\mathcal{X}}_u(\mathcal{D}_N)$ that the system $\mathcal{D}:=\mathcal{D}_N(\Omega_m)$, which is the restriction of $\mathcal{D}_N$ to $\Omega_m=\{\xi^1, \dots,\xi^m\}$, has the property $\mathbf{UP}(v,u)$ in the space $L_2(\Omega_m,\mu_m)$ with constant $U_2 =U_1 3^{1/2}$ for any integers $1\leqslant v\leqslant u$. Thus, applying Theorem 2.1 to the discretized dictionary $\mathcal{D}_N(\Omega_m)$ in the Hilbert space $L_2(\Omega_m,\mu_m)$, we conclude that the algorithm
$$
\begin{equation*}
\mathrm{WOMP}\bigl(\mathcal D_N(\Omega_m); t\bigr)_{L_2(\Omega_m,\mu_m)},
\end{equation*}
\notag
$$
as applied to $f_0\bigl|_{\Omega_m} $, gives
$$
\begin{equation*}
\|f_{cv}\|_{L_2(\Omega_m,\mu_m)}\leqslant C_0\sigma_v(f_0,\mathcal D_N(\Omega_m))_{L_2(\Omega_m,\mu_m)}
\end{equation*}
\notag
$$
whenever $v+c v\leqslant u$, where $c =c(t, R_1, R_2)\in\mathbb{N}$. This proves (3.2) in Theorem 3.1.
Now we derive (3.3) from (3.2). Let $h\in \Sigma_v(\mathcal{D}_N)$ be such that
$$
\begin{equation*}
\|f_0-h\|_{L_p(\mu_\xi)}=\sigma_v(f_0,\mathcal D_N)_{L_p(\mu_\xi)}.
\end{equation*}
\notag
$$
Then we have
$$
\begin{equation*}
\|f_{cv}\|_{L_p(\Omega,\mu)} \leqslant \|h-f_0\|_{L_p(\Omega,\mu)}+\|h-G_{cv}(f_0,\mathcal D_N(\Omega_m))\|_{L_p(\Omega,\mu)}.
\end{equation*}
\notag
$$
First we estimate
$$
\begin{equation*}
\|h-f_0\|_{L_p(\Omega,\mu)} \leqslant 2^{1/p}\|h-f_0\|_{L_p(\mu_\xi)}=2^{1/p}\sigma_v(f_0,\mathcal D_N)_{L_p(\mu_\xi)}.
\end{equation*}
\notag
$$
Second, using that $h - G_{cv}(f_0,\mathcal{D}_N(\Omega_m)) \in \Sigma_u(\mathcal{D}_N)$, from our assumption $\mathcal{D}_N \in \mathrm{NI}(2,p,H,u)$ and the discretization (1.1) we conclude that
$$
\begin{equation}
\begin{aligned} \, \notag \|h-G_{cv}(f_0,\mathcal D_N(\Omega_m))\|_{L_p(\Omega,\mu)} &\leqslant H \|h- G_{cv}(f_0,\mathcal D_N(\Omega_m))\|_{L_2(\Omega,\mu)} \\ &\leqslant 2^{1/2}H\|h-G_{cv}(f_0,\mathcal D_N(\Omega_m))\|_{L_2(\Omega_m,\mu_m)}. \end{aligned}
\end{equation}
\tag{3.4}
$$
Next, (3.2) implies that
$$
\begin{equation*}
\begin{aligned} \, &\|h-G_{cv}(f_0,\mathcal D_N(\Omega_m))\|_{L_2(\Omega_m,\mu_m)} \leqslant \|h-f_0\|_{L_2(\Omega_m,\mu_m)}+\|f_{cv}\|_{L_2(\Omega_m,\mu_m)} \\ &\qquad \leqslant \|h-f_0\|_{L_p(\Omega_m,\mu_m)}+C_0\sigma_v(f_0,\mathcal D_N(\Omega_m))_{L_2(\Omega_m,\mu_m)} \\ &\qquad \leqslant 2^{1/p}(\|h-f_0\|_{L_p(\mu_\xi)}+C_0\sigma_v(f_0,\mathcal D_N(\Omega_m))_{L_p(\mu_\xi)}) \\ &\qquad \leqslant 2^{1/p}(1+C_0)\sigma_v(f_0,\mathcal D_N)_{L_p(\mu_\xi)}. \end{aligned}
\end{equation*}
\notag
$$
This and (3.4) imply that Finally, which completes the proof. For brevity set $L_p(\xi) := L_p(\Omega_m,\mu_m)$, where $\Omega_m=\{\xi^\nu\}_{\nu=1}^m$ and $\mu_m(\xi^\nu) =1/m$, $\nu=1,\dots,m$. Let $B_v(f,\mathcal{D}_N,L_p(\xi))$ denote the best $v$-term approximation of $f$ in the $L_p(\xi)$-norm with respect to the system $\mathcal{D}_N$. Note that $B_v(f,\mathcal{D}_N,L_p(\xi))$ may not be unique. It is obvious that
$$
\begin{equation}
\|f-B_v(f,\mathcal D_N,L_p(\xi))\|_{L_p(\xi)}=\sigma_v(f,\mathcal D_N)_{L_p(\xi)}.
\end{equation}
\tag{3.6}
$$
We proved the following theorem in [5]. Theorem 3.2 ([5]). Let $1\leqslant p<\infty$ and let $m$, $v$ and $N$ be given 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 one-sided $L_p$-universal discretization, Now we prove a version of Theorem 3.2. Theorem 3.3. Let $2\leqslant p\leqslant \infty$, and let $m$, $v$, and $N$ be given natural numbers such that $2v\leqslant N$. Let $\mathcal{D}_N\subset \mathcal{C}(\Omega)$ be a system of $N$ elements such that $\mathcal{D}_N \in \mathrm{NI}(2,p,H,2v)$. Assume that there exists a set $\xi:= \{\xi^j\}_{j=1}^m \subset \Omega$ that provides one-sided $L_2$-universal discretization Proof. The proofs of inequalities (3.11) and (3.12) are similar. We begin with (3.11). For brevity set $g:= B_v(f,\mathcal{D}_N,L_2(\xi))$ and $h:=B_v(f,\mathcal{D}_N,L_p(\mu_\xi))$. Then
$$
\begin{equation*}
\|f-g\|_{L_p(\mu)} \leqslant \|f-h\|_{L_p(\mu)}+\|h-g\|_{L_p(\mu)}.
\end{equation*}
\notag
$$
First, we estimate
$$
\begin{equation*}
\|f-h\|_{L_p(\mu)} \leqslant 2^{1/p} \|f-h\|_{L_p(\mu_\xi)}=2^{1/p} \sigma_v(f,\mathcal D_N)_{L_p(\mu_\xi)}.
\end{equation*}
\notag
$$
Second, using the obvious fact that $h-g\in \Sigma_{2v}(\mathcal{D}_N)$, from the assumption $\mathcal{D}_N \in \mathrm{NI}(2,p,H,2v)$ we obtain and continue by using (3.10) and the trivial inequality $\|f-g\|_{L_2(\xi)} \leqslant \|f-h\|_{L_2(\xi)}$:
$$
\begin{equation*}
\begin{aligned} \, \|h-g\|_{L_p(\mu)} &\leqslant HD \|h-g\|_{L_2(\xi)} \leqslant 2HD \|f-h\|_{L_2(\xi)} \leqslant 2HD \|f-h\|_{L_p(\xi)} \\ & \leqslant 2^{1+1/p}HD \|f-h\|_{L_p(\mu_\xi)}=2^{1+1/p}HD \sigma_v(f,\mathcal D_N)_{L_p(\mu_\xi)}. \end{aligned}
\end{equation*}
\notag
$$
Combining the above inequalities we complete the proof of (3.11).
Now we prove (3.12). Set $g:= B_v(f,\mathcal{D}_N,L_2(\xi))$ and $h:=B_v(f,\mathcal{D}_N,L_\infty)$. Then First, we estimate
$$
\begin{equation*}
\|f-h\|_p \leqslant \|f-h\|_\infty=\sigma_v(f,\mathcal D_N)_\infty.
\end{equation*}
\notag
$$
Second, using the obvious fact that $h-g\in \Sigma_{2v}(\mathcal{D}_N)$, from the assumption $\mathcal{D}_N \in \mathrm{NI}(2,p,H,2v)$ we obtain and continue by using (3.10) and the trivial inequality $\|f-g\|_{L_2(\xi)} \leqslant \|f-h\|_{L_2(\xi)}$:
$$
\begin{equation*}
\begin{aligned} \, \|h-g\|_p &\leqslant HD \|h-g\|_{L_2(\xi)} \leqslant 2HD \|f-h\|_{L_2(\xi)} \\ &\leqslant 2 HD \|f-h\|_\infty=2 HD \sigma_v(f,\mathcal D_N)_\infty. \end{aligned}
\end{equation*}
\notag
$$
Combining the above inequalities we complete the proof of (3.12).
The theorem is proved. § 4. New results on lower boundsLet us discuss lower bounds for the nonlinear characteristic $\varrho_m^{\rm o}(\mathbf{A}^r_\beta(\Psi),L_p)$. We do this in the special case when $\Psi$ is the trigonometric system $\mathcal{T}^d \mkern-1mu\!:=\!\mkern-1mu \{\mkern-1.5mu e^{i(\mathbf{k},\mathbf{x})}\mkern-1.5mu\}_{\mathbf{k}\in \mathbb{Z}^d}$. For $\mathbf{N} = (N_1,\dots,N_d)$, $N_j\in \mathbb{N}_0$, $j=1,\dots,d$, set
$$
\begin{equation*}
\mathcal T({\mathbf N},d):=\biggl\{f=\sum_{{\mathbf k}\colon |k_j|\leqslant N_j, \,j=1,\dots,d} c_j e^{i({\mathbf k},{\mathbf x})}\biggr\}\quad\text{and}\quad \vartheta({\mathbf N}):=\prod_{j=1}^d (2N_j+1).
\end{equation*}
\notag
$$
In this section $\Omega = \mathbb{T}^d$ and $\mu$ is the normalized Lebesgue measure on $\mathbb{T}^d$. Lemma 4.1. Let $1\leqslant q\leqslant p\leqslant \infty$, and let $\mathcal{T}(\mathbf{N},d)_q$ denote the unit $L_q$-ball of the subspace $\mathcal{T}(\mathbf{N},d)$. Then for $m\leqslant \vartheta(\mathbf{N})/2$ we have Proof. Fix a set $\xi\subset \mathbb{T}^d := [0,2\pi)^d$ of points $\xi^1,\dots,\xi^m$. Consider the subspace
$$
\begin{equation*}
T(\xi):=\{f\in \mathcal T({\mathbf N},d)\colon f(\xi^\nu)=0,\ \nu=1,\dots,m\}.
\end{equation*}
\notag
$$
Let $g_\xi\in T(\xi)$ and a point $\mathbf{x}^*$ be such that $|g_\xi(\mathbf{x}^*)|=\|g_\xi\|_\infty=1$. For the further argument we need some classical trigonometric polynomials. The univariate Fejér kernel of order $j - 1$ is
$$
\begin{equation*}
\mathcal K_{j} (x):=\sum_{|k|\leqslant j} \biggl(1-\frac{|k|}j\biggr) e^{ikx} =\frac{(\sin (jx/2))^2}{j (\sin (x/2))^2}.
\end{equation*}
\notag
$$
The Fejér kernel is an even nonnegative trigonometric polynomial of order ${j-1}$. It satisfies the obvious relations
$$
\begin{equation}
\| \mathcal K_{j} \|_1=1 \quad\text{and}\quad \| \mathcal K_{j} \|_{\infty}=j.
\end{equation}
\tag{4.1}
$$
Let $\mathcal{K}_\mathbf{j}(\mathbf{x}):= \prod_{i=1}^d \mathcal{K}_{j_i}(x_i)$ be the $d$-variate Fejér kernels for $\mathbf{j} = (j_1,\dots,j_d)$ and $\mathbf{x}=(x_1,\dots,x_d)$. We set
$$
\begin{equation}
f({\mathbf x}):=g_\xi({\mathbf x})\mathcal K_{\mathbf N}({\mathbf x}-{\mathbf x}^*).
\end{equation}
\tag{4.2}
$$
Then $f\in \mathcal{T}(2\mathbf{N},d)$, $f(\xi^\nu)=0$, $\nu=1,\dots,m$, and
$$
\begin{equation}
\|f\|_q \leqslant \|g_\xi\|_\infty \|\mathcal K_{\mathbf N}\|_q \leqslant C_1(d)\vartheta({\mathbf N})^{1-1/q}.
\end{equation}
\tag{4.3}
$$
At the last step we used the known bound for the $L_q$-norm of the Fejér kernel (see [17], p. 83, (3.2.7)). By (4.1) we have
$$
\begin{equation}
|f({\mathbf x}^*)| \geqslant C_2(d) \vartheta({\mathbf N}).
\end{equation}
\tag{4.4}
$$
By the Nikol’skii inequality for $\mathcal{T}(2\mathbf{N},d)$ (see [17], p. 90, Theorem 3.3.2), from (4.4) we obtain
Let $\mathcal{M}$ be a mapping from $\mathbb{C}^m$ to $L_p$. Set $g_0:=\mathcal{M}(\mathbf 0)$. Then
$$
\begin{equation*}
\biggl\|\frac{f}{\|f\|_q} -g_0\biggr\|_p+\biggl\|-\frac{f}{\|f\|_q}-g_0\biggr\|_p \geqslant 2\biggl\|\frac{f}{\|f\|_q}\biggr\|_p.
\end{equation*}
\notag
$$
This, relations (4.3), (4.5) and the fact that both $f/\|f\|_q$ and $-f/\|f\|_q$ belong to $\mathcal{T}(2\mathbf{N},d)_q$ complete the proof of Lemma 4.1. We now show how Theorem 3.2 can be used to show that Theorem 1.2 cannot be improved substantially in the sense of relation between $m$ and $u$. Proposition 4.1. Let $d\in \mathbb{N}$ and $p\in (2,\infty)$. Then there exists a positive constant $C(d,p)$ with the following property. For any Proof. The proof goes by contradiction. Assume that there exists a set $\xi:= \{\xi^j\}_{j=1}^m \subset \mathbb{T}^d$ that provides the one-sided $L_p$-universal discretization (3.7) for $\mathcal{X}_{2v}(\mathcal{D}_N)$. Then by Theorem 3.2 inequality (3.8) holds for any $f\in\mathcal{C}(\mathbb{T}^d)$. We take the function $f$ from the proof of Lemma 4.1, as defined in (4.2). By the definition of $f$ we obtain $f(\xi^j)=0$ for all $j=1,\dots,m$. Therefore, $B_v(f,\mathcal{D}_N,L_p(\xi))=0$, and from (4.5) we obtain
$$
\begin{equation}
\|f-B_v(f,\mathcal D_N,L_p(\xi))\|_p \geqslant C_3(d)\vartheta({\mathbf N})^{1-1/p}.
\end{equation}
\tag{4.6}
$$
On the other hand, by (4.3), for $q=2$ we have
$$
\begin{equation}
\sum_{{\mathbf k}\in \mathbb Z^d} |\widehat f({\mathbf k})| \leqslant \vartheta(2{\mathbf N})^{1/2} \|f\|_2^{1/2} \leqslant C_1(d) \vartheta(2{\mathbf N})^{1/2}\vartheta({\mathbf N})^{1/2} \leqslant C_1'(d)\vartheta({\mathbf N}).
\end{equation}
\tag{4.7}
$$
From (2.5) we obtain that $\eta(L_p(\mathbb{T}^d,\mu_\xi),w) \leqslant (p-1)w^2/2$. It is known (see, for instance, [15], p. 342) that for any dictionary $\mathcal{D} = \{g\}$, $\|g\|_X \leqslant 1$, in a Banach space $X$ with $\eta(X,w) \leqslant \gamma w^q$, $1<q\leqslant 2$, we have Here
Note that (4.8) was proved in [15] in the case of real Banach spaces. It is clear that we can obtain (4.8) for complex systems $\mathcal{D}_N$ from the corresponding results for real trigonometric polynomials in $\mathcal{T}(2\mathbf{N},d)$. We now apply inequality (4.8) and find from (4.7) that
$$
\begin{equation}
\sigma_v(f,\mathcal D_N)_{L_p(\mathbb T^d, \mu_\xi)} \leqslant C_1(d,p)\vartheta({\mathbf N}) (v+1)^{-1/2}.
\end{equation}
\tag{4.9}
$$
Substituting (4.6) and (4.9) into (3.8) we obtain
$$
\begin{equation*}
v+1 \leqslant C(d,p)(2D+1)^2 \vartheta({\mathbf N})^{2/p}
\end{equation*}
\notag
$$
for some positive constant $C(d,p)$. We fix this constant $C(d,p)$ and complete the proof of Proposition 4.1. § 5. Optimal recovery on function classesThe following theorem was proved in [18]. Theorem 5.1 ([18]). Let $1<p<\infty$, $r>0$ and $\beta\in (0,1]$. Assume that $\|\psi_\mathbf{k}\|_{L_p(\Omega,\mu)} \leqslant B$, $\mathbf{k}\in\mathbb{Z}^d$, for some probability measure $\mu$ on $\Omega$. Then there exist two constants $c^*=c(r,\beta,p,d)$ and $C=C(r,\beta,p,d)$ such that for any $v\in \mathbb{N}$ there is $J\in\mathbb{N}$ independent of the measure $\mu$ such that $2^J \leqslant v^{c^*}$ and ( $p^*:= \min\{p,2\}$). Moreover, this bound is provided by a simple greedy algorithm. We proceed to a new result on sampling recovery. In the proof of Theorem 5.3 below we need the following known result on universal discretization. Theorem 5.2 ([4]). Let $1\leqslant p\leqslant 2$. Assume that $ \mathcal{D}_N=\{\varphi_j\}_{j=1}^N\subset \mathcal{C}(\Omega)$ is a system satisfying conditions (1.7) and (1.9) for some constant $K\geqslant 1$. Let $\xi^1,\dots, \xi^m$ be independent random points on $\Omega$ that are identically distributed with respect to $\mu$. Then there exist constants $C=C(p)>1$ and $c=c(p)>0$ such that, given any integers $1\leqslant u\leqslant N$ and the inequalities hold with probability $\geqslant 1-2 \exp( -cm/(Ku\log^2 (2Ku)))$. Theorem 5.3. Assume that $\Psi$ is a uniformly bounded Riesz system (in the space $L_2(\Omega,\mu)$) satisfying (1.7) and (1.8) for some constants $0<R_1\leqslant R_2<\infty$. Let $2\leqslant p<\infty$ and $r>0$. For any $v\in\mathbb{N}$ let $u := \lceil (1+c)v\rceil$, where $c$ is from Theorem 3.1. Assume, in addition, that $\Psi \in \mathrm{NI}(2,p,H,u)$ for $p\in [2,\infty)$. Then there exist constants $c'=c'(r,\beta,p,R_1,R_2,d)$ and $C'=C'(r,\beta,p,d)$ such that the bound holds for any $m$ satisfying Moreover, this bound is provided by the WOMP. Proof. First we use Theorem 5.1 in the space $L_p(\Omega,\mu)$. In our case $B=1$ and $2<p<\infty$, which implies that $p^*=2$. Consider the system $\Psi_J := \{\psi_\mathbf{k}\}_{\|\mathbf{k}\|_\infty <2^J}$, $2^J \leqslant v^{c^*}$, from Theorem 5.1. Note, that $J$ does not depend on $\mu$. By Theorem 3.1 for $\mathcal{D}_N = \Psi_J$ and Theorem 5.2 with $p=2$ and $K=R_1^{-2}$ there exist $m$ points $\xi^1,\dots,\xi^m\in \Omega$, where such that, given $f_0\in \mathcal{C}(\Omega)$, the WOMP with weakness parameter $t$, as applied to $f_0$, with respect to the system $\mathcal{D}_N(\Omega_m)$ in the space $L_2(\Omega_m,\mu_m)$, provides for any integer $1\leqslant v \leqslant u/(1+c)$ the inequality
$$
\begin{equation}
\|f_{cv} \|_{L_p(\Omega,\mu)} \leqslant C'H \sigma_v(f_0,\mathcal D_N)_{L_p(\Omega, \mu_\xi)}.
\end{equation}
\tag{5.4}
$$
In order to bound the right-hand side of (5.4) we use Theorem 5.1 in the space $L_p(\Omega, \mu_\xi)$. To do this it is sufficient to check that $\|\psi_\mathbf{k}\|_{L_p(\Omega, \mu_\xi)} \leqslant 1$, $\mathbf{k}\in\mathbb{Z}^d$. This follows from the assumption that $\Psi$ satisfies (1.7). Thus, by Theorem 5.1, for $f_0 \in \mathbf{A}^r_\beta(\Psi)$ we obtain
$$
\begin{equation}
\sigma_v(f_0,\Psi_J)_{L_p(\Omega, \mu_\xi)} \leqslant Cv^{1/2 -1/\beta-r/d}.
\end{equation}
\tag{5.5}
$$
Combining (5.5) and (5.4), and taking (5.3) and the bound into account we complete the proof. Corollary 5.1. Assume that $\Psi$ is a uniformly bounded Riesz system (in the space $L_2(\Omega,\mu)$) satisfying (1.7) and (1.8) for some constants $0<R_1\leqslant R_2<\infty$. Let ${2\leqslant p<\infty}$ and $r>0$. Then there exist constants $c=c(r,\beta,p,R_1,R_2,d)$ and $C=C(r,\beta,p,d)$ such that the bound holds for any $m$ satisfying Moreover, this bound is provided by the WOMP. Proof. We prove that a system $\Psi$ satisfying the assumptions of Corollary 5.1 also satisfies the condition $\Psi \in \mathrm{NI}(2,p,H,u)$ for $H= C(R_2) u^{1/2-1/p}$, as required in Theorem 5.3. Then Corollary 5.1 follows from Theorem 5.3. Indeed, let
$$
\begin{equation*}
f:=\sum_{{\mathbf k} \in Q} c_{\mathbf k} \psi_{\mathbf k}, \qquad |Q| \leqslant u.
\end{equation*}
\notag
$$
Then Using the following well-known simple inequality $\|f\|_p \leqslant \|f\|_2^{2/p}\|f\|_\infty^{1-2/p}$, ${2\!\leqslant\! p\!\leqslant\! \infty}$, we obtain
The corollary is proved. We have derived Theorem 5.3 from Theorem 3.1. Now we formulate an analogue of Theorem 5.3, which can be derived from Theorem 3.3 in the same way as Theorem 5.3 is derived from Theorem 3.1. Theorem 5.4. Let $2\leqslant p<\infty$, and let $m$ and $v$ be given natural numbers. Let $\Psi$ be a uniformly bounded Bessel system satisfying (1.7) and (1.9) such that $\Psi \in \mathrm{NI}(2,p,H,2v)$. Then there exist constants $c=c(r,\beta,p,K,d)$ and $C=C(r,\beta,p,d)$ such that the bound holds for any $m$ satisfying In the special case when $\Psi = \mathcal{T}^d$ is the trigonometric system Corollary 5.1 gives
$$
\begin{equation}
\varrho_{m}^{\rm o}({\mathbf A}^r_\beta(\mathcal T),L_p(\Omega,\mu)) \ll v^{1-1/p -1/\beta -r/d} \quad\text{for } m\gg v (\log(2v ))^4.
\end{equation}
\tag{5.8}
$$
It was pointed out in [4] that known results on the restricted isometry property for the trigonometric system can be used to improve results on universal discretization in the $L_2$-norm in the case of the trigonometric system. We explain this in more detail. 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}^d(M) := \mathcal{T}^d(\Pi(M))$ of functions $e^{i(\mathbf{k},\mathbf{x})}$, $\mathbf{k} \in \Pi(M)$, defined on $\mathbb{T}^d =[0,2\pi)^d$. Then $\mathcal{T}^d(M)$ is an orthonormal system in $L_2(\mathbb{T}^d,\mu)$, where $\mu$ is the normalized Lebesgue measure on $\mathbb{T}^d$. The cardinality of this system is $N(M):= |\mathcal{T}^d(M)| = (2M+1)^d$. We are interested in bounds on $m(\mathcal{X}_v(\mathcal{T}^d(M)),2)$ in the special case when $M\leqslant v^c$ for some constant $c$, which can depend on $d$. Then Theorem 5.2 for $p=2$ gives
$$
\begin{equation}
m(\mathcal X_v(\mathcal T^d(v^c)),2) \leqslant C(c,d) v (\log (2v))^4.
\end{equation}
\tag{5.9}
$$
It was stated in [4] that the known results of [8] and [1] allow us to improve (5.9):
$$
\begin{equation}
m(\mathcal X_v(\mathcal T^d(v^c)),2) \leqslant C(c,d) v (\log (2v))^3.
\end{equation}
\tag{5.10}
$$
This, in turn, implies the following estimate:
$$
\begin{equation}
\varrho_{m}^{\rm o}({\mathbf A}^r_\beta(\mathcal T^d),L_p) \ll v^{1-1/p -1/\beta -r/d} \quad\text{for } m\gg v (\log(2v ))^3.
\end{equation}
\tag{5.11}
$$
Now we prove that (5.11) cannot be substantially improved. We use Lemma 4.1. Take $n\in\mathbb{N}$ and set $N:=2^n-1$, $\mathbf{N} := (N,\dots,N)$. Then for $f\in \mathcal{T}(\mathbf{N},d)_2$, by Hölder’s inequality with parameter $2/\beta$ we have
$$
\begin{equation*}
\begin{aligned} \, \biggl(\sum_{{\mathbf k}\colon \|{\mathbf k}\|_\infty\leqslant N} |\widehat f({\mathbf k})|^\beta\biggr)^{1/\beta} &\leqslant (2N+1)^{d(1/\beta-1/2)} \biggl(\sum_{{\mathbf k}\colon \|{\mathbf k}\|_\infty\leqslant N} |\widehat f({\mathbf k})|^2\biggr)^{1/2} \\ &=(2N+1)^{d(1/\beta-1/2)}\|f\|_2 . \end{aligned}
\end{equation*}
\notag
$$
This bound and Lemma 4.1 for $q=2$ imply the following lower bound.
§ 6. DiscussionIn this paper we emphasize the importance of the classes $\mathbf{A}^r_\beta(\Psi)$, which are defined by structural conditions, rather than smoothness conditions. We give a brief history of the development of this idea. The first result connecting the best approximations $\sigma_v(f,\Psi)_2$ with the convergence of the series $\sum_{k}|\langle f,\psi_k\rangle|$ was obtained by Stechkin [13] in 1955, in the case of an orthonormal system $\Psi$. We formulate his result and a more general result below. The following classes were introduced in [6], in the study of sparse approximation with respect to arbitrary systems ( dictionaries) $\mathcal{D}$ in a Hilbert space $H$. Given a general dictionary $\mathcal{D}$ and $\beta>0$, we define the class of functions (elements)
$$
\begin{equation*}
\mathcal A^{\rm o}_\beta(\mathcal D,M):=\biggl\{f\in H\colon f=\sum_{k\in \Lambda} c_kg_k,\, g_k\in \mathcal D,\, |\Lambda| <\infty,\, \sum_{k\in \Lambda} |c_k|^\beta \leqslant M^\beta\biggr\},
\end{equation*}
\notag
$$
and we define $\mathcal{A}_\beta(\mathcal{D},M)$ as the closure of $\mathcal{A}^{\rm o}_\beta(\mathcal{D},M)$ (in $H$). Furthermore, we define $\mathcal{A}_\beta(\mathcal{D})$ as the union of the classes $\mathcal{A}_\beta(\mathcal{D},M)$ over all $M>0$. In the case when $\mathcal{D}$ is an orthonormal system Stechkin [13] proved (see a discussion of this result in [7], § 7.4) that
$$
\begin{equation}
f\in \mathcal A_1(\mathcal D) \quad \text{if and only if}\quad \sum_{v=1}^\infty (v^{1/2}\sigma_v(f,\mathcal D)_2)\frac{1}{v} <\infty.
\end{equation}
\tag{6.1}
$$
A version of (6.1) for the classes $\mathcal{A}_\beta(\mathcal{D})$, $\beta\in (0,2)$, was obtained in [6]:
$$
\begin{equation}
f\in \mathcal A_\beta(\mathcal D) \quad \text{if and only if}\quad \sum_{v=1}^\infty (v^{\alpha}\sigma_v(f,\mathcal D)_H)^\beta\frac{1}{v} <\infty,
\end{equation}
\tag{6.2}
$$
where $\alpha := 1/\beta-1/2$. In particular, (6.2) implies that for $f\in \mathcal{A}_\beta(\mathcal{D})$ and $\beta\in (0,2)$, we have We recall that relations (6.1)–(6.3) were proved for an orthonormal system $\mathcal{D}$. It is very interesting to note that (6.3) actually holds for a general normalized system $\mathcal{D}$, provided that $\beta \in (0,1]$. In the case $\beta =1$ it was proved by Maurey (see [12]). For $\beta \in (0,1]$ it was proved in [6]. We note that the classes $\mathcal{A}_1(\mathcal{D})$ and their generalizations to the case of Banach spaces play a fundamental role in the study of best $v$-term approximation and the convergence properties of greedy algorithms with respect to general dictionaries $\mathcal{D}$ (see [15]). This fact has encouraged experts to introduce and study function classes defined in terms of some restrictions on the coefficients of the functions’ expansions. We explain this approach in detail. As above, let the system $\Psi:=\{\psi_\mathbf{k}\}_{\mathbf{k}\in \mathbb{Z}^d}$ be indexed by $\mathbf{k}\in\mathbb{Z}^d$. Consider a sequence of subsets $\mathcal{G}:=\{G_j\}_{j=1}^\infty$, $G_j \subset \mathbb{Z}^d$, $j=1,2,\dots$, such that
$$
\begin{equation}
G_1\subset G_2\subset \dots \subset G_j\subset G_{j+1} \subset \dotsb\quad\text{and} \quad \bigcup_{j=1}^\infty G_j=\mathbb Z^d.
\end{equation}
\tag{6.4}
$$
Consider functions representable in the form of absolutely convergent series:
$$
\begin{equation}
f=\sum_{{\mathbf k}\in\mathbb Z^d} a_{\mathbf k}(f)\psi_{\mathbf k}, \qquad \sum_{{\mathbf k}\in\mathbb Z^d} |a_{\mathbf k}(f)|<\infty.
\end{equation}
\tag{6.5}
$$
For $\beta \in (0,1]$ and $r>0$ consider the following class $\mathbf{A}^r_\beta(\Psi,\mathcal{G})$ of functions $f$ that have representations (6.5) satisfying the conditions
$$
\begin{equation}
\biggl(\sum_{ {\mathbf k}\in G_j\setminus G_{j-1}} |a_{\mathbf k}(f)|^\beta\biggr)^{1/\beta} \leqslant 2^{-rj}, \qquad j=1,2,\dots, \qquad G_0:=\varnothing .
\end{equation}
\tag{6.6}
$$
One can also consider the following narrower version $\mathbf{A}^r_\beta(\Psi,\mathcal{G},\infty)$, the class of functions $f$ with representations (6.5) satisfying the condition
$$
\begin{equation}
\sum_{j=1}^\infty 2^{r\beta j} \sum_{ {\mathbf k}\in G_j\setminus G_{j-1}} |a_{\mathbf k}(f)|^\beta \leqslant 1, \qquad G_0:=\varnothing .
\end{equation}
\tag{6.7}
$$
The first realization of the idea of the classes $\mathbf{A}^r_\beta(\Psi,\mathcal{G})$ was probably carried out in [16] in the special case when $\Psi$ is the trigonometric system $\mathcal{T}^d := \{e^{i(\mathbf{k},\mathbf{x})}\}_{\mathbf{k}\in\mathbb{Z}^d}$. We now proceed to the definition of the classes $\mathbf{W}^{a,b}_A(\mathcal{T}^d)$ from [16], which correspond to the case $\beta=1$. We introduce the necessary notation. Let $\mathbf s=(s_1,\dots,s_d )$ be a vector whose coordinates are nonnegative integers, and set
$$
\begin{equation*}
\rho(\mathbf s):=\bigl\{ \mathbf k\in\mathbb Z^d\colon [2^{s_j-1}] \leqslant |k_j| < 2^{s_j},\, j=1,\dots,d \bigr\},
\end{equation*}
\notag
$$
where $[a]$ means the integer part of a real number $a$. For $f\in L_1(\mathbb{T}^d)$ let
$$
\begin{equation*}
\delta_{\mathbf s} (f,\mathbf x):=\sum_{\mathbf k\in\rho(\mathbf s)} \widehat f(\mathbf k)e^{i(\mathbf k,\mathbf x)}\quad\text{and}\quad \widehat f(\mathbf k):=(2\pi)^{-d}\int_{\mathbb T^d} f({\mathbf x})e^{-i(\mathbf k,\mathbf x)}\,d{\mathbf x}.
\end{equation*}
\notag
$$
Consider functions with absolutely convergent Fourier series. For such functions we define their Wiener norm ($A$- or $\ell_1$-norm) by The following classes, which are convenient in the studies of sparse approximation with respect to the trigonometric system, were introduced and considered in [16]. For $f\in L_1(\mathbb{T}^d)$ we set
$$
\begin{equation*}
f_j:=\sum_{\|{\mathbf s}\|_1=j}\delta_{\mathbf s}(f), \qquad j\in \mathbb{N}_0, \quad \mathbb{N}_0:=\mathbb{N}\cup \{0\}.
\end{equation*}
\notag
$$
For parameters $a\in \mathbb{R}_+$ and $b\in \mathbb{R}$ we define the class
$$
\begin{equation*}
{\mathbf W}^{a,b}_A:=\{f\colon \|f_j\|_A \leqslant 2^{-aj}(\overline j)^{(d-1)b},\, \overline j:=\max(j,1), \, j\in \mathbb{N}\}.
\end{equation*}
\notag
$$
In this case
$$
\begin{equation*}
G_j:=\bigcup_{{\mathbf s}\colon \|{\mathbf s}\|_1 \leqslant j} \rho({\mathbf s}), \qquad j=1,2,\dots,
\end{equation*}
\notag
$$
and the classes $\mathbf{W}^{a,b}_A$ with $b=0$ are similar to the classes $\mathbf{A}^a_1(\mathcal{T}^d,\mathcal{G})$ defined above. A more narrow version $\mathbf{A}^a_1(\mathcal{T}^d,\mathcal{G},\infty)$ of these classes was studied recently in [9]. The classes $\mathbf{A}^r_\beta(\Psi)$ considered in this paper correspond to the case of $\mathbf{A}^r_\beta(\Psi,\mathcal{G})$ where
$$
\begin{equation}
G_j:=\{{\mathbf k}\in \mathbb Z^d\colon \|{\mathbf k}\|_\infty <2^j\}, \qquad j=1,2,\dots\,.
\end{equation}
\tag{6.8}
$$
Note that the classes $\mathbf{A}^r_\beta(\mathcal{T}^d)$ are related to the periodic isotropic Nikol’skii classes $H^r_q$. There are several equivalent definitions of the classes $H^r_q$. We give a definition convenient for us. Let $r>0$ and $1\leqslant q\leqslant \infty$. The class $H^r_q$ consists of the periodic functions $f$ of $d$ variables satisfying the conditions
$$
\begin{equation*}
\biggl\|\sum_{[2^{j-1}] \leqslant \|{\mathbf k}\|_\infty< 2^j} \widehat f({\mathbf k}) e^{i({\mathbf k},{\mathbf x})}\biggr\|_q \leqslant 2^{-rj}, \qquad j=0,1,\dots\,.
\end{equation*}
\notag
$$
For instance, it is easy to see that in the case when $q=2$ and $r/d >1/2$ the class $H^r_q$ is embedded in $\mathbf{A}^{r-d/2}_1(\mathcal{T}^d)$. However, the class $\mathbf{A}^{r-d/2}_1(\mathcal{T}^d)$ is substantially larger than $H^r_2$. For instance, take $\mathbf{k} \in G_j\setminus G_{j-1}$, where $G_j$ is defined in (6.8). Then the function $g_\mathbf{k} := 2^{-(r-d/2)j}e^{i(\mathbf{k},\mathbf{x})}$ belongs to $\mathbf{A}^{r-d/2}_1(\mathcal{T}^d)$ but does not belong to any $H^{r'}_2$ for $r'> r-d/2$. Now we give a brief comparison of sampling recovery results for the classes $H^r_q$ and $\mathbf{A}^r_\beta(\mathcal{T}^d)$. Recall the setting of optimal linear recovery. For fixed $m$ and a set of points $\xi:=\{\xi^j\}_{j=1}^m\subset \Omega$, let $\Phi$ be a linear operator from $\mathbb{C}^m$ into $L_p(\Omega,\mu)$. For a class $\mathbf{F}$ (usually, a centrally symmetric and compact subset of $L_p(\Omega,\mu)$; see [14]) set
$$
\begin{equation*}
\varrho_m({\mathbf F},L_p):=\inf_{\text{linear}\, \Phi;\,\xi} \, \sup_{f\in {\mathbf F}} \|f-\Phi(f(\xi^1),\dots,f(\xi^m))\|_p.
\end{equation*}
\notag
$$
It is known (see [17], p. 125, Theorem 3.6.4) that for all $1\leqslant p,q\leqslant \infty$ and $r >d/q$ we have
$$
\begin{equation}
\varrho_m(H^r_q,L_p) \asymp m^{-r/d+(1/q-1/p)_+}, \qquad (a)_+:=\max(a,0).
\end{equation}
\tag{6.9}
$$
Clearly, (6.9) implies the same upper bound for $\varrho^{\rm o}_m(H^r_q,L_p)$. The results on lower bounds for $\varrho^{\rm o}_m(\mathcal{T}(\mathbf{N},d)_q,L_p)$ from Lemma 4.3 in [18] and Lemma 4.1 in this paper show that
$$
\begin{equation}
\varrho^{\rm o}_m(H^r_q,L_p) \asymp m^{-r/d+(1/q-1/p)_+}.
\end{equation}
\tag{6.10}
$$
In particular,
$$
\begin{equation}
\varrho^{\rm o}_m(H^r_2,L_p) \asymp m^{-r/d+(1/2-1/p)_+}.
\end{equation}
\tag{6.11}
$$
The lower bound (1.5) in [18] and the lower bound in (1.14) here give the following bound in the case $\beta=1$:
$$
\begin{equation}
\varrho^{\rm o}_m({\mathbf A}^r_1(\mathcal T^d,L_p)) \gg m^{-1/2+(1/2-1/p)_+-r/d}.
\end{equation}
\tag{6.12}
$$
The upper bound in (1.14) here gives the bound
$$
\begin{equation}
\varrho^{\rm o}_m({\mathbf A}^r_1(\mathcal T^d,L_p)) \ll \biggl(\frac{m}{(\log m)^3}\biggr)^{-1/2+(1/2-1/p)_+-r/d}.
\end{equation}
\tag{6.13}
$$
Relations (6.11)–(6.13) mean that we obtain close bounds for the class $H^r_2$ and the larger class $\mathbf{A}^{r-d/2}_1(\mathcal{T}^d)$, $r>d/2$. Note that for $H^r_2$ we obtain the same bounds for linear sampling recovery. It was proved in [18] that for linear sampling recovery in $\mathbf{A}^r_\beta(\mathcal{T}^d)$ we have
$$
\begin{equation}
\varrho_m({\mathbf A}^r_\beta(\mathcal T^d,L_2)) \gg m^{-r/d}.
\end{equation}
\tag{6.14}
$$
Inequalities (6.14) for $\beta=1$ and (6.13) for $p=2$ demonstrate that nonlinear sampling recovery provides better error guarantees than linear sampling recovery.
Citation in format AMSBIB
\Bibitem{Tem24} |
|
|||||||||||||||||||||||||||||||||||||||||||||||||||||||
|
Contact us: |
Terms of Use
|
Registration to the website |
Logotypes |
|