| Russian Mathematical Surveys |
|
|
|
|
|
On greedy approximation in complex Banach spaces A. V. Gasnikovabc, V. N. Temlyakovdbef a Ivannikov institute for System Programming of Russian Academy of Sciences, Moscow, Russia b Steklov Mathematical Institute of Russian Academy of Sciences, Moscow, Russia c Innopolis University, Innopolis, Russia d University of South Carolina, Columbia, USA e Lomonosov Moscow State University, Moscow, Russia f Moscow Center for Fundamental and Applied Mathematics, Moscow, Russia
Bibliographic databases:
   1. IntroductionSparse and greedy approximation theory is important in applications. This theory has actively been developing for about 40 years. In the beginning researchers were interested in approximation in Hilbert spaces (see, for instance, [12], [15], [17], [18], [1], [7], [4], and [2]; for a detailed history, see [22]). Later, this theory was extended to the case of real Banach spaces (see, for instance, [10], [20], [13], and [5]; for a detailed history see [22] and [23]) and to the case of convex optimization (see, for instance, [3], [11], [16], [19], [24], [25], [8], [14], and [6]). The reader can find some open problems in the book [22]. We study greedy approximation with respect to arbitrary dictionaries in Banach spaces. This general theory is well developed in the case of real Banach spaces (see the book [22]). Recently (see [9]) some results proved in the case of real Banach spaces were extended to the case of complex Banach spaces. The Weak Chebyshev Greedy Algorithm (WCGA) was studied in [9]. In this paper we discuss greedy algorithms other than the WCGA. For them we extend some results known in the real case to the case of complex Banach spaces. We use the same main ideas as in the real case: first, we prove a recurrent inequality between the norms ‖fm‖ and ‖fm−1‖ of the residuals of the algorithm; second, we analyze this recurrent inequality. The step from the real case to the complex case requires some technical modifications in the proofs of the corresponding recurrent inequalities. For the reader’s convenience we present a detailed analysis here. Let X be a (real or complex) Banach space with norm ‖⋅‖. We say that a set D of elements (functions) from X is a dictionary if each g∈D has a norm bounded by one (‖g‖⩽1) and the closure of spanD is X. It is convenient for us to consider, along with the dictionary D, its symmetrization. In the case of real Banach spaces we set In the case of complex Banach spaces we set In the above notation D∘ symbol ∘ stands for the unit circle.Following the standard notation, set and denote the closure (in X) of Ao1(D) by A1(D). Then it is clear that A1(D) is the closure (in X) of the convex hull of D± in the real case and of D∘ in the complex case. Also, denote by conv(D) the closure (in X) of the convex hull of D.We introduce a new norm, associated with the dictionary D, in the dual space X∗ by the formula Note that, clearly, in the real case \|F\|_{\mathcal D}=\sup_{\phi\in{\mathcal D}^\pm}F(\phi) and in the complex case \|F\|_{\mathcal D}= \sup_{\phi\in{\mathcal D}^{\circ}}\operatorname{Re}(F(\phi)).In this paper we study greedy algorithms with respect to {\mathcal D}. For a non-zero element h\in X we let F_h denote a norming (peak) functional for h: The existence of such a functional is guaranteed by the Hahn–Banach theorem.2. Definitions and lemmasWe consider here approximation in uniformly smooth Banach spaces. For a Banach space X we define its modulus of smoothness
\begin{equation*}
\rho(u):=\rho(u,X):=\sup_{\|x\|=\|y\|=1} \biggl(\frac{1}{2}(\|x+uy\|+\|x-uy\|)-1\biggr).
\end{equation*}
\notag
A uniformly smooth Banach space is one with the property It is easy to see that for any Banach space X its modulus of smoothness \rho(u) is an even convex function satisfying the inequalities
\begin{equation*}
\max(0,u-1)\leqslant \rho(u)\leqslant u,\qquad u\in (0,\infty).
\end{equation*}
\notag
It is well known (see, for instance, [10]) that in the case X=L_p, 1\leqslant p < \infty, we have
\begin{equation}
\rho(u,L_p) \leqslant \begin{cases} \dfrac{u^p}{p} & \text{if}\ \ 1\leqslant p\leqslant 2, \vphantom{\Biggl\}} \\ \dfrac{(p-1)u^2}{2} & \text{if}\ \ 2\leqslant p<\infty. \end{cases}
\end{equation}
\tag{2.1}
We note that from the definition of the modulus of smoothness we obtain the following inequality (in the real case see, for instance, [22], p. 336). Proof. We have
\begin{equation*}
\|x+uy\|\geqslant |F_x(x+uy)|\geqslant \operatorname{Re}(F_x(x+uy))=\|x\|+\operatorname{Re}(uF_x(y)).
\end{equation*}
\notag
This proves the left-hand inequality. Next, from the definition of the modulus of smoothness it follows that
\begin{equation}
\|x+uy\|+\|x-uy\|\leqslant 2\|x\|\biggl(1+\rho\biggl(u\,\frac{\|y\|}{\|x\|}\biggr)\biggr).
\end{equation}
\tag{2.3}
Also,
\begin{equation}
\|x-uy\|\geqslant |F_x(x-uy)| \geqslant \operatorname{Re}(F_x(x-uy))= \|x\|-\operatorname{Re}(uF_x(y)).
\end{equation}
\tag{2.4}
Combining (2.3) and (2.4) we obtain
\begin{equation*}
\|x+uy\|\leqslant \|x\|+\operatorname{Re}(uF_x(y))+ 2\|x\|\rho\biggl(u\,\frac{\|y\|}{\|x\|}\biggr).
\end{equation*}
\notag
This proves the second inequality. \Box We will use the following three simple and well-known lemmas. In the case of real Banach spaces these lemmas were proved, for instance, in [22], Chap. 6, pp. 342–343. Lemma 2.2. Let X be a uniformly smooth Banach space and L be a finite-dimensional subspace of X. For any f\in X\setminus L let f_L denote the best approximant of f in L. Then for any \phi \in L. Proof. Let us assume the contrary: there is \phi \in L such that \|\phi\|=1 and Denote by \nu the complex conjugate of \operatorname{sign}(F_{f-f_L}(\phi)), where \operatorname{sign} z:=z/|z| for z\ne 0. Then \nu F_{f-f_L}(\phi)=|F_{f-f_L}(\phi)|. For any \lambda\geqslant 0, from the definition of \rho(u) we obtain
\begin{equation}
\|f-f_L-\lambda \nu\phi\|+\|f-f_L+\lambda \nu\phi\| \leqslant 2\|f-f_L\|\biggl(1+\rho\biggl(\frac{\lambda}{\|f-f_L\|}\biggr)\biggr).
\end{equation}
\tag{2.5}
Next,
\begin{equation}
\|f-f_L+\lambda \nu\phi\| \geqslant |F_{f-f_L}(f-f_L+\lambda\nu\phi)|= \|f-f_L\|+\lambda\beta.
\end{equation}
\tag{2.6}
Combining (2.5) and (2.6) we obtain
\begin{equation}
\|f-f_L-\lambda\nu\phi\|\leqslant \|f-f_L\|\biggl(1-\frac{\lambda\beta}{\|f-f_L\|}+ 2\rho\biggl(\frac{\lambda}{\|f-f_L\|}\biggr)\!\biggr).
\end{equation}
\tag{2.7}
Taking into account that \rho(u)=o(u), we find \lambda'>0 such that
\begin{equation*}
\biggl(1-\frac{\lambda'\beta}{\|f-f_L\|}+ 2\rho\biggl(\frac{\lambda'}{\|f-f_L\|}\biggr)\!\biggr)<1.
\end{equation*}
\notag
Then (2.7) gives which contradicts the assumption that f_L \in L is the best approximant of f. \Box Remark 2.1. The condition F_{f-f_L}(\phi)=0 for all \phi \in L is also a sufficient condition for f_L\in L to be a best approximant of f in L. Indeed, for any g \in L we have Proof. The inequality
\begin{equation*}
\sup_{g\in {\mathcal D}}|F(g)| \leqslant \sup_{f\in A_1({\mathcal D})} |F(f)|
\end{equation*}
\notag
is obvious because {\mathcal D} \subset A_1({\mathcal D}). We prove the reverse inequality. Take any f\in A_1({\mathcal D}). Then for any \varepsilon >0 there exist g_1^\varepsilon,\dots,g_N^\varepsilon \in {\mathcal D} and numbers a_1^\varepsilon,\dots,a_N^\varepsilon such that |a_1^\varepsilon|+\cdots+|a_N^\varepsilon| \leqslant 1 and
\begin{equation*}
\biggl\|f-\sum_{i=1}^Na_i^\varepsilon g_i^\varepsilon\biggr\| \leqslant \varepsilon.
\end{equation*}
\notag
Thus,
\begin{equation*}
|F(f)| \leqslant \|F\|\varepsilon+ \biggl|F\biggl(\,\sum_{i=1}^Na_i^\varepsilon g_i^\varepsilon\biggr)\biggr| \leqslant \varepsilon \|F\|+\sup_{g\in {\mathcal D}}|F(g)|,
\end{equation*}
\notag
which proves the lemma. \Box Proof. The inequality
\begin{equation*}
\sup_{g\in {\mathcal D}}\operatorname{Re}(F(g)) \leqslant \sup_{f\in \operatorname{conv}({\mathcal D})} \operatorname{Re}(F(f))
\end{equation*}
\notag
is obvious because {\mathcal D} \subset \operatorname{conv}({\mathcal D}). We prove the reverse inequality. Take any f\in \operatorname{conv}({\mathcal D}). Then for any \varepsilon >0 there exist g_1^\varepsilon,\dots,g_N^\varepsilon \in {\mathcal D} and non-negative numbers a_1^\varepsilon,\dots,a_N^\varepsilon such that a_1^\varepsilon+\cdots+a_N^\varepsilon=1 and
\begin{equation*}
\biggl\|f-\sum_{i=1}^Na_i^\varepsilon g_i^\varepsilon\biggr\| \leqslant \varepsilon.
\end{equation*}
\notag
Thus,
\begin{equation*}
\operatorname{Re}(F(f)) \leqslant \|F\|\varepsilon+\operatorname{Re} \biggl(F\biggl(\,\sum_{i=1}^Na_i^\varepsilon g_i^\varepsilon\biggr)\!\biggr) \leqslant \varepsilon \|F\|+\sup_{g\in {\mathcal D}} \operatorname{Re}(F(g)),
\end{equation*}
\notag
which proves the lemma. \Box 3. Main resultsIn this section we discuss three greedy-type algorithms and prove convergence and rate of convergence results for those algorithms. In the case of real Banach spaces these algorithms and the corresponding results on their convergence and rate of convergence are known. We show here how to modify these algorithms to the case of complex Banach spaces. 3.1. WGAFRThe following algorithm — WGAFR — can be defined in the same way in both the real and complex cases. We present the definition in the complex case. The Weak Greedy Algorithm with Free Relaxation (WGAFR). Let \tau:=\{t_m\}_{m=1}^\infty, t_m\in[0,1], be a weakness sequence. We define f_0:=f and G_0:=0. Then for each m\geqslant 1 we have the following inductive definition. (1) \varphi_m \in {\mathcal D} is any element satisfying
\begin{equation*}
|F_{f_{m-1}}(\varphi_m)| \geqslant t_m\|F_{f_{m-1}}\|_{\mathcal D}.
\end{equation*}
\notag
(2) Find w_m\in {\mathbb C} and \lambda_m\in{\mathbb C} such that
\begin{equation*}
\|f-((1-w_m)G_{m-1}+\lambda_m\varphi_m)\|= \inf_{\lambda,w\in{\mathbb C}}\|f-((1-w)G_{m-1}+\lambda\varphi_m)\|
\end{equation*}
\notag
and define (3) Let We begin with the main lemma. In the case of real Banach spaces this lemma is known (see, for instance, [22], p. 350, Lemma 6.20). Lemma 3.1. Let X be a uniformly smooth complex Banach space with modulus of smoothness \rho(u). Take a number \varepsilon\geqslant 0 and two elements f and f^\varepsilon of X such that
\begin{equation*}
\|f-f^\varepsilon\| \leqslant \varepsilon,\qquad \frac{f^\varepsilon}{A(\varepsilon)} \in A_1({\mathcal D})
\end{equation*}
\notag
for some number A(\varepsilon)\geqslant \varepsilon. Then for the residual of the WGAFR after m iterations we have
\begin{equation*}
\|f_m\| \leqslant \|f_{m-1}\|\inf_{\lambda\geqslant0} \biggl(1-\frac{\lambda t_m}{A(\varepsilon)} \biggl(1-\frac{\varepsilon}{\|f_{m-1}\|}\biggr)+ 2\rho\biggl(\frac{5\lambda}{\|f_{m-1}\|}\biggr)\!\biggr),
\end{equation*}
\notag
for m=1,2,\dots . Proof. Denote by \nu the complex conjugate of \operatorname{sign} F_{f_{m-1}}(\varphi_m), where \operatorname{sign} z:=z/|z| for z\ne 0. Then \nu F_{f_{m-1}}(\varphi_m)=|F_{f_{m-1}}(\varphi_m)|. By the definition of f_m
\begin{equation*}
\|f_m\|\leqslant \inf_{\lambda\geqslant0,w\in{\mathbb C}}\|f_{m-1}+ wG_{m-1}-\lambda\nu\varphi_m\|.
\end{equation*}
\notag
As in the proof of Lemma 2.2 we use the inequality
\begin{equation}
\begin{aligned} \, \nonumber &\|f_{m-1}+wG_{m-1}-\lambda\nu\varphi_m\|+\|f_{m-1}-wG_{m-1}+ \lambda\nu\varphi_m\| \\ &\qquad \leqslant 2\|f_{m-1}\|\biggl(1+\rho\biggl(\frac{\|wG_{m-1}- \lambda\nu\varphi_m\|}{\|f_{m-1}\|}\biggr)\!\biggr) \end{aligned}
\end{equation}
\tag{3.1}
and estimate for \lambda\geqslant0:
\begin{equation*}
\begin{aligned} \, &\|f_{m-1}-wG_{m-1}+\lambda\nu\varphi_m\|\geqslant \operatorname{Re}(F_{f_{m-1}}(f_{m-1}-wG_{m-1}+\lambda\nu\varphi_m)) \\ &\qquad\geqslant \|f_{m-1}\|-\operatorname{Re}(F_{f_{m-1}}(wG_{m-1}))+ \lambda t_m\sup_{g\in{\mathcal D}}|F_{f_{m-1}}(g)| \\ &\qquad=\|f_{m-1}\|-\operatorname{Re}(F_{f_{m-1}}(wG_{m-1}))+ \lambda t_m\sup_{\phi\in A_1({\mathcal D})}|F_{f_{m-1}}(\phi)|\quad (\text{by Lemma 2.3}) \\ &\qquad\geqslant \|f_{m-1}\|-\operatorname{Re}(F_{f_{m-1}}(wG_{m-1}))+ \frac{\lambda t_m}{A(\varepsilon)}|F_{f_{m-1}}(f^\varepsilon)| \\ &\qquad\geqslant\|f_{m-1}\|-\operatorname{Re}(F_{f_{m-1}}(wG_{m-1}))+ \frac{\lambda t_m}{A(\varepsilon)}(\operatorname{Re}(F_{f_{m-1}}(f))- \varepsilon). \end{aligned}
\end{equation*}
\notag
We set w^*:=\lambda t_m/A(\varepsilon) and obtain
\begin{equation}
\|f_{m-1}-w^*G_{m-1}+\lambda\nu\varphi_m\|\geqslant\|f_{m-1}\|+ \frac{\lambda t_m}{A(\varepsilon)}(\|f_{m-1}\|-\varepsilon).
\end{equation}
\tag{3.2}
Combining (3.1) and (3.2) we get that
\begin{equation*}
\|f_m\| \leqslant \|f_{m-1}\|\inf_{\lambda\geqslant0} \biggl(1-\frac{\lambda t_m}{A(\varepsilon)} \biggl(1-\frac{\varepsilon}{\|f_{m-1}\|}\biggr) +2\rho\biggl(\frac{\|w^*G_{m-1}-\lambda\nu\varphi_m\|} {\|f_{m-1}\|}\biggr)\!\biggr).
\end{equation*}
\notag
We now estimate
\begin{equation*}
\|w^*G_{m-1}-\lambda\nu\varphi_m\| \leqslant w^*\|G_{m-1}\|+\lambda.
\end{equation*}
\notag
Next,
\begin{equation*}
\|G_{m-1}\|=\|f-f_{m-1}\|\leqslant 2\|f\|\leqslant 2(\|f^\varepsilon\|+\varepsilon)\leqslant2(A(\varepsilon)+\varepsilon).
\end{equation*}
\notag
Thus, under the assumption A(\varepsilon)\geqslant\varepsilon we obtain
\begin{equation*}
w^*\|G_{m-1}\|\leqslant \frac{2\lambda t_m(A(\varepsilon)+\varepsilon)} {A(\varepsilon)} \leqslant 4\lambda.
\end{equation*}
\notag
Finally, This completes the proof of the lemma. \Box Remark 3.1. It follows from the definition of the \operatorname{WGAFR} that the sequence \{\|f_m\|\} is non-increasing. We now prove a convergence theorem for an arbitrary uniformly smooth Banach space. The modulus of smoothness \rho(u) of a uniformly smooth Banach space is an even convex function such that \rho(0)=0 and \lim_{u\to0}\rho(u)/u=0. The function s(u):=\rho(u)/u, s(0):=0, associated with \rho(u) is a continuous increasing function on [0,\infty). Therefore, the inverse function s^{-1}(\,\cdot\,) is well defined. The following theorem is known in the case of real Banach spaces (see, for instance, [22], p. 352, Theorem 6.22). Theorem 3.1. Let X be a uniformly smooth complex Banach space with modulus of smoothness \rho(u). Assume that a sequence \tau:=\{t_k\}_{k=1}^\infty satisfies the following condition: for each \theta >0 we have Then for any f\in X we have for the WGAFR Proof. This proof only uses Lemma 3.1, which provides a relation between the residuals \|f_m\| and \|f_{m-1}\|. It repeats the corresponding proof in the real case. For completeness we present this simple proof here. By Remark 3.1 \{\|f_m\|\} is a non-increasing sequence. Therefore, We prove that \beta=0 by contradiction. Assume the contrary: \beta>0. Then for any m we have We set \varepsilon=\beta/2 and find f^\varepsilon such that
\begin{equation*}
\|f-f^\varepsilon\| \leqslant \varepsilon \quad \text{and}\quad \frac{f^\varepsilon}{A(\varepsilon)} \in A_1({\mathcal D}),
\end{equation*}
\notag
for some A(\varepsilon)\geqslant\varepsilon. Then by Lemma 3.1 we obtain
\begin{equation*}
\|f_m\| \leqslant \|f_{m-1}\|\inf_{\lambda\geqslant0} \biggl(1-\frac{\lambda t_m}{2A(\varepsilon)}+ 2\rho\biggl(\frac{5\lambda}{\beta}\biggr)\!\biggr).
\end{equation*}
\notag
Let us specify \theta:=\beta/(40A(\varepsilon)) and take \lambda=\beta s^{-1}(\theta t_m)/5. Then
\begin{equation*}
\|f_m\| \leqslant \|f_{m-1}\|\bigl(1-2\theta t_m s^{-1}(\theta t_m)\bigr).
\end{equation*}
\notag
The assumption implies that We obtain a contradiction, which proves the theorem. \Box Remark 3.2. The reader can find some necessary conditions on the weakness sequence \tau for the convergence of the WCGA, for instance, in [22], p. 346, Proposition 6.13. We now proceed to results on the rate of convergence. The following theorem is known in the case of real Banach spaces (see, for instance, [22], p. 353, Theorem 6.23). Theorem 3.2. Let X be a uniformly smooth Banach space with modulus of smoothness \rho(u)\leqslant \gamma u^q, 1<q\leqslant 2. Take a number \varepsilon\geqslant 0 and two elements f and f^\varepsilon of X such that
\begin{equation*}
\|f-f^\varepsilon\| \leqslant \varepsilon,\qquad \frac{f^\varepsilon}{A(\varepsilon)} \in A_1({\mathcal D}),
\end{equation*}
\notag
for some number A(\varepsilon)>0. Then for the residual of the WGAFR after m iterations we have Proof. This proof only uses Lemma 3.1, which provides a relation between the residuals \|f_m\| and \|f_{m-1}\|. It repeats the corresponding proof in the real case. For completeness we present this proof here. It is clear that it suffices to consider the case A(\varepsilon)\geqslant\varepsilon. Otherwise, \|f_m\|\leqslant\|f\|\leqslant\|f^\varepsilon\|+ \varepsilon\leqslant2\varepsilon. Also assume that \|f_m\|>2\varepsilon (otherwise Theorem 3.2 holds trivially). Then, by Remark 3.1 we have \|f_k\|>2\varepsilon for all k=0,1,\dots,m. By Lemma 3.1 we obtain
\begin{equation}
\|f_k\| \leqslant \|f_{k-1}\|\inf_{\lambda\geqslant0} \biggl(1-\frac{\lambda t_k}{2A(\varepsilon)}+ 2\gamma\biggl(\frac{5\lambda}{\|f_{k-1}\|}\biggr)^{\!q}\,\biggr).
\end{equation}
\tag{3.4}
We choose \lambda from the equation
\begin{equation*}
\frac{\lambda t_k}{4A(\varepsilon)}= 2\gamma \biggl(\frac{5\lambda}{\|f_{k-1}\|}\biggr)^{\!q},
\end{equation*}
\notag
which implies that
\begin{equation*}
\lambda=\|f_{k-1}\|^{q/(q-1)}\,5^{-q/(q-1)} (8\gamma A(\varepsilon))^{-1/(q-1)}t_k^{1/(q-1)}.
\end{equation*}
\notag
Define Using notation p:=q/(q-1), we deduce from (3.4)
\begin{equation*}
\|f_k\| \leqslant \|f_{k-1}\|\biggl(1-\frac{1}{4}\, \frac{\lambda t_k}{A(\varepsilon)}\biggr)= \|f_{k-1}\|\biggl(1-\frac{t_k^p\|f_{k-1}\|^p}{A_qA(\varepsilon)^p}\biggr).
\end{equation*}
\notag
Raising both sides of this inequality to power p and taking into account the inequality x^r\leqslant x for r\geqslant 1, 0\leqslant x\leqslant 1, we obtain
\begin{equation}
\|f_k\|^p \leqslant \|f_{k-1}\|^p \biggl(1-\frac{t^p_k\|f_{k-1}\|^p}{A_qA(\varepsilon)^p}\biggr).
\end{equation}
\tag{3.5}
We will need the following simple lemma, various versions of which are well known (see, for example, [22], p. 91).
Lemma 3.2. Given a number C_1>0 and a sequence \{a_k\}_{k=1}^\infty, a_k >0, k=1,2,\dots, assume that \{x_m\}_{m=0}^\infty is a sequence of non-negative numbers satisfying the inequalities
\begin{equation*}
x_0 \leqslant C_1, \qquad x_{m+1} \leqslant x_m(1-x_m a_{m+1}), \quad m=1,2,\dots\,.
\end{equation*}
\notag
Then for each m we have Proof. The proof is by induction on m. For m=0 the statement is true by assumption. We prove that the inequality
\begin{equation*}
x_m \leqslant \biggl(\frac{1}{C_1}+\sum_{k=1}^{m} a_k\biggr)^{\!-1} \quad\text{implies that} \quad x_{m+1} \leqslant\biggl(\frac{1}{C_1}+\sum_{k=1}^{m+1} a_k\biggr)^{\!-1}.
\end{equation*}
\notag
If x_{m+1}=0, this statement is obvious. Assume therefore that x_{m+1} > 0. Then we have
\begin{equation*}
x_{m+1}^{-1} \geqslant x_m^{-1}(1-x_m a_{m+1})^{-1} \geqslant x_m^{-1}(1+x_m a_{m+1})=x_m^{-1}+a_{m+1} \geqslant \frac{1}{C_1}+\sum_{k=1}^{m+1} a_k,
\end{equation*}
\notag
which proves the required inequality. \Box We use Lemma 3.2 for x_k:=\|f_k\|^p. Using the estimate \|f\| \leqslant A(\varepsilon)+\varepsilon, we set C_1:= A(\varepsilon)+\varepsilon. We specify a_k:=t^p_k/(A_qA(\varepsilon)^p). Then (3.5) guarantees that we can apply Lemma 3.2. Note that A_q>1. Then Lemma 3.2 gives
\begin{equation}
\|f_m\|^p \leqslant A_q(A(\varepsilon)+ \varepsilon)^p\biggl(1+\sum_{k=1}^m t_k^p\biggr)^{\!-1},
\end{equation}
\tag{3.6}
which implies that
\begin{equation*}
\|f_m\|\leqslant C(q,\gamma)(A(\varepsilon)+ \varepsilon)\biggl(1+\sum_{k=1}^m t_k^p\biggr)^{\!-1/p}.
\end{equation*}
\notag
Theorem 3.2 is proved. \Box 3.2. GAWRIn this subsection we study the Greedy Algorithm with Weakness parameter t and Relaxation {\mathbf r} (\operatorname{GAWR}(t,{\mathbf r})), where {\mathbf r}:=\{r_j\}_{j=1}^\infty, r_j\in [0,1), j=1,2,\dots . In addition to the acronym \operatorname{GAWR}(t,{\mathbf r}), we will use the abbreviated acronym \operatorname{GAWR} for the name of this algorithm. We give a general definition of the algorithm in the case of the weakness sequence \tau. The Greedy Algorithm with Weakness and Relaxation \operatorname{GAWR}(\tau,\mathbf r). Let \tau:=\{t_m\}_{m=1}^\infty, t_m\in[0,1], be a weakness sequence. We define f_0:=f and G_0:=0. Then for each m\geqslant 1 we give the following inductive definition. (1) \varphi_m \in {\mathcal D} is any element satisfying
\begin{equation*}
|F_{f_{m-1}}(\varphi_m)| \geqslant t_m \| F_{f_{m-1}}\|_{\mathcal D}.
\end{equation*}
\notag
(2) Find \lambda_m \in {\mathbb C} such that
\begin{equation*}
\|f-((1-r_m)G_{m-1}+\lambda_m\varphi_m)\|= \inf_{\lambda\in {\mathbb C}}\|f-((1-r_m)G_{m-1}+\lambda\varphi_m)\|
\end{equation*}
\notag
and define (3) Set We now prove results on convergence and rate of convergence for the \operatorname{GAWR}(t,{\mathbf r}), that is, for the \operatorname{GAWR}(\tau,{\mathbf r}) with \tau =\{t_j\}_{j=1}^\infty, t_j=t \in (0,1], j=1,2,\dots . We begin with an analogue of Lemma 3.1. In the case of real Banach spaces Lemma 3.3 is known (see, for instance, [22], p. 355, Lemma 6.24). Lemma 3.3. Let X be a uniformly smooth complex Banach space with modulus of smoothness \rho(u). Take a number \varepsilon\geqslant 0 and two elements f and f^\varepsilon of X such that
\begin{equation*}
\|f-f^\varepsilon\| \leqslant \varepsilon,\qquad \frac{f^\varepsilon}{A(\varepsilon)} \in A_1({\mathcal D}),
\end{equation*}
\notag
for some number A(\varepsilon)>0. Then for the \operatorname{GAWR}(t,\mathbf r) we have the inequality
\begin{equation*}
\|f_m\| \leqslant \|f_{m-1}\|\biggl(1-r_m\biggl(1-\frac{\varepsilon} {\|f_{m-1}\|}\biggr)+2\rho\biggl(\frac{r_m(\|f\|+A(\varepsilon)/t)}{(1-r_m) \|f_{m-1}\|}\biggr)\!\biggr),
\end{equation*}
\notag
for m=1,2,\dots . Proof. As in the above proof of Lemma 3.1, we denote by \nu the complex conjugate of \operatorname{sign} F_{f_{m-1}}(\varphi_m), where \operatorname{sign}z:=z/|z| for z\ne 0. Then \nu F_{f_{m-1}}(\varphi_m)=|F_{f_{m-1}}(\varphi_m)|. The definition of f_m implies that
\begin{equation*}
\|f_m\|\leqslant \inf_{\lambda\geqslant0}\|f-((1-r_m)G_{m-1}+ \lambda\nu\varphi_m)\|.
\end{equation*}
\notag
For any \lambda we have
\begin{equation}
f-((1-r_m)G_{m-1}+\lambda\nu \varphi_m)= (1-r_m)f_{m-1}+r_mf-\lambda\nu \varphi_m,
\end{equation}
\tag{3.7}
and from the definition of \rho(u) with u=\|r_mf-\lambda\nu\varphi_m\|/((1-r_m)\|f_{m-1}\|) we obtain
\begin{equation}
\begin{aligned} \, \nonumber &\|(1-r_m)f_{m-1}+r_mf-\lambda\nu \varphi_m\|+\|(1-r_m)f_{m-1}-r_mf+ \lambda\nu \varphi_m\| \\ &\qquad\leqslant 2(1-r_m)\|f_{m-1}\| \biggl(1+\rho\biggl(\frac{\|r_mf-\lambda\nu\varphi_m\|} {(1-r_m)\|f_{m-1}\|}\biggr)\!\biggr). \end{aligned}
\end{equation}
\tag{3.8}
We have
\begin{equation}
\begin{aligned} \, \nonumber &\|(1-r_m)f_{m-1}-r_mf+\lambda \nu\varphi_m\|\geqslant \operatorname{Re}\bigl(F_{f_{m-1}}((1-r_m)f_{m-1}-r_mf+ \lambda\nu \varphi_m)\bigr) \\ &\qquad=(1-r_m)\|f_{m-1}\|-r_m\operatorname{Re}(F_{f_{m-1}}(f))+ \lambda \operatorname{Re}(\nu F_{f_{m-1}}(\varphi_m)). \end{aligned}
\end{equation}
\tag{3.9}
From the definition of \varphi_m we obtain
\begin{equation}
\nu F_{f_{m-1}}(\varphi_m)=|F_{f_{m-1}}(\varphi_m)| \geqslant t\sup_{g\in{\mathcal D}}|F_{f_{m-1}}(g)|.
\end{equation}
\tag{3.10}
From Lemma 2.3 we deduce that
\begin{equation}
\begin{aligned} \, \nonumber \sup_{g\in{\mathcal D}} |F_{f_{m-1}}(g)|&= \sup_{\phi\in A_1({\mathcal D})}|F_{f_{m-1}}(\phi)| \\ &\geqslant \frac{1}{A(\varepsilon)}|F_{f_{m-1}}(f^\varepsilon)|\geqslant \frac{1}{A(\varepsilon)}(|F_{f_{m-1}}(f)|-\varepsilon). \end{aligned}
\end{equation}
\tag{3.11}
Combining (3.10) and (3.11) we obtain
\begin{equation}
|F_{f_{m-1}}(\varphi_m)|\geqslant \frac{t}{A(\varepsilon)}(|F_{f_{m-1}}(f)|-\varepsilon).
\end{equation}
\tag{3.12}
We now choose \lambda:=\lambda^*:=r_mA(\varepsilon)/t. Then for this \lambda we derive from (3.9) and (3.12) the inequality
\begin{equation}
\|(1-r_m)f_{m-1}-r_mf+\lambda^*\nu \varphi_m\|\geqslant (1-r_m)\|f_{m-1}\|-r_m\varepsilon.
\end{equation}
\tag{3.13}
Relations (3.8) and (3.13) imply that The lemma is proved. We begin with a convergence result. It is known that the version of Lemma 3.3 for the real case implies the corresponding convergence result — Theorem 3.3 below — in the real case (see, for instance, [22], pp. 355–357). That same proof derives Theorem 3.3 from Lemma 3.3. We do not present it here. Theorem 3.3. Let the sequence {\mathbf r}:=\{r_k\}_{k=1}^\infty, r_k\in[0,1), satisfy the conditions
\begin{equation*}
\sum_{k=1}^\infty r_k =\infty,\qquad r_k\to 0\quad\textit{as}\ \ k\to\infty.
\end{equation*}
\notag
Then the \operatorname{GAWR}(t,{\mathbf r}) converges in any uniformly smooth Banach space for each f\in X and for all dictionaries {\mathcal D}. The situation with results on the rate of convergence is very similar to the situation with the convergence result described above. The real-case proof (see, for instance, [22], pp. 357–358) derives Theorem 3.4 from Lemma 3.3. We do not present it here. Theorem 3.4. Let X be a uniformly smooth Banach space with modulus of smoothness \rho(u)\leqslant \gamma u^q, 1<q\leqslant 2. Let {\mathbf r}:=\{2/(k+2)\}_{k=1}^\infty. Consider the \operatorname{GAWR}(t,{\mathbf r}). Then for a pair of functions f, f^\varepsilon satisfying we have3.3. Incremental algorithmWe proceed to one more greedy-type algorithm (see [21]). Let \varepsilon=\{\varepsilon_n\}_{n=1}^\infty , \varepsilon_n> 0, n=1,2,\dots . The following greedy algorithm was introduced and studied in [21] (see also [22], pp. 361–363) in the case of real Banach spaces. The Incremental Algorithm with schedule \varepsilon (\operatorname{IA}(\varepsilon)). Let f\in\operatorname{conv}({\mathcal D}). Denote f_0^{i,\varepsilon}:=f and G_0^{i,\varepsilon}:=0. Then for each m\geqslant 1 we have the following inductive definition. (1) \varphi_m^{i,\varepsilon} \in {\mathcal D} is any element satisfying
\begin{equation*}
F_{f_{m-1}^{i,\varepsilon}}(\varphi_m^{i,\varepsilon}-f) \geqslant -\varepsilon_m.
\end{equation*}
\notag
(2) Define
\begin{equation*}
G_m^{i,\varepsilon}:=\biggl(1-\frac{1}{m}\biggr)G_{m-1}^{i,\varepsilon}+ \frac{\varphi_m^{i,\varepsilon}}{m}\,.
\end{equation*}
\notag
(3) Let It is clear from the definition of the \operatorname{IA}(\varepsilon) that
\begin{equation}
G_m^{i,\varepsilon}=\frac{1}{m}\sum_{j=1}^m \varphi_j^{i,\varepsilon}.
\end{equation}
\tag{3.14}
We now modify the definition of \operatorname{IA}(\varepsilon) to make it suitable for complex Banach spaces. Incremental Algorithm (complex) with schedule \varepsilon (\operatorname{IAc}(\varepsilon)). Let f\in A_1({\mathcal D}). Denote f_0^{{\rm c},\varepsilon}:= f and G_0^{{\rm c},\varepsilon}:=0. Then for each m\geqslant 1 we have the following inductive definition. (1) \varphi_m^{{\rm c},\varepsilon} \in {\mathcal D}^\circ is any element satisfying
\begin{equation*}
\operatorname{Re}(F_{f_{m-1}^{{\rm c},\varepsilon}} (\varphi_m^{{\rm c},\varepsilon}-f))\geqslant -\varepsilon_m.
\end{equation*}
\notag
Denote by \nu_m the complex conjugate of \operatorname{sign} F_{f_{m-1}^{{\rm c},\varepsilon}}(\varphi_m^{{\rm c},\varepsilon}), where \operatorname{sign} z:=z/|z| for z\ne 0. (2) Define
\begin{equation*}
G_m^{{\rm c},\varepsilon}:=\biggl(1-\frac{1}{m}\biggr) G_{m-1}^{{\rm c},\varepsilon}+ \frac{\nu_m\varphi_m^{{\rm c},\varepsilon}}{m}\,.
\end{equation*}
\notag
(3) Let It follows from the definition of the \operatorname{IAc}(\varepsilon) that
\begin{equation}
G_m^{{\rm c},\varepsilon}= \frac{1}{m}\sum_{j=1}^m \nu_j\varphi_j^{{\rm c},\varepsilon},\qquad |\nu_j|=1, \quad j=1,2,\dots\,.
\end{equation}
\tag{3.15}
Note that by the definition of \nu_m we have
\begin{equation*}
F_{f_{m-1}^{{\rm c},\varepsilon}}(\nu_m\varphi_m^{{\rm c},\varepsilon})= |F_{f_{m-1}^{{\rm c},\varepsilon}}(\varphi_m^{{\rm c},\varepsilon})|,
\end{equation*}
\notag
and therefore, by Lemma 2.3
\begin{equation*}
\begin{aligned} \, \sup_{\phi \in {\mathcal D}^\circ}\operatorname{Re} \bigl(F_{f_{m-1}^{{\rm c},\varepsilon}}(\phi)\bigr)&= \sup_{g \in {\mathcal D}}\bigl|F_{f_{m-1}^{{\rm c},\varepsilon}}(g)\bigr|= \sup_{\phi \in A_1({\mathcal D})} \bigl|F_{f_{m-1}^{{\rm c},\varepsilon}}(\phi)\bigr| \\ &\geqslant \bigl|F_{f_{m-1}^{{\rm c},\varepsilon}}(f)\bigr| \geqslant \operatorname{Re}\bigl(F_{f_{m-1}^{{\rm c},\varepsilon}}(f)\bigr). \end{aligned}
\end{equation*}
\notag
This means that we can always run the \operatorname{IAc}(\varepsilon) for f\in A_1({\mathcal D}). Theorem 3.5. Let X be a uniformly smooth complex Banach space with modulus of smoothness \rho(u)\leqslant \gamma u^q, 1<q\leqslant 2. Define
\begin{equation*}
\varepsilon_n:=K_1\gamma ^{1/q}n^{-1/p},\qquad p=\frac{q}{q-1}\,,\quad n=1,2,\dots\,.
\end{equation*}
\notag
Then for any f\in A_1({\mathcal D}) we have Proof. We use the abbreviated notation f_m:=f_m^{{\rm c},\varepsilon}, \varphi_m:=\nu_m\varphi_m^{{\rm c},\varepsilon}, and G_m:=G_m^{{\rm c},\varepsilon}. Writing we immediately obtain the trivial estimate Since
\begin{equation}
f_m=\biggl(1-\frac{1}{m}\biggr)f_{m-1}-\frac{\varphi_m-f}{m} =\biggl(1-\frac{1}{m}\biggr)\biggl(f_{m-1}-\frac{\varphi_m-f}{m-1}\biggr),
\end{equation}
\tag{3.17}
from Lemma 2.1 for y=\varphi_m-f and u=-1/(m-1) we obtain the inequality
\begin{equation}
\biggl\|f_{m-1}-\frac{\varphi_m-f}{m-1}\biggr\|\leqslant \|f_{m-1}\|\biggl(1+2\rho\biggl(\frac{2}{(m-1)\|f_{m-1}\|}\biggr)\!\biggr)+ \frac{\varepsilon_m}{m-1}\,.
\end{equation}
\tag{3.18}
Using the definition of \varepsilon_m and the assumption \rho(u) \leqslant \gamma u^q, we make the following observation. There exists a constant C(K_1) such that if then
\begin{equation}
2\rho\biggl(\frac{2}{(m-1)\|f_{m-1}\|}\biggr)+ \frac{\varepsilon_m}{(m-1)\|f_{m-1}\|}\leqslant \frac{1}{4m}\,,
\end{equation}
\tag{3.20}
and therefore, by (3.17) and (3.18)
We now need the following technical lemma (see, for instance, [22], p. 357). Lemma 3.4. Let the sequence \{a_n\}_{n=1}^\infty have the following property: given positive numbers \alpha < \gamma \leqslant 1 and A > a_1, we have
\begin{equation}
a_n\leqslant a_{n-1}+A(n-1)^{-\alpha}\quad\textit{for all}\ \ n\geqslant2,
\end{equation}
\tag{3.22}
and if for some v \geqslant2 we have then Then there exists a constant C(\alpha,\gamma) such that Taking (3.16) into account we apply Lemma 3.4 to the sequence a_n=\|f_n\|, n=1,2,\dots, for \alpha=1/p, \beta =3/4 and complete the proof of Theorem 3.5. We now consider one more modification of \operatorname{IA}(\varepsilon), which is suitable for complex Banach spaces and provides a convex combination of dictionary elements. In the case of real Banach spaces it coincides with the \operatorname{IA}(\varepsilon). The Incremental Algorithm (complex and convex) with schedule \varepsilon (\operatorname{IAcc}(\varepsilon)). Let f\in \operatorname{conv}({\mathcal D}). Set f_0^{{\rm cc},\varepsilon}:=f and G_0^{{\rm cc},\varepsilon}:=0. Then, for each m\geqslant 1 we have the following inductive definition. (1) \varphi_m^{{\rm cc},\varepsilon} \in {\mathcal D} is any element satisfying
\begin{equation*}
\operatorname{Re}\bigl(F_{f_{m-1}^{{\rm cc},\varepsilon}} (\varphi_m^{{\rm cc},\varepsilon}-f)\bigr) \geqslant -\varepsilon_m.
\end{equation*}
\notag
(2) Define
\begin{equation*}
G_m^{{\rm cc},\varepsilon}:= \biggl(1-\frac{1}{m}\biggr)G_{m-1}^{{\rm cc},\varepsilon}+ \frac{\varphi_m^{{\rm cc},\varepsilon}}{m}\,.
\end{equation*}
\notag
(3) Let It follows from the definition of the \operatorname{IAcc}(\varepsilon) that
\begin{equation}
G_m^{{\rm cc},\varepsilon}= \frac{1}{m}\sum_{j=1}^m \varphi_j^{{\rm cc},\varepsilon}.
\end{equation}
\tag{3.24}
Note that by Lemma 2.4
\begin{equation*}
\sup_{g \in {\mathcal D}} \operatorname{Re}\bigl(F_{f_{m-1}^{{\rm cc},\varepsilon}}(g)\bigr)= \sup_{\phi \in \operatorname{conv}({\mathcal D})}\operatorname{Re} \bigl(F_{f_{m-1}^{{\rm cc},\varepsilon}}(\phi)\bigr) \geqslant \operatorname{Re}\bigl(F_{f_{m-1}^{{\rm cc},\varepsilon}}(f)\bigr).
\end{equation*}
\notag
This means that we can always run the \operatorname{IAcc}(\varepsilon) for f\in \operatorname{conv}({\mathcal D}). In the same way as Theorem 3.5 was proved above, one can prove the following theorem. Theorem 3.6. Let X be a uniformly smooth Banach space with modulus of smoothness \rho(u)\leqslant \gamma u^q, 1<q\leqslant 2. Define
\begin{equation*}
\varepsilon_n:=K_1\gamma ^{1/q}n^{-1/p},\qquad p=\frac{q}{q-1}\,,\quad n=1,2,\dots\,.
\end{equation*}
\notag
Then for any f\in \operatorname{conv}({\mathcal D}) we have
Citation in format AMSBIB
\Bibitem{GasTem24} |
|
|||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|
Contact us: |
Terms of Use
|
Registration to the website |
Logotypes |
|