| Sbornik: Mathematics |
|
|
|
|
|
A remark on constructive covering of a ball of finite-dimensional Banach space 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 short note is a follow-up of the author’s paper [5]. The purpose of this note is threefold. First of all, we discuss Theorem 5.2 from [5]. That theorem is formulated in [5] under one assumption on the system but it is proved under a different assumption. We discuss this issue in § 2. The reader can view this paper as a replacement of Theorem 5.2 and § 6 of [5]. We do not know if Theorem 5.2 from [5] is correct. This means that the reader can view some results in § 6 of [5] (namely, Examples 1–3) as conditional results obtained under the assumption that Theorem 5.2 is correct. Second, we discuss some new incoherence type characteristics of a finite system of elements in a Banach space. We present this discussion in § 3. Third, in § 4 we present constructive ways (algorithms) of building reasonably good coverings of the unit balls of Banach spaces. We use the notations from [5] but for the reader’s convenience we recall some of them here. Let $X$ be a Banach space $\mathbb{R}^d$ with norm $\|\cdot\|$, and let $B:=B_X$ denote the corresponding closed unit ball:
$$
\begin{equation}
B:=B_X:=\{x\in \mathbb R^d\colon \|x\|\leqslant 1\}.
\end{equation}
\tag{1.1}
$$
Notation $B(x,r):=B_X(x,r)$ will be used for the closed ball with centre $x$ and radius $r$. In case $r=1$ we drop $r$ from the notation: $B(x):=B(x,1)$. For a compact set $A$ and a positive number $\varepsilon$ we define the covering number $N_\varepsilon(A)$ by
$$
\begin{equation*}
N_\varepsilon(A) := N_\varepsilon(A,X) :=\min \biggl\{n \biggm| \exists\, x^1,\dots,x^n\colon A\subseteq \bigcup_{j=1}^n B_X(x^j,\varepsilon)\biggr\}.
\end{equation*}
\notag
$$
For $x\neq 0$ let $F_x$ be a norming functional for $x$: $\|F_x\|_{X^*}=1$ and $F_x(x)=\|x\|$. The existence of such a functional follows from the Hahn–Banach theorem. Let $\mathcal{D}$ be a normalized system of vectors in a Banach space $X$. We define the coherence parameter of $\mathcal{D}$ in the following way (see [3]):
$$
\begin{equation*}
M(\mathcal D):=M(\mathcal D,X):= \sup_{\substack{g\neq h \\ g,h\in\mathcal D}}\sup_{F_g}|F_g(h)|,
\end{equation*}
\notag
$$
where $F_g$ is a norming functional for $g$. We note that, in general, a norming functional $F_g$ is not unique. This is why we take $\sup_{F_g}$ over all the norming functionals of $g$ in the definition of $M(\mathcal{D})$. We do not need $\sup_{F_g}$ in the definition of $M(\mathcal{D})$ if for each $g\in\mathcal{D}$ there is a unique norming functional $F_g\in X^*$. For instance, this is the case when the Banach space is uniformly smooth. In this paper we only study the uniformly smooth Banach spaces, and for this reason we do not take the supremum over the norming functionals. Clearly, $M(\mathcal{D})\leqslant 1$. In [5] we discussed the following characteristics for $\mu\leqslant 1$ (we recall that $X$ is a Banach space $\mathbb{R}^d$ with some norm)
$$
\begin{equation*}
N(X,d,\mu) := \sup\{N\mid \exists\, \mathcal D\colon \# \mathcal D \geqslant N,\, M(\mathcal D,X)\leqslant\mu\}.
\end{equation*}
\notag
$$
We proved in § 5 of [5] the following upper bound for $N(X,d,\mu)$. In the case of Euclidean space this bound was known before (see [4], § 5.7). Theorem 1.1. There is a positive absolute constant $C_1$ such that for a Banach space $X$ that is $\mathbb{R}^d$ equipped with a norm $\|\cdot\|$, $\mu \in (0,1/2]$ we have In this paper, for a finite normalized system $\mathcal{D}_N:=\{g^j\}_{j=1}^N$ we introduce two concepts of semi-incoherence parameter. We formulate these definitions in the case of uniformly smooth Banach spaces (see a comment above). We define the upper semi-incoherence parameter by
$$
\begin{equation*}
M^u(\mathcal D_N) := M^u(\mathcal D_N,X) := \sup_{1\leqslant i<j\leqslant N} |F_{g^j}(g^i)|
\end{equation*}
\notag
$$
and the lower semi-incoherence parameter by
$$
\begin{equation*}
M^\ell(\mathcal D_N) := M^\ell(\mathcal D_N,X) := \sup_{1\leqslant i<j\leqslant N} |F_{g^i}(g^j)|.
\end{equation*}
\notag
$$
We discuss here the following characteristic:
$$
\begin{equation*}
N^u(X,d,\mu) := \sup\{N\mid \exists\, \mathcal D\colon|\mathcal D|\geqslant N,\, M^u(\mathcal D,X) \leqslant \mu\},
\end{equation*}
\notag
$$
and its sibling $N^\ell(X,d,\mu)$ defined in the same way. Clearly,
$$
\begin{equation*}
M^u(\mathcal D_N,X) \leqslant M(\mathcal D_N,X) \quad\text{and}\quad M^\ell(\mathcal D_N,X) \leqslant M(\mathcal D_N,X).
\end{equation*}
\notag
$$
Therefore,
$$
\begin{equation}
N(X,d,\mu) \leqslant \min(N^u(X,d,\mu),N^\ell(X,d,\mu)).
\end{equation}
\tag{1.3}
$$
The following observation was made by the referee. Consider, along with ${\mathcal{D}_N:=\{g^j\}_{j=1}^N}$, the system $\mathcal{D}_N':=\{y^j\}_{j=1}^N$, $y^j := g^{N-j+1}$. Then we have $M^u(\mathcal{D}_N)=M^\ell(\mathcal{D}_N')$, and therefore $N^u(X,d,\mu)=N^\ell(X,d,\mu)$. We prove in § 3 the following version of Theorem 1.1 from [5] (see Theorem 1.1 above). Theorem 1.2. There exists a positive absolute constant $C_2$ with the following property: if the Banach space $X$ is $\mathbb{R}^d$ equipped with a norm $\|\cdot\|$, then for $\mu \in (0,1/2]$ and the same bound holds for $N^\ell(X,d,\mu)$ as well. Theorem 1.2 is much weaker than Theorem 1.1. However, we do not know if it can be improved. Note that Milo informed the author that he independently obtained results similar to Theorem 1.2. Here we introduce and study the following two incoherence-type properties. Definition 1.1. We say that a system $\mathcal{D}_N:=\{g^j\}_{j=1}^N$, $\|g^j\|=1$, $j=1,\dots,N$, has the Incoherence property $\operatorname{Inc}(\mu):=\operatorname{Inc}(\mu,X)$ and write $\mathcal{D}_N \in \operatorname{Inc}(\mu) $ if for each $x\in X$, $x\neq 0$, there is $g^k\in \mathcal{D}_N$ such that $|F_x(g^k)| \geqslant\mu$. Set Clearly, $ N_\mu \leqslant N_\nu$ if $\mu < \nu$. Definition 1.2. We say that a system $\mathcal{D}_N:=\{g^j\}_{j=1}^N$, $\|g^j\|=1$, $j=1,\dots,N$, has the Dual Incoherence property $\operatorname{DInc}(\mu):=\operatorname{DInc}(\mu,X)$ and write $\mathcal{D}_N \in \operatorname{DInc}(\mu)$ if for each $x\in X$, $\|x\|=1$, there is $g^k\in \mathcal{D}_N$ such that $|F_{g^k}(x)| \geqslant\mu$. Set For further discussion we need some concepts from the theory of Banach spaces. A Banach space $X$ is called smooth if each $g\in X$, $g\neq0$, is a point of Gâteaux smoothness: for any $y\in X$. For a Banach space $X$ we define the modulus of smoothness
$$
\begin{equation*}
\rho(u) := \sup_{\|x\|=\|y\|=1}\biggl(\frac{1}{2}(\|x+uy\|+\|x-uy\|)-1\biggr).
\end{equation*}
\notag
$$
It is easy to see that
$$
\begin{equation}
\max(0,u-1) \leqslant \rho(u) \leqslant u, \qquad u\geqslant 0.
\end{equation}
\tag{1.5}
$$
The uniformly smooth Banach space is the one with the property It is known (and easy to check) that a finite-dimensional smooth Banach space is uniformly smooth. Let $X$ be a smooth Banach space with modulus of smoothness $\rho(u)$. For $\mu \in (0,1]$ we denote by $a(\mu):=a(\rho,\mu)$ a solution (actually, it is a unique nonzero solution) to the equation It is easy to see that a solution exists, and by (1.5) we have $a(\mu)\leqslant 1$. Then $4\rho(2a(\mu))= a(\mu)\mu\leqslant 1$. In § 2 we prove the following result. Theorem 1.3. Assume that a finite system $\mathcal{D}_N:=\{g^j\}_{j=1}^N$, $\|g^j\|=1$, $j\!=\!1,\dots,N$, has the Incoherence property $\operatorname{Inc}(\mu)$. Then where $ r=1-\frac{1}{2}\mu a(\mu)$. Thus, In § 3 we prove Theorem 1.2 and obtain some inequalities between the characteristics introduced above. For instance (see Theorem 3.2 below), we prove that $N_\mu(d,X) \leqslant N^u(X,d,\mu)+1$. In § 4 we introduce and study a greedy-type algorithm which uses a system from $\operatorname{Inc}(\mu,X)$ to build a good covering of $B_X$. § 2. Proof of Theorem 1.3 and some examplesWe begin with the proof of Theorem 1.3 This proof is similar to the proof of Theorem 5.2 from [5] (see Remark 5.2 in [5]). It is a short proof, and for the reader’s convenience we present it here. Our assumption that $\mathcal{D}_N$ has the Incoherence property $\operatorname{Inc}(\mu)$ implies that for each $x\in B_X$ there is $g^k\in \mathcal{D}_N$ such that ${|F_x(g^k)| \geqslant \mu}$. Remark 2.1. We make a comment on a problem with the proof of Theorem 5.2 in [5]. We assumed there that $\mathcal{D}_N$ is an extreme system for $\mu$ in the space $X$. This implies that for each $x\in B_X$ either there is $g^k\in \mathcal{D}_N$ such that $|F_x(g^k)| \geqslant \mu$ or there is $g^l\in \mathcal{D}_N$ such that $|F_{g^l}(x)| \geqslant \mu$. In [5] we did not analyse the second option, when $|F_{g^l}(x)| \geqslant \mu$. Proof of Theorem 1.3. Suppose $F_x(g^k) \geqslant \mu$. The other case $F_x(-g^k) \geqslant \mu$ is treated in just the same way. In the case when $\|x\|\leqslant 1/2$, $x$ is covered by $B_X(0,1/2)$, so assume that $\|x\|\geqslant 1/2$. We need the following well-known lemma, which follows from the definition of the modulus of smoothness (see, for instance, [4], p. 336).
Lemma 2.1. Let $x\neq0$. Then for all $y\in X$ and $u\in \mathbb{R}$ where $F_x$ is a norming functional of $x$. By Lemma 2.1, for $u=-a(\mu)$ we obtain
$$
\begin{equation*}
\begin{aligned} \, \|x-a(\mu)g^k\| &\leqslant \|x\| -a(\mu) F_x(g^k)+2\|x\|\rho(2a(\mu)) \\ &\leqslant 1-\mu a(\mu) +2\rho(2a(\mu)) \leqslant 1- \frac{1}{2}\mu a(\mu). \end{aligned}
\end{equation*}
\notag
$$
Theorem 1.3 is proved. Often we do not know $\rho(u,X)$ but we know a majorant of it. For instance, the following bounds are known for the $L_p$-spaces, $1<p<\infty$:
$$
\begin{equation}
\rho(u,L_p) \leqslant\frac{u^p}p \quad \text{if } 1\leqslant p\leqslant 2
\end{equation}
\tag{2.1}
$$
and
$$
\begin{equation}
\rho(u,L_p) \leqslant \frac{p-1}{2}u^2 \quad \text{if } 2\leqslant p<\infty.
\end{equation}
\tag{2.2}
$$
Remark 2.2. Let $\omega(u)$ be a continuous majorant of $\rho(u)$, $u\in[0,\infty)$, such that $\omega(u)/u$ increases monotonically on $(0,\infty)$ and $\lim_{u\to0} \omega(u)/u =0$. Then Theorem 1.3 holds for $a(\mu)=a(\rho,\mu)$ replaced by $a(\omega,\mu)$. We complement Theorem 1.3 by the following statement. Proposition 2.1. Let $\mathcal{D}_N:=\{g^j\}_{j=1}^N$, $\|g^j\|=1$, $j=1,\dots,N$, be such that (1.7) is satisfied. Then $\mathcal{D}_N\in \operatorname{Inc}(\mu/2,X)$. Proof. Take any $x$ such that $\|x\|=1$. Then by (1.7) there exists $k\in \{1,\dots,N\}$ with, say, the property Then by the left-hand inequality of Lemma 2.1 for $y=g^k$ and $u=-a(\mu)$, we obtain Inequalities (2.3) and (2.4) imply that $F_x(g^k)\geqslant\mu/2$.
The proposition is proved. Iterating Theorem 1.3Typically, $\mu$ is a small number, while Theorem 1.3 is designed for covering $B_X$ by balls of radius close to $1$. It is an interesting and important problem by itself. The reader can find the corresponding discussion in [5]. We now discuss applications of Theorem 1.3 to coverings of $B_X$ by balls of small radius $\varepsilon$. The following proposition is well known (see, for instance, [4], p. 145). This proposition describes the behaviour of $N_\varepsilon(B_X,X)$ as $\varepsilon\to 0$. It gives the bounds
$$
\begin{equation}
d\ln\frac1\varepsilon \leqslant \ln(N_\varepsilon(B_X,X)) \leqslant d\ln\frac3\varepsilon, \qquad \varepsilon\in (0,1].
\end{equation}
\tag{2.5}
$$
However, the proof of these bounds is based on a volume argument and does not provide a construction of a good covering. We now explain how Theorem 1.3 can be used for such a construction. We begin with a general scheme and provide detailed constructions in the examples below. The main idea here is to iterate Theorem 1.3. This idea was formulated and used in [5]. Here is a direct corollary to Theorem 1.3. Corollary 2.1. For any system $\mathcal{D}_N \in \operatorname{Inc}(\mu,X)$ after $m$ iterations of the covering (1.7) we obtain a constructive covering (provided that $\mathcal{D}_N$ is given constructively) of $B_X$ by at most $(2N+1)^m$ balls of radius $\varepsilon_m := r^m = (1-\frac{1}{2}\mu a(\mu))^m$. Therefore, $N_{\varepsilon_m}(B_X) \leqslant (2N_\mu(d,X)+1)^m$ and We now discuss some upper bounds for $N_\mu(d,X)$. It will be convenient for us to use order inequalities: $a\ll b$ is $a\leqslant Cb$, $a\asymp b$ is $C_1b\leqslant a\leqslant C_2b$. The constants $C$, $C_1$ and $C_2$ below can depend on some characteristics of the space $X$, but do not depend on its dimension. In Examples 2.1–2.4 we consider the case when $X$ is a uniformly smooth Banach space $\mathbb{R}^d$ with a normalized basis $\Psi:=\{\psi^j\}_{j=1}^d$. It will be convenient for us to use the following notation: $\mu_d$ is a positive number such that for each $x\in X$ there exists
$$
\begin{equation}
k \in \{1,\dots,d\}\colon \quad|F_x(\psi^k)| \geqslant \mu_d.
\end{equation}
\tag{2.7}
$$
In Examples 2.1–2.4 we choose an appropriate $\mu_d$ by using different methods. Note that by the choice of $\mu_d$, which satisfies (2.7), we always have the inequality $N_{\mu_d} \leqslant d$. Example 2.1. Let $X$ be a uniformly smooth Banach space $\mathbb{R}^d$ with norm $\|\cdot\|$ and a normalized basis $\Psi:=\{\psi^j\}_{j=1}^d$. Then there is a positive constant $K$ such that each $x$ has a unique representation Set $a:=a_d:=a(\omega,\frac{1}{Kd})$ to be a solution to equation (1.6) for $\mu:=\mu_d:=\frac{1}{Kd}$, with a majorant $\omega$ from Remark 2.2. Inequality (2.8) shows that $\Psi \in \operatorname{Inc}(\mu_d)$. Therefore, by Theorem 1.3 the union
$$
\begin{equation*}
\biggl(\bigcup_{j=1}^d B_X(a\psi^j,r)\biggr)\cup\biggl(\bigcup_{j=1}^d B_X(-a\psi^j,r)\biggr)\cup B_X\biggl(0,\frac12\biggr),
\end{equation*}
\notag
$$
where $r\geqslant 1-\frac{1}{2} a\mu_d$, covers $B_X$. Inequality (2.7) implies that $N_{\mu_d} \leqslant d$. Then from Corollary 2.1 we obtain
$$
\begin{equation}
\ln (N_{\varepsilon_m}(B_X)) \leqslant \biggl(\ln \frac{1}{\varepsilon_m}\biggr)2 (\mu_d a(\mu_d))^{-1} \ln (2d+1).
\end{equation}
\tag{2.9}
$$
Comparing (2.9) with (2.5), we see that the extra factor $2(\mu_d a(\mu_d))^{-1} \ln (2d+1)$ must be greater than or equal to $d$. This extra factor is determined by the properties of the Banach space $X$. Under the extra assumption that $\rho(u,X) \leqslant \gamma u^q$, $1\!<\!q\!\leqslant\! 2$, choosing ${\omega_q(u) := \gamma u^q}$, from (1.6) we obtain This implies thatWe now demonstrate the behaviour of the extra factor $2 (\mu_d a(\mu_d))^{-1} \ln (2d+1)$ in some specific examples, where appropriate $\mu_d$ and $a(\mu_d)$ will be chosen. We consider some special examples of $X$. Example 2.2. Let $X$ be a Hilbert space. Take $\Psi$ to be an orthonormal basis. Then for $x$, $\|x\|=1$, we obtain Clearly, By (2.1) we can take $\omega(u):= u^2/2$ as a majorant for $\rho(u,X)$. Thus $\mu_d$ can be taken as $d^{-1/2}$ and $a_d:=a(\omega,\mu_d)$ is of the order of $d^{-1/2}$. In this case, by Corollary 2.1 (see also (2.9)), for $\mu_d a_d \asymp d^{-1}$ we obtain For $1<p<\infty$ we define $\ell_p^d$ as $\mathbb{R}^d$ equipped with the norm
$$
\begin{equation*}
\|x\|_p := \biggl(\sum_{j=1}^d |x_j|^p\biggr)^{1/p}, \qquad x=(x_1,\dots,x_d)\in \mathbb R^d.
\end{equation*}
\notag
$$
It is well known that for $x\neq 0$ we have for $y\in \mathbb{R}^d$
$$
\begin{equation}
F_x(y) = \|x\|_p^{1-p}\sum_{j=1}^d |x_j|^{p-2}x_jy_j.
\end{equation}
\tag{2.10}
$$
Example 2.3. Let $X=\ell^d_p$, $2<p<\infty$. Set Example 2.4. Let $X=\ell^d_p$, $1< p\leqslant 2$. As above, $|F_x(e_j)| = |x_j|^{p-1}$ and § 3. Other characteristics Proof of Theorem 1.2. The proof of Theorem 1.1 in [5] is based on the following result due to Alon and Gluskin (see, for instance, [4], p. 317, where Theorem 3.1 is formulated for $\varepsilon<1/2$ but its proof also works for $\varepsilon\leqslant 1/2$). Note that in [4] this result is cited as the Alon’s theorem. Subsequently, Kashin informed the author that this result is essentially contained in Gluskin’s paper [1].
Theorem 3.1. Let $A=\|a_{i,j}\|_{i,j=1}^N$ be a square matrix of the form $a_{i,i}=1$, ${i=1,\dots,N}$, $|a_{i,j}|\leqslant \varepsilon\leqslant1/2$, $i\neq j$. Then there exists an absolute constant $C_2$ such that Remark 3.1. We note that Theorem 3.1 and matrices of the above form are related directly to the study of the Kolmogorov widths of an octahedron (see [2], for instance). We need the following corollary of Theorem 3.1. Proposition 3.1. Let $A=\|a_{i,j}\|_{i,j=1}^N$ be a square matrix of the form $a_{i,i}=1$, $i=1,\dots,N$, $|a_{i,j}|\leqslant \varepsilon\leqslant1/2$, $1\leqslant i < j\leqslant N$, and $|a_{i,j}|\leqslant1$, $1\leqslant j<i\leqslant N$. Then Proof. Clearly $\operatorname{rank} A = \operatorname{rank} A^\top$. Consider the Hadamard product $AHA^\top$, where for two matrices $A$ and $B=\|b_{i,j}\|_{i,j=1}^N$ It is known and easy to check that $\operatorname{rank} AHB \leqslant (\operatorname{rank} A)(\operatorname{rank} B)$. Then the matrix $AHA^\top$ satisfies the conditions of Theorem 3.1, and $\operatorname{rank} AHA^\top \leqslant (\operatorname{rank} A)^2$.
The proposition is proved. Note that in Theorem 1.1 we can take $C_1=C_2$. In the same way as Theorem 1.1 was derived from Theorem 3.1 in [5], we can derive from Proposition 3.1 the bounds for the semi-incoherent characteristics $N^u(X,d,\mu)$ and $N^\ell(X,d,\mu)$ presented in Theorem 1.2. Theorem 1.2 is proved. We now establish relations between $N_\mu(d,X)$ and $N^u(X,d,\mu)$ and also between $N'_\mu(d,X)$ and $N^\ell(X,d,\mu)$. Proof. By the negation of the definition of $N_\mu:=N_\mu(d,X)$ the following statement holds:
The construction of $\mathcal{D}_N$ with small $M^u(\mathcal{D}_N)$. We set $N:= N_\mu -1$ and take any normalized set $\{y^1,\dots,y^N\}\subset X$. Then by (3.4) there exists $g^1$, $\|g^1\|=1$, such that $F_{g^1}(y^j)| < \mu$ for $j=1,\dots,N$. We now delete $y^1$ and apply (3.4) to the set $\{y^2,\dots,y^N,g^1\}$. This gives us an element $g^2$, $\|g^2\|=1$, such that $F_{g^2}(y^j)| < \mu$ for $j=2,\dots,N$ and $|F_{g^2}(g^1)| < \mu$. Clearly, $g^2\neq g^1$. We continue this process and build a normalized set $\{g^1,\dots,g^N\}$ with the property
$$
\begin{equation*}
|F_{g^j}(g^i)| < \mu, \qquad 1\leqslant i < j\leqslant N,
\end{equation*}
\notag
$$
which means that $M^u(\mathcal{D}_N)<\mu $.
Therefore, from the definition of $N^u(X,d,\mu)$ we obtain We proceed to the second inequality. The proof in this case is similar to the above. By the negation of the definition of $N'_\mu:=N'_\mu(d,X)$ the following statement holds:
$$
\begin{equation}
\begin{gathered} \, \notag \forall\, \{y^1,\dots,y^N\}\subset X \quad \|y^j\|=1, \quad j=1,\dots, N, \quad N< N_\mu', \\ \exists\, x,\, \|x\|=1,\quad \text{such that } |F_{y^j}(x)|< \mu, \quad j=1,\dots,N. \end{gathered}
\end{equation}
\tag{3.5}
$$
The construction of $\mathcal{D}_N$ with small $M^\ell(\mathcal{D}_N)$. We set $N:= N'_\mu -1$ and take any normalized set $\{y^1,\dots,y^N\}\subset X$. Then by (3.5) there exists $g^1$, $\|g^1\|=1$, such that $F_{y^j}(g^1)| < \mu$ for $j=1,\dots,N$. We now delete $y^1$ and apply (3.5) to the set $\{y^2,\dots,y^N,g^1\}$. This gives us an element $g^2$, $\|g^2\|=1$, such that $F_{y^j}(g^2)| < \mu$ for $j=2,\dots,N$ and $|F_{g^1}(g^2)| < \mu$. We continue this process and build a normalized set $\{g^1,\dots,g^N\}$ with the property
$$
\begin{equation*}
|F_{g^i}(g^j)| < \mu, \qquad 1\leqslant i < j\leqslant N,
\end{equation*}
\notag
$$
which means that $M^\ell(\mathcal{D}_N)<\mu $.
Therefore, from the definition of $N^\ell(X,d,\mu)$ we obtain Theorem 3.2 is proved. § 4. On constructive coveringAs above, let $X$ be a uniformly smooth Banach space with modulus of smoothness $\rho(u)$. For $\mu\in (0,1]$ let $a(\mu):=a(\rho,\mu)$ denote the unique nonzero solution of the equation It is easy to see that a solution exists, and we have $a(\mu)\leqslant 1$ by (1.5). Then $4\rho(2a(\mu))= a(\mu)\mu\leqslant 1$. Given $\mu \in (0,1]$, consider a system $\mathcal{D}\in \operatorname{Inc}(\mu)$. We now describe a greedy-type algorithm that provides a good covering for $B_X$.The Dual Thresholding Covering Algorithm with parameter $\mu$ and system $\mathcal{D}$ ($\mathrm{DTCA}(\mu,\mathcal{D})$)Let $\mu\in (0,1]$ and $\mathcal{D}\in \operatorname{Inc}(\mu)$. The algorithm is defined recursively. Take $x\in B_X$. Set $x^0:=x$ and $G_0(x):=0$. Iteration 1. If $\|x^0\|<1/2$, then we set $G_1(x) =0$ and $x^1=x^0$. If $\|x^0\|\geqslant 1/2$, then we make the following thresholding step with respect to $\mathcal{D} := \{g^j\}_{j=1}^N \in \operatorname{Inc}(\mu)$. Find $\varphi_1 \in \mathcal{D}$ such that Such $\varphi_1$ exists by our assumption that $\mathcal{D}\in \operatorname{Inc}(\mu)$. Set
$$
\begin{equation*}
G_1(x):= (\operatorname{sign} F_{x^0}(\varphi_1)) a(\mu) \varphi_1, \qquad x^1 := x-G_1(x)\quad\text{and} \quad r(\mu) := 1-\frac{\mu a(\mu)}2.
\end{equation*}
\notag
$$
Iteration $m$. Suppose that after $m-1$ iterations we have an approximant $G_{m-1}(x)$ and a residual $x^{m-1} := x- G_{m-1}(x)$. If $\|x^{m-1}\|<r(\mu)^{m-1}/2$, then we set $G_m(x) =G_{m-1}(x)$ and $x^m=x^{m-1}$. If $\|x^{m-1}\|\geqslant r(\mu)^{m-1}/2$, then we make the following thresholding step with respect to $\mathcal{D} := \{g^j\}_{j=1}^N \in \operatorname{Inc}(\mu)$. Find $\varphi_m \in \mathcal{D}$ such that Such $\varphi_m$ exists by our assumption that $\mathcal{D}\in \operatorname{Inc}(\mu)$. Set
$$
\begin{equation*}
G_m(x):= G_{m-1}(x) + (\operatorname{sign} F_{x^{m-1}}(\varphi_m)) r(\mu)^{m-1} a(\mu) \varphi_m\quad\text{and} \quad x^m := x-G_m(x).
\end{equation*}
\notag
$$
Remark 4.1. Note that we can replace the thresholding conditions (4.2) and (4.3) by a greedy condition: find $\varphi_m \in \mathcal{D}$ such that Proposition 4.1. Let $\mu\in (0,1]$ and $\mathcal{D}\in \operatorname{Inc}(\mu)$. Then after $m$ iterations of the $\mathrm{DTCA}(\mu,\mathcal{D})$, for each $x\in B_X$ we obtain Proof. The proof goes by induction. We begin with the first iteration. If $\|x\|<1/2$ then, clearly, $\|x\| \leqslant r(\mu)$. Suppose that $\|x\|\geqslant 1/2$ and $\varphi_1$ is such that $F_{x^0}(\varphi_1) \geqslant\mu$ (the case $-F_{x^0}(\varphi_1) \geqslant\mu$ is treated in the same way). Then by Lemma 2.1 we have
Consider the $m$th iteration. Suppose that $\|x^{m-1}\|\leqslant r(\mu)^{m-1}$. If $\|x^{m-1}\|<r(\mu)^{m-1}/2$ then, clearly, $\|x^m\|=\|x^{m-1}\| \leqslant r(\mu)^m$. If $\|x^{m-1}\|\geqslant r(\mu)^{m-1}/2$ and $F_{x^{m-1}}(\varphi_m) \geqslant\mu$, then, as above, in (4.5), we obtain
$$
\begin{equation}
\begin{aligned} \, \notag \|x^m\| &=\|x-G_m(x)\| = \|x^{m-1} - a(\mu)r(\mu)^{m-1}\varphi_m\| \\ \notag &\leqslant \|x^{m-1}\| - a(\mu)r(\mu)^{m-1} F_{x^{m-1}}(\varphi_m) + 2\|x^{m-1}\|\rho(2a(\mu)) \\ &\leqslant r(\mu)^{m-1}(1-\mu a(\mu) +2\rho(2a(\mu))) \leqslant r(\mu)^m. \end{aligned}
\end{equation}
\tag{4.6}
$$
The proposition is proved. Remark 4.2. By Remark 4.1 Proposition 4.1 holds for the dual greedy version of the $\mathrm{DTCA}(\mu,\mathcal{D})$. We point out that Proposition 4.1 also holds for the following $X$-greedy version of the $\mathrm{DTCA}(\mu,\mathcal{D})$. At the $m$th iteration we find an element $\psi_m \in \mathcal{D}$ and a sign $\epsilon_m \in \{-1,0,1\}$ such that AcknowledgementsThe author is grateful to Tomer Milo for bringing to his attention the problem with Theorem 5.2 in [5]. Also, the author is grateful to the referee for their valuable comments and suggestions. 
Citation in format AMSBIB
\Bibitem{Tem25} |
|
||||||||||
|
Contact us: |
Terms of Use
|
Registration to the website |
Logotypes |
|