Approximation Properties of the Vector Weak Rescaled Pure Greedy Algorithm

Abstract

We first study the error performances of the Vector Weak Rescaled Pure Greedy Algorithm for simultaneous approximation with respect to a dictionary $\mathcal{D}$ in a Hilbert space. We show that the convergence rate of the Vector Weak Rescaled Pure Greedy Algorithm on ${\mathcal{A}}_1\left(\mathcal{D}\right)$ and the closure of the convex hull of the dictionary $\mathcal{D}$ is optimal. The Vector Weak Rescaled Pure Greedy Algorithm has some advantages. It has a weaker convergence condition and a better convergence rate than the Vector Weak Pure Greedy Algorithm and is simpler than the Vector Weak Orthogonal Greedy Algorithm. Then, we design a Vector Weak Rescaled Pure Greedy Algorithm in a uniformly smooth Banach space setting. We obtain the convergence properties and error bound of the Vector Weak Rescaled Pure Greedy Algorithm in this case. The results show that the convergence rate of the VWRPGA on ${\mathcal{A}}_1\left(\mathcal{D}\right)$ is sharp. Similarly, the Vector Weak Rescaled Pure Greedy Algorithm is simpler than the Vector Weak Chebyshev Greedy Algorithm and the Vector Weak Relaxed Greedy Algorithm.

1. Introduction

Approximation using a sparse linear combination of elements from a fixed redundant family is actively used because of its concise representations and increased computational efficiency. It has been applied widely to signal processing, image compression, machine learning and PDE solvers (see [1,2,3,4,5,6,7,8,9,10]). Among others, simultaneous sparse approximation has been utilized in signal vector processing and multi-task learning (see [11,12,13,14]). It is well known that the greedy-type algorithms are powerful tools for generating such sparse approximations (see [15,16,17,18,19]). In particular, vector greedy algorithms are very efficient at approximating a given finite number of target elements simultaneously (see [20,21,22,23]). In this article, we propose a new vector greedy algorithm—the Vector Weak Rescaled Pure Greedy Algorithm (VWRPGA)—for simultaneous approximation. We estimate the error of the VWRPGA and show that its convergence rate on the convex hull of the dictionary is optimal.

Let X be a real Banach space with norm $\parallel ·\parallel$. We say a set of elements $\mathcal{D}\subset X$ is a dictionary, if $\parallel \phi \parallel =1$ for each $\phi \in \mathcal{D}$ and $\overline{\mathrm{span}}\left(\mathcal{D}\right)=X$. We assume that every dictionary $\mathcal{D}$ is symmetric, i.e.,

$\phi \in \mathcal{D} \mathrm{implies} -\phi \in \mathcal{D}.$

If $f_m$ is the output of a greedy algorithm after m iterations, then the efficiency of the approximation can be measured by the decay of the error $\parallel f-f_m\parallel$ as $m\to \infty$. We are mainly concerned with the error $\parallel f-f_m\parallel$. We want to know whether it tends to zero, as $m\to \infty$. If it indeed converges to zero, then what is the convergence rate? To solve these problems, we need the following classes of elements.

For a general dictionary $\mathcal{D}$, we define the class of elements

${\mathcal{A}}_1^o(\mathcal{D},M):=\left\{f:f=\sum _{k\in \Lambda }{c}_k\left(f\right){\phi }_k,{\phi }_k\in \mathcal{D},|\Lambda |<\infty ,\sum _{k\in \Lambda }\left|c_k\left(f\right)\right|\le M\right\}$

and ${\mathcal{A}}_1(\mathcal{D},M)$ as the closure of ${\mathcal{A}}_1^o(\mathcal{D},M)$. Let ${\mathcal{A}}_1\left(\mathcal{D}\right)$ be the union of the classes ${\mathcal{A}}_1(\mathcal{D},M)$ over all $M>0$. Denote $A_1\left(\mathcal{D}\right):={\mathcal{A}}_1(\mathcal{D},1)$. For $f\in {\mathcal{A}}_1\left(\mathcal{D}\right)$, we define its norm as

${\parallel f\parallel }_{{\mathcal{A}}_1\left(\mathcal{D}\right)}:=inf\{M:f\in {\mathcal{A}}_1(\mathcal{D},M)\}.$

We recall some related results in a Hilbert space for the reason that this kind of space has priority in geometric features and practical applications. Let H be a real Hilbert space with an inner product $⟨·,·⟩$ and the norm $\parallel x\parallel :={⟨x,x⟩}^{1/2}$.

The most natural greedy algorithm in a Hilbert space is the Pure Greedy Algorithm (PGA). This algorithm is also known as the Matching Pursuit in signal processing [24]. We recall its definition from [15].

• PGA(H, $\mathcal{D}$):

•Step 0: Define $f_0=0$.

•Step m:

- If $f=f_{m-1}$, stop the algorithm and define $f_k=f_{m-1}=f$ for $k\ge m$.

- If $f\ne f_{m-1}$, choose an element ${\phi }_m\in \mathcal{D}$ such that

$|⟨f-f_{m-1},{\phi }_m⟩|=\underset{\phi \in \mathcal{D}}{sup}\left|⟨f-f_{m-1},\phi ⟩\right|.$

Define the next approximant to be

$f_m=f_{m-1}+⟨f-f_{m-1},{\phi }_m⟩{\phi }_m,$

and proceed to Step $m+1$.

The first upper bound on the rate of convergence of the PGA for $f\in {\mathcal{A}}_1\left(\mathcal{D}\right)$ was obtained in [15] as follows:

$\parallel f-f_m{\parallel \le \parallel f\parallel }_{{\mathcal{A}}_1\left(\mathcal{D}\right)}{m}^{-\frac{1}{6}},m=1,2,\cdots .$

Later, the above estimate of the PGA was improved in [25,26] to $\mathcal{O}\left(m^{-\frac{11}{62}}\right)$ and $\mathcal{O}\left(m^{-\frac{s}{2(s+2)}}\right)$, where s is the root of the equation

${(1+x)}^{\frac{1}{2+x}}\left(1+\frac{1}{1+x}\right)-1-\frac{1}{x}=0$

on the closed interval $[1,1.5].$ It is known that $\frac{s}{2(s+2)}>\frac{11}{62}$.

Note that when $\mathcal{D}$ is an ortho-normal basis of H, it is not difficult to prove that for any $f\in {\mathcal{A}}_1\left(\mathcal{D}\right)$, there holds

(1)$\parallel f-f_m{\parallel \le c\parallel f\parallel }_{{\mathcal{A}}_1\left(\mathcal{D}\right)}{m}^{-\frac{1}{2}},m=1,2,\cdots .$

In addition, there exists an element $f^{*}\in {\mathcal{A}}_1\left(\mathcal{D}\right)$ (see [27]) such that

$\parallel f^{*}-f_m^{*}\parallel =c·m^{-\frac{1}{2}},m=1,2,\cdots .$

Thus, inequality (1) cannot be improved for ortho-normal bases. A natural question arises: does inequality (1) hold for any dictionary $\mathcal{D}\subset H$? Unfortunately, the answer is negative.

In fact, Livshitz and Temlyakov [28] proved that there exists a dictionary $\mathcal{D}\subset H$, a positive constant C and an element $f\in A_1\left(\mathcal{D}\right)$ such that

$\parallel f-f_m\parallel \ge C{m}^{-0.27},m=1,2,\cdots .$

This lower bound on the convergence rate of the PGA indicates that this algorithm does not attain the rate $O\left(m^{-\frac{1}{2}}\right)$ for all $\mathcal{D}$.

In [15], the idea of the best approximation was introduced into the greedy algorithm, which formed the original idea of the Orthogonal Greedy Algorithm (OGA). In order to construct an approximation, the OGA takes the orthogonal projection of f on the subspace generated by all the chosen ${\phi }_1,\cdots ,{\phi }_m$. We recall its definition from [15].

• OGA(H, $\mathcal{D}$):

•Step 0: Define $f_0=0$.

•Step m:

- If $f=f_{m-1}$, stop the algorithm and define $f_k=f_{m-1}=f$ for $k\ge m$.

- If $f\ne f_{m-1}$, choose an element ${\phi }_m\in \mathcal{D}$ such that

$|⟨f-f_{m-1},{\phi }_m⟩|=\underset{\phi \in \mathcal{D}}{sup}|⟨f-f_{m-1},\phi ⟩|.$

Define the next approximant to be

$f_m=P_m\left(f\right),$

and proceed to Step $m+1$, where $P_m$ is the orthogonal projection onto $V_m:=\mathrm{span}\{{\phi }_1,{\phi }_2,···,{\phi }_m\}$

In [15], it is shown that for any $\mathcal{D}$, the output of the OGA(H, $\mathcal{D}$) satisfies

$\parallel f-f_m{\parallel \le c\parallel f\parallel }_{{\mathcal{A}}_1\left(\mathcal{D}\right)}{m}^{-\frac{1}{2}},m=1,2,\cdots .$

Note that when $\mathcal{D}$ is an ortho-normal basis of H, the OGA(H, $\mathcal{D}$) coincides with the PGA(H, $\mathcal{D}$). So, the rate $\mathcal{O}\left(m^{-\frac{1}{2}}\right)$ is sharp.

The Relaxed Greedy Algorithm (RGA) is also a modification of PGA. We recall its definition from [15].

• RGA(H, $\mathcal{D}$):

•Step 0: Define $f_0=0$.

•Step m:

- If $f=f_{m-1}$, stop the algorithm and define $f_k=f_{m-1}=f$ for $k\ge m$.

- If $f\ne f_{m-1}$, choose an element ${\phi }_m\in \mathcal{D}$ such that

$\left|⟨f-f_{m-1},{\phi }_m⟩\right|=\underset{\phi \in \mathcal{D}}{sup}\left|⟨f-f_{m-1},\phi ⟩\right|.$

For $m=1$, define

$f_1=⟨f,{\phi }_1⟩{\phi }_1.$

For $m\ge 2$, define the next approximant to be

$f_m=\left(1-\frac{1}{m}\right)f_{m-1}+\frac{1}{m}{\phi }_m,$

and proceed to Step $m+1$.

It is shown in [15] that the RGA also achieves the rate $O\left(m^{-\frac{1}{2}}\right)$ on ${\mathcal{A}}_1\left(\mathcal{D}\right)$.

The Rescaled Pure Greedy Algorithm (RPGA) [17] is another kind of greedy algorithm which makes a modification to the rescaling process to replace the original output of the PGA with $f_m=s_m\widehat{f_m}$ at each iteration. It is defined as follows.

• RPGA(H, $\mathcal{D})$:

•Step 0: Define $f_0=0$.

•Step m:

- If $f=f_{m-1}$, stop the algorithm and define $f_k=f_{m-1}=f$ for $k\ge m$.

- If $f\ne f_{m-1}$, choose an element ${\phi }_m\in \mathcal{D}$ such that

$|⟨f-f_{m-1},{\phi }_m⟩|=\underset{\phi \in \mathcal{D}}{sup}\left|⟨f-f_{m-1},\phi ⟩\right|.$

With

${\lambda }_m=⟨f-f_{m-1},{\phi }_m⟩,{\widehat{f}}_m:=f_{m-1}+{\lambda }_m{\phi }_m,s_m=\frac{⟨f,{\widehat{f}}_m⟩}{\parallel {\widehat{f}}_m{\parallel }^2},$

define the next approximant to be

$f_m=s_m{\widehat{f}}_m,$

and proceed to Step $m+1$.

In [17], the convergence rate of the RPGA was obtained as follows:

$\parallel f-f_m{\parallel \le \parallel f\parallel }_{{\mathcal{A}}_1\left(\mathcal{D}\right)}{(m+1)}^{-\frac{1}{2}},m=0,1,2,\cdots .$

It is worth noting that the supremum of the inner product might not be attainable. To remedy this problem, the original condition on the selection of ${\phi }_m$ is replaced by

${\displaystyle |⟨f-f_{m-1},{\phi }_m⟩|\ge t_m\underset{\phi \in \mathcal{D}}{sup}\left|⟨f-f_{m-1},\phi ⟩\right|,}$

where $0<t_m\le 1$. This is often referred to as the “weak” condition. The study on the weak version of the above algorithms can be found in [15,25,29,30].

Meanwhile, building simultaneous approximations for a given vector of elements brings about the so-called vector-type greedy algorithms. Instead of running the algorithm for a finite collection of elements $f^1,\dots ,f^N$ each time separately, the vector greedy algorithm manages to obtain a simultaneous approximation of all elements with a single run. Hence, the complexity of calculation and the storage of information can be reduced greatly. Now, it comes to the question of how well this type of algorithm can perform. Namely, we need to measure its efficiency via its error bound. The Vector Weak Pure Greedy Algorithm (VWPGA, which is also referred to as the Vector Weak Greedy Algorithm (VWGA)) and the Vector Weak Orthogonal Greedy Algorithm (VWOGA) have been introduced and studied in [21,22,23].

We recall the definitions of the VWPGA and VWOGA from [23] as follows. Let $\tau ={\left\{t_m\right\}}_{m=1}^{\infty }$ and $0<t_m\le 1$ be a given sequence.

• VWPGA(H, $\mathcal{D}$): $f^i\in H,i=1,\dots ,N$ is the target element.

•Step 0: Define $f_0^i:=0,i=1,\dots N$.

•Step m:

- If $f^i=f_{m-1}^i$, stop the algorithm and define $f_k^i=f_{m-1}^i=f$ for $k\ge m$.

- If $f\ne f_{m-1}$, choose an element ${\phi }_m\in \mathcal{D}$ such that

${\displaystyle \underset{i}{max}|⟨f^i-f_{m-1}^i,{\phi }_m⟩|\ge t_m\underset{i}{max}\underset{\phi \in \mathcal{D}}{sup}\left|⟨f^i-f_{m-1}^i,\phi ⟩\right|.}$

Define the next approximant to be

$f_m^i:=f_{m-1}^i+⟨f^i-f_{m-1}^i,{\phi }_m⟩{\phi }_m,i=1,2,\dots ,N,$

and proceed to Step $m+1$.

• VWOGA(H, $\mathcal{D}$): $f^i\in H,i=1,\dots ,N$ is the target element.

•Step 0: Define $f_0^i:=0,i=1,\dots N$.

•Step m:

- If $f^i=f_{m-1}^i$, stop the algorithm and define $f_k^i=f_{m-1}^i=f$ for $k\ge m$.

- If $f^i\ne f_{m-1}^i$. Let $i_m$ be such that

$\parallel f^{i_m}-f_{m-1}^{i_m}\parallel \ge \parallel f^i-f_{m-1}^i\parallel ,i=1,\dots N.$

Choose an element ${\phi }_m\in \mathcal{D}$ such that

${\displaystyle |⟨f^{i_m}-f_{m-1}^{i_m},{\phi }_m⟩|\ge t_m\underset{\phi \in \mathcal{D}}{sup}\left|⟨f^{i_m}-f_{m-1}^{i_m},\phi ⟩\right|.}$

Define the next approximant to be

$f_m^i=P_m\left(f^i\right),i=1,2,\dots ,N,$

and proceed to Step $m+1$, where $P_m$ is the orthogonal projection onto $V_m$ := span{${\phi }_1,{\phi }_2,···,{\phi }_m$}.

We list the results on the convergence rate of the VWPGA and VWOGA in [23] as follows.

Theorem 1.

Let $\tau :={\left\{t_k\right\}}_{k=1}^{\infty },t_k=t,0<t\le 1$ be a given real sequence. Then, for any $f^1,\dots ,f^N,f^i\in A_1\left(\mathcal{D}\right)$, the output ${\left\{f_m^i\right\}}_{m\ge 0}$ of the VWPGA satisfies

${\displaystyle \sum _{i=1}^N{\parallel f^i-f_m^i\parallel }^2\le {\left(1+\frac{m{t}^2}{N}\right)}^{-t/(2N+t)}{N}^{\frac{2N+2t}{2N+t}}}.$

Theorem 2.

Let $\tau :={\left\{t_k\right\}}_{k=1}^{\infty },t_k=t,0<t\le 1$ be a given real sequence. Then, for any $f^i\in A_1\left(\mathcal{D}\right)$, the output ${\left\{f_m^i\right\}}_{m\ge 0}$ of the VWOGA satisfies

$\parallel f^i-f_m^i\parallel \le min\left\{1,{\left(\frac{N}{m{t}^2}\right)}^{1/2}\right\},i=1,\dots ,N.$

Improvements to the above estimates are made in [19,21,22]. The results indicate that the VWOGA achieves a better convergence rate on $A_1\left(\mathcal{D}\right)$ than that of the VWPGA.

In [23], the authors gave a sufficient condition of convergence for the VWPGA.

Theorem 3.

Assume that ${\displaystyle \sum _{m=1}^{\infty }\frac{t_m}{m}=\infty }$. Then, for any dictionary and any finite elements $f^i\in H,i=1,\dots ,N$, the VWPGA satisfies

${\displaystyle \underset{m\to \infty }{lim}\parallel f^i-f_m^i\parallel =0.}$

Motivated by these studies, we design the Vector Weak Rescaled Pure Greedy Algorithm (VWRPGA) and study its efficiency. The remainder of the paper is organized as follows. In Section 2, we deal with the case of Hilbert spaces. In Section 3, we deal with the case of Banach spaces. In Section 4, we draw the conclusions. Below, we provide more details.

In Section 2, we define the VWRPGA in Hilbert spaces and study its approximation properties. We first prove that

$\sum _{m=1}^{\infty }{t}_m^2=\infty$

is the sufficient convergence condition of the VWRPGA for any $f^i\in H$ and $\mathcal{D}\subset H$, $i=1,\cdots ,N$. This convergence condition is weaker than that of the VWPGA. Then, we prove that the error bound of the VWRPGA on $A_1\left(\mathcal{D}\right)$ satisfies

$\parallel f^i-f_m^{i,v,\tau ,r}\parallel \le min\left\{1,{\left({\displaystyle \frac{1}{N}\sum _{k=1}^m{t}_k^2}\right)}^{-\frac{1}{2}}\right\}.$

When $t_1=t_2=\cdots =t_m=1$, we show that convergence rate of the VWRPGA on ${\mathcal{A}}_1\left(\mathcal{D}\right)$ is $O\left(m^{-\frac{1}{2}}\right)$, which is sharp. This convergence rate is better than that of the VWPGA. In particular, this advantage is more obvious when N is large. The VWRPGA is more efficient than VWOGA from the viewpoint of computational complexity. This is because, for N target elements, the VWRPGA only needs to solve N one-dimensional optimization problems, while the VWOGA involves N m-dimensional optimization problems.

In Section 3, we define the VWRPGA for some uniformly smooth Banach spaces. The sufficient condition of the convergence of the VWRPGA is obtained in this case. It seems that this is the first result on the convergence analysis of the vector greedy algorithms in the Banach space setting. Then, we derive the error bound of the VWRPGA. The results show that the convergence rate of the VWRPGA on ${\mathcal{A}}_1\left(\mathcal{D}\right)$ is sharp. We compare the approximation properties of the VWRPGA with those of the Vector Weak Chebyshev Greedy Algorithm (VWCGA) and the Vector Weak Relaxed Greedy Algorithm (VWRGA). We show that the VWRPGA has better convergence properties than the VWRGA. Similarly, the computational complexity of the VWRPGA is essentially smaller than those of the VWCGA and VWRGA.

In Section 4, we draw the conclusions of our study. Our results show that the VWRPGA is the simplest vector greedy algorithm for simultaneous approximation with the best convergence property and the optimal convergence rate. We also discuss the possible applications of the VWRPGA in multi-task learning and signal vector processing.

2. The VWRPGA for Hilbert Spaces

In this section, we define the VWRPGA in Hilbert spaces and obtain its sufficient condition of convergence together with an estimate of its error bound. Based on these results, we compare the VWRPGA with the VWPGA and the VWOGA.

Firstly, we recall the definition of the Weak Rescaled Pure Greedy Algorithm (WRPGA) in Hilbert spaces from [17]. Let $\tau ={\left\{t_m\right\}}_{m=1}^{\infty }$, $0<t_m\le 1$ be a given sequence. The WRPGA consists of the following stages:

• WRPGA(H, $\mathcal{D}$):

•Step 0: Define $f_0=0$.

•Step m:

- If $f=f_{m-1}$, stop the algorithm and define $f_k=f_{m-1}=f$ for $k\ge m$.

- If $f\ne f_{m-1}$, choose an element ${\phi }_m\in \mathcal{D}$ such that

${\displaystyle |⟨f-f_{m-1},{\phi }_m⟩|\ge t_m\underset{\phi \in \mathcal{D}}{sup}\left|⟨f-f_{m-1},\phi ⟩\right|.}$

With

${\lambda }_m=⟨f-f_{m-1},{\phi }_m⟩,\widehat{f_m}:=f_{m-1}+{\lambda }_m{\phi }_m,s_m=\frac{⟨f,\widehat{f_m}⟩}{\parallel \widehat{f_m}{\parallel }^2},$

define the next approximation to be

$f_m=s_m\widehat{f_m},$

and proceed to Step $m+1$.

The error bound of the WRPGA has been obtained as follows.

Theorem 4

(see Theorem 4.1 in [17]). If $f\in {\mathcal{A}}_1\left(\mathcal{D}\right)\subset H$, then the output ${\left\{f_m\right\}}_{m\ge 0}$ of the WRPGA satisfies the error estimate

$\parallel f-f_m{\parallel \le \parallel f\parallel }_{{\mathcal{A}}_1\left(\mathcal{D}\right)}{\left({\displaystyle \sum _{k=1}^m{t}_k^2}\right)}^{-\frac{1}{2}}.$

Based on the WRPGA, we can define the VWRPGA. Let $\tau ={\left\{t_m\right\}}_{m=1}^{\infty }$, $0<t_m\le 1$ be a given sequence. Now, we define the VWRPGA using the following steps:

• VWRPGA(H, $\mathcal{D}$): Given $f^i\in H,i=1,\dots ,N.$

•Step 0: Define $f_0^{i,v,\tau ,r}:=0,i=1,\dots N$.

•Step m:

- If $f^i=f_{m-1}^{i,v,\tau ,r}$, stop the algorithm and define $f_k^{i,v,\tau ,r}=f_{m-1}^{i,v,\tau ,r}=f$ for $k\ge m$.

- If $f^i\ne f_{m-1}^{i,v,\tau ,r}$, let $i_m$ be such that

${\displaystyle \parallel f^{i_m}-f_{m-1}^{i_m,v,\tau ,r}\parallel =\underset{1\le i\le N}{max}\parallel f^i-f_{m-1}^{i,v,\tau ,r}\parallel .}$

Choose an element ${\phi }_m\in \mathcal{D}$ such that

${\displaystyle ⟨f^{i_m}-f_{m-1}^{i_m,v,\tau ,r},{\phi }_m⟩\ge t_m\underset{\phi \in \mathcal{D}}{sup}⟨f^{i_m}-f_{m-1}^{i_m,v,\tau ,r},\phi ⟩.}$

With

${\lambda }_m^i=⟨f^i-f_{m-1}^{i,v,\tau ,r},{\phi }_m⟩,\widehat{f_m^i}:=f_{m-1}^{i,v,\tau ,r}+{\lambda }_m^i{\phi }_m,s_m^i=\frac{⟨f^i,\widehat{f_m^i}⟩}{\parallel \widehat{f_m^i}{\parallel }^2},$

define the next approximation to be

$f_m^{i,v,\tau ,r}:=s_m^i\widehat{f_m^i},$

and proceed to Step $m+1$.

We establish in this section two typical results on the approximation properties of the VWRPGA (H, $\mathcal{D}$). We first give the sufficient condition for the convergence of the VWRPGA for any dictionary $\mathcal{D}$ and any $f^i$, $i=1,\cdots ,N.$

Theorem 5.

Assume ${\displaystyle \sum _{m=1}^{\infty }{t}_m^2=\infty }$. Then, the VWRPGA converges for any dictionary $\mathcal{D}$ and any $f^i\in H,i=1,\dots ,N.$

In the proof of Theorem 5, we will reduce the approximation of the general element to that of the element from $A_1\left(\mathcal{D}\right)$. To this end, we recall from [31] the following lemmas on the approximation properties of $A_1\left(\mathcal{D}\right)$.

Lemma 1.

Let X be a Banach space and $\mathcal{D}\subset X$ be a dictionary. Then, for any $ϵ>0$ and any $f\in X$, there exists $f^{ϵ}\in X$ such that

$\parallel f-f^{ϵ}\parallel <ϵ$

and

$\frac{f^{ϵ}}{A\left(ϵ\right)}\in A_1\left(\mathcal{D}\right),$

with some number $A\left(ϵ\right)>0$.

Lemma 2.

For any $f\in H$ and any dictionary $\mathcal{D}$, we have

${\displaystyle \underset{\phi \in \mathcal{D}}{sup}⟨f,\phi ⟩=\underset{g\in A_1\left(\mathcal{D}\right)}{sup}⟨f,g⟩.}$

Proof of Theorem 5.

Note that $f_m^{i,v,\tau ,r}$ is the orthogonal projection of $f^i$ onto the one-dimensional space $\mathrm{span}\left\{\widehat{f_m^i}\right\}$. Thus, it is the best approximation of $f_m^{i,v,\tau ,r}$ from $\mathrm{span}\left\{\widehat{f_m^i}\right\}$.

Let $r_m^i:=\parallel f^i-f_m^{i,v,\tau ,r}\parallel ,i=1,\cdots ,N$, be the residual of $f_m^{i,v,\tau ,r}$. By the definition of $\widehat{f_m^i}$ and the choice of ${\lambda }_m^i$, we have

(2)$\begin{array}{cc}\hfill \parallel r_m^i{\parallel }^2& =\parallel f^i-f_m^{i,v,\tau ,r}{\parallel }^2\hfill \\ \hfill & =\parallel f^i-s_m^i\widehat{f_m^i}{\parallel }^2\hfill \\ \hfill & \le \parallel f^i-\widehat{f_m^i}{\parallel }^2\hfill \\ \hfill & \le ⟨f^i-f_{m-1}^{i,v,\tau ,r}-{\lambda }_m^i{\phi }_m,f^i-f_{m-1}^{i,v,\tau ,r}-{\lambda }_m^i{\phi }_m⟩\hfill \\ \hfill & =\parallel f^i-f_{m-1}^{i,v,\tau ,r}{\parallel }^2-2{\lambda }_m^i⟨f^i-f_{m-1}^{i,v,\tau ,r},{\phi }_m⟩+{\left({\lambda }_m^i\right)}^2\hfill \\ \hfill & =\parallel r_{m-1}^i{\parallel }^2-{⟨f^i-f_{m-1}^{i,v,\tau ,r},{\phi }_m⟩}^2.\hfill \end{array}$

The latter inequality implies that $\{\parallel r_m^i{\parallel \}}_{m=0}^{\infty }$ is a decreasing sequence. According to the Monotone Convergence Theorem, we know that ${\displaystyle \underset{m\to \infty }{lim}\parallel r_m^i\parallel }$ exists, $i=1,\dots ,N$.

We prove that ${\displaystyle \underset{m\to \infty }{lim}\parallel r_m^i\parallel =0}$ by contradiction. Assume ${\displaystyle \underset{m\to \infty }{lim}\parallel r_m^i\parallel \ge a>0}$, $i=1,\dots ,N$. Then, for any m, we have $\parallel r_m^i\parallel \ge a$. By (2), we obtain that

$\begin{array}{cc}\hfill {\displaystyle \sum _{i=1}^N{\parallel r_m^i\parallel }^2}& {\displaystyle \le \sum _{i=1}^N{\parallel r_{m-1}^i\parallel }^2-\sum _{i=1}^N{⟨f^i-f_{m-1}^{i,v,\tau ,r},{\phi }_m⟩}^2}\hfill \\ \hfill & {\displaystyle =\sum _{i=1}^N{\parallel r_{m-1}^i\parallel }^2\left(1-\frac{{\displaystyle \sum _{i=1}^N{⟨f^i-f_{m-1}^{i,v,\tau ,r},{\phi }_m⟩}^2}}{{\displaystyle \sum _{i=1}^N{\parallel r_{m-1}^i\parallel }^2}}\right)}\hfill \\ \hfill & {\displaystyle \le \sum _{i=1}^N{\parallel r_{m-1}^i\parallel }^2\left(1-\frac{{⟨f^{i_m}-f_{m-1}^{i_m,v,\tau ,r},{\phi }_m⟩}^2}{N\parallel r_{m-1}^{i_m}{\parallel }^2}\right)}\hfill \\ \hfill & {\displaystyle \le \sum _{i=1}^N{\parallel f^i\parallel }^2\prod _{j=1}^m\left(1-\frac{{⟨f^{i_j}-f_{j-1}^{i_j,v,\tau ,r},{\phi }_j⟩}^2}{N\parallel r_{j-1}^{i_j}{\parallel }^2}\right).}\hfill \end{array}$

Denote

$x_j=\frac{{⟨f^{i_j}-f_{j-1}^{i_j,v,\tau ,r},{\phi }_j⟩}^2}{N\parallel r_{j-1}^{i_j}{\parallel }^2}.$

By the inequality $1-x\le \frac{1}{1+x},0\le x\le 1$, we obtain that

(3)$\begin{array}{cc}\hfill {\displaystyle \sum _{i=1}^N{\parallel r_m^i\parallel }^2}& {\displaystyle \le \sum _{i=1}^N{\parallel f^i\parallel }^2\prod _{j=1}^m\left(\frac{1}{1+x_j}\right)}\hfill \\ \hfill & {\displaystyle \le \sum _{i=1}^N{\parallel f^i\parallel }^2\frac{1}{{\displaystyle 1+\sum _{j=1}^m{x}_j}}.}\hfill \end{array}$

Then, we come to obtain a lower estimate for $x_j,j=1,\dots ,m$.

Set $ϵ=\frac{a}{2}$. In view of Lemma 1, we can find $f_j^{ϵ}$ such that

$\parallel f^{i_j}-f_j^{ϵ}\parallel <ϵ$

and

$\frac{f_j^{ϵ}}{A\left(ϵ\right)}\in A_1\left(\mathcal{D}\right),$

with some number $A\left(ϵ\right)>0$.

Using Lemma 2, we have

(4)$\begin{array}{cc}\hfill ⟨f^{i_j}-f_{j-1}^{i_j,v,\tau ,r},{\phi }_j⟩& {\displaystyle \ge t_j\underset{\phi \in \mathcal{D}}{sup}⟨f^{i_j}-f_{j-1}^{i_j,v,\tau ,r},\phi ⟩}\hfill \\ \hfill & {\displaystyle =t_j\underset{g\in A_1\left(\mathcal{D}\right)}{sup}⟨f^{i_j}-f_{j-1}^{i_j,v,\tau ,r},g⟩}\hfill \\ \hfill & \ge t_{j}A{\left(ϵ\right)}^{-1}⟨f^{i_j}-f_{j-1}^{i_j,v,\tau ,r},f_j^{ϵ}⟩.\hfill \end{array}$

Since $f_m^{i,v,\tau ,r}$ is the orthogonal projection of $f^i$ onto $\mathrm{span}\left\{\widehat{f_m^i}\right\}$, we have

$⟨f^i-f_m^{i,v,\tau ,r},f_m^{i,v,\tau ,r}⟩=0.$

Then,

(5)$\begin{array}{cc}\hfill ⟨f^{i_j}-f_{j-1}^{i_j,v,\tau ,r},f_j^{ϵ}⟩& =⟨r_{j-1}^{i_j},f^{i_j}+f_j^{ϵ}-f^{i_j}⟩\hfill \\ \hfill & =⟨r_{j-1}^{i_j},r_{j-1}^{i_j}+f_{j-1}^{i_j,v,\tau ,r}⟩-⟨r_{j-1}^{i_j},f^{i_j}-f_j^{ϵ}⟩\hfill \\ \hfill & >\parallel r_{j-1}^{i_j}{\parallel }^2-\parallel r_{j-1}^{i_j}\parallel ·ϵ.\hfill \end{array}$

Combining (4) and (5) with $ϵ=\frac{a}{2}$, we obtain

(6)$\begin{array}{ccc}\hfill x_j& \ge & \frac{1}{N\parallel r_{j-1}^{i_j}{\parallel }^2}·{\left(\frac{⟨f^{i_j}-f_{j-1}^{i_j,v,\tau ,r},f_j^{ϵ}⟩}{A\left(ϵ\right)}{t}_j\right)}^2\hfill \\ \hfill & \ge & \frac{1}{N}·{\left(\frac{\parallel r_{j-1}^{i_j}\parallel -ϵ}{A\left(ϵ\right)}{t}_j\right)}^2\hfill \\ & \ge & \frac{a^2}{4NA{\left(ϵ\right)}^2}{t}_j^2.\hfill \end{array}$

Combining (3) with (6), we can obtain that

${\displaystyle \sum _{i=1}^N\parallel r_m^i{\parallel }^2\le \sum _{i=1}^N{\parallel f^i\parallel }^2\frac{1}{{\displaystyle 1+{\displaystyle \frac{a^2}{4NA{\left(ϵ\right)}^2}}\sum _{j=1}^m{t}_j^2}}.}$

The assumption ${\displaystyle \sum _{m=1}^{\infty }{t}_m^2=\infty }$ implies that ${\displaystyle \sum _{i=1}^N{\parallel r_m^i\parallel }^2\to 0}$ as $m\to \infty$.

It is obvious that ${\displaystyle \underset{m\to \infty }{lim}\parallel r_m^i\parallel =0}$ for $i=1,\dots ,N$. Hence, we obtain a contradiction, which proves this theorem. □

Remark 1.

It is known from Theorem 2.1 in [32] that ${\displaystyle \sum _{m=1}^{\infty }{t}_m^2=\infty }$ is also the necessary condition for the convergence of the VWRPGA.

Remark 2.

According to the Cauchy–Schwartz inequality, we know that

$\sum _{m=1}^{\infty }\frac{t_m}{m}\le {\left(\sum _{m=1}^{\infty }{t}_m^2\right)}^{\frac{1}{2}}{\left(\sum _{m=1}^{\infty }\frac{1}{m^2}\right)}^{\frac{1}{2}}.$

Hence,

$\sum _{m=1}^{\infty }\frac{t_m}{m}=\infty \mathrm{implies}\sum _{m=1}^{\infty }{t}_m^2=\infty .$

On the other hand, taking $t_m=m^{-\frac{1}{2}}$, $m=1,2,···,$ we notice that

$\sum _{m=1}^{\infty }{t}_m^2=\infty ,\sum _{m=1}^{\infty }\frac{t_m}{m}<\infty .$

Therefore, the convergence condition of the VWPRGA is weaker than that of the VWPGA.

The following theorem gives the error bound of the VWRPGA ($H,\mathcal{D}$) for $f^i\in A_1\left(\mathcal{D}\right),i=1,\dots ,N$.

Theorem 6.

Let $\tau :={\left\{t_k\right\}}_{k=1}^{\infty },0<t_k\le 1$ be a weakness sequence. If $f^i\in A_1\left(\mathcal{D}\right)\subset H,i=1,\dots ,N$. Then, we have for the VWRPGA ($H,\mathcal{D}$)

$\parallel f^i-f_m^{i,v,\tau ,r}\parallel \le min\left\{1,{\left({\displaystyle \frac{1}{N}\sum _{k=1}^m{t}_k^2}\right)}^{-\frac{1}{2}}\right\}.$

Proof. 

We establish the approximation error of the VWRPGA based on the methods of [25]. The main idea of this proof is that the VWRPGA can be seen as a realization of the WRPGA with a particular weakness sequence.

Let $i\in \{1,\dots ,N\}$. Under the assumption that $f^i\in A_1\left(\mathcal{D}\right)$ and the fact that the sequence $\{\parallel f^i-f_m^{i,v,\tau ,r}{\parallel \}}_{m=0}^{\infty }$ is decreasing, we have

$\parallel f^i-f_m^{i,v,\tau ,r}\parallel \le 1.$

Thus, we only need to prove the estimate below:

$\parallel f^i-f_m^{i,v,\tau ,r}\parallel \le {\left({\displaystyle \frac{1}{N}\sum _{k=1}^m{t}_k^2}\right)}^{-\frac{1}{2}},i=1,\dots ,N.$

At step k, the VWRPGA chooses ${\phi }_k$ from the $\mathcal{D}$ in terms of only one remainder from $\{r_{k-1}^1,\dots ,r_{k-1}^N\}$. Then, each $f^i,i=1,\cdots ,N$ has been used different times to choose ${\phi }_k$ when the VWRPGA carries on to step m. Now, we record the usage of $f^i,i=1,\dots ,N$.

For every $l,l=1,\dots ,N$, denote $E_l:=\left\{k\right|i_k=l,1\le k\le m$} ( $i_k$ is defined in the definition of VWRPGA). Then, we have

$E_1\cup E_2\cup \dots \cup E_N=\{1,\dots ,m\},E_i\cap E_j=\varnothing \mathrm{if}i\ne j.$

Hence,

${\displaystyle \parallel f^l-f_{k-1}^{l,v,\tau ,r}\parallel =\parallel f^{i_k}-f_{k-1}^{i_k,v,\tau ,r}\parallel =\underset{1\le i\le N}{max}\parallel f^i-f_{k-1}^{i,v,\tau ,r}\parallel ,k\in E_l.}$

Using ${\displaystyle \sum _{k=1}^m{t}_k^2=\sum _{l=1}^N\sum _{k\in E_l}{t}_k^2,}$ we can find $l_0\in [1,N]$ such that

${\displaystyle \sum _{k\in E_{l_0}}{t}_k^2\ge \frac{1}{N}\sum _{k=1}^m{t}_k^2.}$

Next, let $k_0=max\left\{k\right|k\in E_{l_0}\},k_0\le m$. We have

(7)$\begin{array}{c}\hfill {\displaystyle \underset{1\le i\le N}{max}\parallel f^i-f_m^{i,v,\tau ,r}\parallel \le \underset{1\le i\le N}{max}\parallel f^i-f_{k_0-1}^{i,v,\tau ,r}\parallel =\parallel f^{l_0}-f_{k_0-1}^{l_0,v,\tau ,r}\parallel .}\end{array}$

Now, we only consider element $f^{l_0}\in H$. For $f^{l_0}\in H$, we can obtain $f_1^{l_0,v,\tau ,r},\dots ,f_m^{l_0,v,\tau ,r}$ as an application of the WRPGA with the weakness sequence ${\tau }^{l_0}:=\left\{t_k^{l_0}\right\}$ given by

$\begin{array}{c}\hfill t_k^{l_0}=\left\{\begin{array}{cc}{t}_k,\hfill & k\in E_{l_0}\hfill \\ 0,\hfill & \mathrm{otherwise}.\hfill \end{array}\right.\end{array}$

Therefore, by Theorem 4, we obtain

$\begin{array}{cc}\hfill \parallel f^{l_0}-f_{k_0-1}^{l_0,v,\tau ,r}\parallel & \le {\left({\displaystyle 1+\sum _{k\in E_{l_0}-\left\{k_0\right\}}{t}_k^2}\right)}^{-\frac{1}{2}}\hfill \\ \hfill & \le {\left({\displaystyle 1+\sum _{k\in E_{l_0}}{t}_k^2-1}\right)}^{-\frac{1}{2}}\hfill \\ \hfill & \le {\left({\displaystyle \frac{1}{N}\sum _{k=1}^m{t}_k^2}\right)}^{-\frac{1}{2}}.\hfill \end{array}$

Together with (7), we complete the proof of Theorem 6. □

We recall the theorem in [21] about the error estimate of the VWPGA.

Theorem 7.

Let $\tau :={\left\{t_k\right\}}_{k=1}^{\infty },0<t_k\le 1$ be a decreasing sequence. Then, for any $f^1,\dots ,f^N,f^i\in A_1\left(\mathcal{D}\right)$, the output ${\left\{f_m^i\right\}}_{m\ge 0}$ of the VWPGA satisfies

${\displaystyle \sum _{i=1}^N{\parallel f^i-f_m^i\parallel }^2\le N^2{\left({\displaystyle 1+\frac{1}{N}\sum _{i=1}^m{t_k}^2}\right)}^{\frac{-t_m}{2N^{1/2}+t_m}}.}$

We observe from Theorem 7, for a fixed m, the error of the VWPGA increases as the number of the target elements increases. The exponent is close to zero as long as N is sufficiently large.

Taking $t_k=1,k=1,2,\dots$ in Theorem 7, we yield the following theorem, which gives the convergence rate of the VWPGA.

Theorem 8.

Let $\tau :={\left\{t_k\right\}}_{k=1}^{\infty }$, $t_k=1$. Then, for any $f^1,\dots ,f^N,f^i\in A_1\left(\mathcal{D}\right)$, the output ${\left\{f_m^i\right\}}_{m\ge 0}$ of the VWPGA satisfies

${\displaystyle \sum _{i=1}^N\parallel f^i-f_m^i\parallel \le N^2{\left(1+\frac{m}{N}\right)}^{-\frac{1}{2N^{1/2}+1}}.}$

Again, by taking $t_k=1,k=1,2,\dots$ in Theorem 6, we obtain the following theorem.

Theorem 9.

Let $\tau :={\left\{t_k\right\}}_{k=1}^{\infty },$$t_k=1$. If $f^i\in A_1\left(\mathcal{D}\right)\subset H,i=1,\dots ,N$. Then, for the VWRPGA ($H,\mathcal{D}$),

$\parallel f^i-f_m^{i,v,\tau ,r}\parallel \le min\left\{1,{\left(\frac{m}{N}\right)}^{-\frac{1}{2}}\right\}.$

Remark 3.

From Theorems 8 and 9, we see that the VWRPGA provides a significantly better convergence rate than the VWPGA. In particular, this advantage is more obvious when N is large.

Remark 4.

It is known from Theorems 2 and 9 that the approximation property of the VWRPGA is almost the same as that of the VWOGA. While the VWRPGA is simpler than the VWOGA from the viewpoint of computational complexity. For N target elements, from the definitions of the algorithms, one can see that the VWOGA needs to solve N m-dimensional optimization problems. However, the VWRPGA only needs to solve N one-dimensional optimization problems. Then, this makes the VWRPGA easier to implement than the VWOGA in practical applications.

3. The VWRPGA for Banach Spaces

In this section, we consider the VWRPGA in the context of Banach spaces. We remark that there are two natural generations of the PGA in the case of Banach space X: the X-greedy algorithm and the dual greedy algorithm. However, there are no general results on convergence and error bound of these two algorithms, cf. [29]. On the other hand, the WOGA, WRGA, WRPGA and VWOGA have been successfully generalized to the case of Banach spaces. We first recall from [31] the definition of the Weak Chebyshev Greedy Algorithm (WCGA), which is a natural generalization of the WOGA.

For any non-zero element $f\in X$, we denote by $F_f$ a norming functional for f:

$\parallel F_f\parallel =1,F_f\left(f\right)=\parallel f\parallel .$

The existence of such a functional is guaranteed by the Hahn–Banach theorem. Let $\tau ={\left\{t_m\right\}}_{m=1}^{\infty }$, $0<t_m\le 1$ be a given sequence. The WCGA is defined as follows.

• WCGA(X, $\mathcal{D}$):

•Step 0: Define $f_0=0$.

•Step m:

- If $f=f_{m-1}$, stop the algorithm and define $f_k=f_{m-1}=f$ for $k\ge m$.

- If $f\ne f_{m-1}$, choose an element ${\phi }_m\in \mathcal{D}$ such that

$F_{f-f_{m-1}}\left({\phi }_m\right)\ge t_m\underset{\phi \in \mathcal{D}}{sup}{F}_{f-f_{m-1}}\left(\phi \right).$

Set

${\Phi }_m:=\mathrm{span}\{{\phi }_1,{\phi }_2,···,{\phi }_m\}.$

Define $f_m$ to be the best approximant to f from ${\Phi }_m$ and proceed to Step $m+1$.

To estimate the error of WCGA, we shall utilize some geometric aspects of Banach spaces. For a Banach space X, we define $\rho \left(u\right)$, the modulus of smoothness of X, as

${\displaystyle \rho \left(u\right):=\underset{f,g\in X,\parallel f\parallel =\parallel g\parallel =1}{sup}\left\{\frac{\parallel f+ug\parallel +\parallel f-ug\parallel }{2}-1\right\},u>0.}$

A uniformly smooth Banach space is one with the property

${\displaystyle \underset{u\to 0}{lim}\frac{\rho \left(u\right)}{u}=0.}$

We shall only consider Banach spaces whose modulus of smoothness satisfies the inequality

$\rho \left(u\right)\le \gamma u^q,1<q\le 2,$

where $\gamma$ is a constant independent of u.

A typical example of a uniformly smooth Banach space is the Lebesgue space $L_p$, $1<p<\infty$. It is known from [33] that

(8)$\rho \left(u\right)\le \left\{\begin{array}{cc}{u}^p/p\hfill & if1<p\le 2,\hfill \\ (p-1)u^2/2\hfill & if2\le p<\infty .\hfill \end{array}\right.$

Moreover, we obtain from [34] that for any X with $dimX=\infty$,

$\rho \left(u\right)\ge {(1+u^2)}^{\frac{1}{2}}-1$

and for any X with $dimX\ge 2$,

$\rho \left(u\right)\ge C{u}^2,C>0.$

The following error bound of the WCGA on $A_1\left(\mathcal{D}\right)$ has been established in [31].

Theorem 10.

Let X be a Banach space with modulus of smoothness $\rho \left(u\right)\le \gamma u^q,1<q\le 2$. If $f\in A_1\left(\mathcal{D}\right)\subset X$, then the output ${\left\{f_m\right\}}_{m\ge 0}$ of the WCGA($X,\mathcal{D}$) satisfies the inequality

$\parallel f-f_m\parallel \le C_1(q,\gamma ){\left({\displaystyle 1+\sum _{k=1}^m{t}_k^{\frac{q}{q-1}}}\right)}^{-1+\frac{1}{q}},$

where the constant $C_1(q,\gamma )$ depends only on q and γ.

Taking ${\left\{t_k\right\}}_{k=1}^{\infty },t_k=1,k=1,2,\cdots$, Theorem 10 implies the following corollary, which can be seen in [31].

Corollary 1.

Let X be a Banach space with modulus of smoothness $\rho \left(u\right)\le \gamma u^q,1<q\le 2$. Then, for any $f\in A_1\left(\mathcal{D}\right)$, the output ${\left\{f_m\right\}}_{m\ge 0}$ of the WCGA(X, $\mathcal{D}$) satisfies the inequality

$\parallel f-f_m\parallel \le c·m^{-1+\frac{1}{q}}.$

In order to show the convergence rate $O\left(m^{-1+\frac{1}{q}}\right)$ cannot be improved, we now take $L_p,1<p<\infty$ as an example.

Let $1<p\le 2$ be fixed. Combining Corollary 1 with inequality (8), we have for any $\mathcal{D}\subset L_p$ and any $f\in L_p$

(9)$\parallel f-f_m\parallel \le c·m^{-1+\frac{1}{p}}.$

When $\mathcal{D}$ is a wavelet basis of $L_p$, it is known from [35] that there is a $f\in A_1\left(\mathcal{D}\right)$ such that

$\parallel f-f_m\parallel \ge c·m^{-1+\frac{1}{p}}.$

Thus, inequality (9) could not be improved.

Similarly, let $p>2$ be fixed. Combining Corollary 1 with inequality (8), we have for any $\mathcal{D}\subset L_p$ and any $f\in L_p$

(10)$\parallel f-f_m\parallel \le c·m^{-\frac{1}{2}}.$

When $\mathcal{D}$ is the trigonometric system of $L_p$, it is known from [36] that there is a $f\in A_1\left(\mathcal{D}\right)$ such that

$\parallel f-f_m\parallel \ge c·m^{-\frac{1}{2}}.$

Thus, inequality (10) could not be improved.

Then, the convergence rate $O\left(m^{-1+\frac{1}{q}}\right)$ in Corollary 1 serves as a benchmark for the performance of greedy algorithms in uniformly smooth Banach spaces.

Next, we recall the definition of the WRGA in the Banach space setting from [31]. Let $\tau ={\left\{t_m\right\}}_{m=1}^{\infty }$, $0<t_m\le 1$, be a given sequence. The WRGA is defined as follows.

• WRGA(X, $\mathcal{D}$):

•Step 0: Define $f_0=0$.

•Step m:

- If $f=f_{m-1}$, stop the algorithm and define $f_k=f_{m-1}=f$ for $k\ge m$.

- If $f\ne f_{m-1}$, choose a element ${\phi }_m\in \mathcal{D}$ such that

$F_{f-f_{m-1}}({\phi }_m-f_{m-1})\ge t_m\underset{\phi \in \mathcal{D}}{sup}{F}_{f-f_{m-1}}(\phi -f_{m-1}).$

Find $0\le {\lambda }_m\le 1$ such that

$\parallel f-((1-{\lambda }_m)f_{m-1}+{\lambda }_m{\phi }_m)\parallel =\underset{0\le \lambda \ge 1}{inf}\parallel f-((1-\lambda )f_{m-1}+\lambda {\phi }_m)\parallel .$

Define $f_m:=(1-{\lambda }_m)f_{m-1}+{\lambda }_m{\phi }_m,$ and proceed to Step $m+1$.

The following error bound of the WRGA on $A_1\left(\mathcal{D}\right)$ has been established in [31].

Theorem 11.

Let X be a Banach space with a modulus of smoothness $\rho \left(u\right)\le \gamma u^q,1<q\le 2$. If $f\in A_1\left(\mathcal{D}\right)\subset X$, then the output ${\left\{f_m\right\}}_{m\ge 0}$ of the WRGA ($X,\mathcal{D}$) satisfies the inequality

$\parallel f-f_m\parallel \le C_2(q,\gamma ){\left({\displaystyle 1+\sum _{k=1}^m{t}_k^p}\right)}^{-\frac{1}{p}},p=\frac{q}{q-1},$

where the constant $C_2(q,\gamma )$ depends only on q and γ.

Now, we turn to the vector greedy algorithms. Let $\tau ={\left\{t_m\right\}}_{m=1}^{\infty }$, $0<t_m\le 1$ be a given sequence. The Vector Weak Chebyshev Greedy Algorithm (VWCGA) [22] is defined as follows.

• VWCGA(X, $\mathcal{D}$):

•Step 0: Define $f_0^{i,v,\tau ,c}:=0,i=1,\dots N$.

•Step m:

- If $f^i=f_{m-1}^{i,v,\tau ,c}$, stop the algorithm and define $f_k^{i,v,\tau ,c}=f_{m-1}^{i,v,\tau ,c}=f$ for $k\ge m$.

- If $f^i\ne f_{m-1}^{i,v,\tau ,c}$, let $i_m$ be such that

${\displaystyle \parallel f^{i_m}-f_{m-1}^{i_m,v,\tau ,c}\parallel =\underset{1\le i\le N}{max}\parallel f^i-f_{m-1}^{i,v,\tau ,c}\parallel .}$

Choose an element ${\phi }_m\in \mathcal{D}$ such that

${\displaystyle F_{f^{i_m}-f_{m-1}^{i_m,v,\tau ,c}}\left({\phi }_m\right)\ge t_m\underset{\phi \in \mathcal{D}}{sup}{F}_{f^{i_m}-f_{m-1}^{i_m,v,\tau ,c}}\left(\phi \right).}$

Set

${\Phi }_m:=\mathrm{span}\{{\phi }_1,{\phi }_2,···,{\phi }_m\}.$

Define $f_m^i$ to be the best approximant to $f^i$ from ${\Phi }_m$, $i=1,···,N$ and proceed to Step $m+1$.

Let $\tau ={\left\{t_m\right\}}_{m=1}^{\infty }$, $0<t_m\le 1$ be a given sequence. The Vector Weak Relaxed Greedy Algorithm (VWRGA) [22] is defined as follows.

• VWRGA(X, $\mathcal{D}$):

•Step 0: Define $f_0^{i,v,\tau ,c}:=0,i=1,\dots N$.

•Step m:

- If $f^i=f_{m-1}^{i,v,\tau ,r}$, stop the algorithm and define $f_k^{i,v,\tau ,r}=f_{m-1}^{i,v,\tau ,r}=f$ for $k\ge m$.

- If $f^i\ne f_{m-1}^{i,v,\tau ,r}$, let $i_m$ be such that

${\displaystyle \parallel f^{i_m}-f_{m-1}^{i_m,v,\tau ,r}\parallel =\underset{1\le i\le N}{max}\parallel f^i-f_{m-1}^{i,v,\tau ,r}\parallel .}$

Choose an element ${\phi }_m\in \mathcal{D}$ such that

${\displaystyle F_{f^{i_m}-f_{m-1}^{i_m,v,\tau ,r}}\left({\phi }_m\right)\ge t_m\underset{\phi \in \mathcal{D}}{sup}{F}_{f^{i_m}-f_{m-1}^{i_m,v,\tau ,r}}\left(\phi \right).}$

Find $0\le {\lambda }_m^i\le 1$ such that

$\parallel f^i-((1-{\lambda }_m^i)f_{m-1}^{i_m,v,\tau ,r}+{\lambda }_m^i{\phi }_m)\parallel =\underset{0\le \lambda \ge 1}{inf}\parallel f^i-((1-\lambda )f_{m-1}^{i_m,v,\tau ,r}+\lambda {\phi }_m)\parallel .$

Define $f_m^{i,v,\tau ,r}:=(1-{\lambda }_m^i)f_{m-1}^{i,v,\tau ,r}+{\lambda }_m^i{\phi }_m,$ and proceed to Step $m+1$.

The error bounds of the VWCGA and VWRGA on $A_1\left(\mathcal{D}\right)$ have been established in [22].

Theorem 12.

Let X be a Banach space with a modulus of smoothness $\rho \left(u\right)\le \gamma u^q,1<q\le 2$. Then, for a sequence $\tau :={\left\{t_k\right\}}_{k=1}^{\infty },0<t_k\le 1$ and any $f^i\in A_1\left(\mathcal{D}\right)\subset X,i=1,\dots ,N$, we have

$\parallel f^i-f_m^{i,v,\tau ,c}\parallel \le C_1(q,\gamma )min\left\{1,{\left({\displaystyle \frac{1}{N}\sum _{k=1}^m{t}_k^p}\right)}^{-\frac{1}{p}}\right\},p=\frac{q}{q-1},$

$\parallel f^i-f_m^{i,v,\tau ,r}\parallel \le C_2(q,\gamma )min\left\{1,{\left({\displaystyle \frac{1}{N}\sum _{k=1}^m{t}_k^p}\right)}^{-\frac{1}{p}}\right\},p=\frac{q}{q-1}.$

Now, we start to define the VWRPGA (X, $\mathcal{D}$). To accomplish this, we recall the definition of the WRPGA from [17]. Let X be a Banach space with a modulus of smoothness $\rho \left(u\right)\le \gamma u^q,1<q\le 2$. Let $\tau ={\left\{t_m\right\}}_{m=1}^{\infty }$, $0<t_m\le 1$ be a given sequence.

• WRPGA(X, $\mathcal{D}$):

•Step 0: Define $f_0=0$.

•Step m:

- If $f=f_{m-1}$, stop the algorithm and define $f_k=f_{m-1}=f$ for $k\ge m$.

- If $f\ne f_{m-1}$, choose an element ${\phi }_m\in \mathcal{D}$ such that

$|F_{f-f_{m-1}}\left({\phi }_m\right)|\ge t_m\underset{\phi \in \mathcal{D}}{sup}{F}_{f-f_{m-1}}\left(\phi \right).$

With

${\lambda }_m=\mathrm{sign}\left\{F_{f-f_{m-1}}\left({\phi }_m\right)\right\}\parallel f-f_{m-1}\parallel {\left(2\gamma q\right)}^{\frac{1}{1-q}}{\left|F_{f-f_{m-1}}\left({\phi }_m\right)\right|}^{\frac{1}{q-1}},$

${\widehat{f}}_m:=f_{m-1}+{\lambda }_m{\phi }_m,$

choose $s_m$ such that

$\parallel f-s_m{\widehat{f}}_m\parallel =\underset{s\in \mathbb{R}}{min}\parallel f-s{\widehat{f}}_m\parallel .$

Define the next approximant to be $f_m=s_m{\widehat{f}}_m,$ and proceed to Step $m+1$.

The sufficient conditions for the convergence of the WRPGA in terms of the weakness sequence and the modulus of smoothness can be found in [17]. Moreover, the following theorem gives the error bound of the WRPGA on $A_1\left(\mathcal{D}\right)$.

Theorem 13

(see Theorem 6.1 in [17]). Let X be a Banach space with modulus of smoothness $\rho \left(u\right)\le \gamma u^q,1<q\le 2$. If $f\in A_1\left(\mathcal{D}\right)\subset X$, then the output ${\left\{f_m\right\}}_{m\ge 0}$ of the WRPGA($X,\mathcal{D}$) satisfies the inequality

$\parallel f-f_m\parallel \le C_3(q,\gamma ){\left({\displaystyle 1+\sum _{k=1}^m{t}_k^p}\right)}^{-\frac{1}{p}},p=\frac{q}{q-1},$

where the constant $C_3(q,\gamma )$ depends only on q and γ.

Let X be a Banach space with modulus of smoothness $\rho \left(u\right)\le \gamma u^q,1<q\le 2$. Let $\tau ={\left\{t_m\right\}}_{m=1}^{\infty }$, $0<t_m\le 1$ be a given sequence. We define the VWRPGA (X, $\mathcal{D}$) as follows.

• VWRPGA(X, $\mathcal{D}$): Given $f^i\in X,i=1,\dots ,N.$

•Step 0: Define $f_0^{i,v,\tau ,R}:=0,i=1,\dots N$.

•Step m:

- If $f^i=f_{m-1}^{i,v,\tau ,R}$, stop the algorithm and define $f_k^{i,v,\tau ,R}=f_{m-1}^{i,v,\tau ,R}=f$ for $k\ge m$.

- If $f^i\ne f_{m-1}^{i,v,\tau ,R}$, let $i_m$ be such that

${\displaystyle \parallel f^{i_m}-f_{m-1}^{i_m,v,\tau ,R}\parallel =\underset{1\le i\le N}{max}\parallel f^i-f_{m-1}^{i,v,\tau ,R}\parallel .}$

Choose an element ${\phi }_m\in \mathcal{D}$ such that

${\displaystyle F_{f^{i_m}-f_{m-1}^{i_m,v,\tau ,R}}\left({\phi }_m\right)\ge t_m\underset{\phi \in \mathcal{D}}{sup}{F}_{f^{i_m}-f_{m-1}^{i_m,v,\tau ,R}}\left(\phi \right).}$

With

${\lambda }_m^i=\mathrm{sign}\left\{F_{f^i-f_{m-1}^{i,v,\tau ,R}}\left({\phi }_m\right)\right\}\parallel f^i-f_{m-1}^{i,v,\tau ,R}\parallel {\left(2\gamma q\right)}^{\frac{1}{1-q}}{\left|F_{f^i-f_{m-1}^{i,v,\tau ,R}}\left({\phi }_m\right)\right|}^{\frac{1}{q-1}},$

$\widehat{f_m^i}:=f_{m-1}^{i,v,\tau ,R}+{\lambda }_m^i{\phi }_m,$

choose $s_m$ such that

${\displaystyle \parallel f^i-s_m^i\widehat{f_m^i}\parallel =\underset{s\in \mathbb{R}}{min}\parallel f^i-s\widehat{f_m^i}\parallel .}$

Define the next approximant to be $f_m^{i,v,\tau ,R}=s_m^i\widehat{f_m^i},$ and proceed to Step $m+1$.

In this section, we obtain the convergence properties and error bound of the VWRPGA.

Firstly, we establish the theorem on the convergence of the VWRPGA. It seems that this theorem is the first result on the convergence property of the vector greedy algorithms in the Banach space setting.

Theorem 14.

Let X be a Banach space with modulus of smoothness $\rho \left(u\right)\le \gamma u^q,1<q\le 2$. Assume

${\displaystyle \sum _{m=1}^{\infty }{t}_m^p=\infty ,p=\frac{q}{q-1}.}$

Then, for any $f^i\in X,i=1,\dots ,N$ and any dictionary $\mathcal{D}$ the VWRPGA converges.

The idea of the proof of Theorem 14 is similar to that of Theorem 5. However, because of the complexity of Banach spaces, a series of arguments in the subsequence analysis must be modified, replaced, and generalized. Some useful results in the case of Hilbert spaces have been generalized to the case of Banach spaces, as shown in the following lemmas.

Lemma 3.

Let X be a Banach space with modulus of smoothness $\rho \left(u\right)\le \gamma u^q,1<q\le 2$. For any two nonzero elements $f,g\in X$ and any $h>0$, we have

$\parallel f-hg\parallel \le \parallel f\parallel +2\parallel f\parallel \gamma ·{\left(\frac{h\parallel g\parallel }{\parallel f\parallel }\right)}^q-h{F}_f\left(g\right).$

Proof. 

The proof of this lemma follows from the proof of Lemma 6.1 in [29] and the fact that the modulus of smoothness of X satisfies $\rho \left(u\right)\le \gamma u^q,1<q\le 2.$ □

Lemma 4.

Let X be a Banach space with modulus of smoothness $\rho \left(u\right)\le \gamma u^q,1<q\le 2$. Let $f_{m-1}^{i,v,\tau ,R}$ be the output of the VWRPGA at Step $m-1$ for $f^i,i=1,\dots ,N$. If $f^i\ne f_{m-1}^{i,v,\tau ,R}$, then we have

$F_{f^i-f_{m-1}^{i,v,\tau ,R}}\left(f_{m-1}^{i,v,\tau ,R}\right)=0.$

Proof. 

Denote $L:=\mathrm{span}\left\{\widehat{f_m^i}\right\}\subset X$. By the definition of the VWRPGA$(X,\mathcal{D}),f_{m-1}^{i,v,\tau ,R}$ is the best approximant to $f^i$ from L for $i=1,\dots ,N$. Thus, the conclusion of the lemma follows from Lemma 2.1 in [31]. □

Lemma 5

(see Lemma 2.2 in [31]). For any bounded linear functional F and any dictionary $\mathcal{D}$ from a Banach space, we have

${\displaystyle \underset{\phi \in \mathcal{D}}{sup}F\left(\phi \right)=\underset{g\in A_1\left(\mathcal{D}\right)}{sup}F\left(g\right).}$

Now, we prove Theorem 14.

Proof of Theorem 14.

Let $r_m^i,i=1,\cdots ,N$ be the residual of $f_m^{i,v,\tau ,R}$. It is known from the definition of the VWRPGA$(X,D)$ that $r_m^i$ satisfies

$\begin{array}{cc}\hfill \parallel r_m^i\parallel & =\parallel f^i-f_m^{i,v,\tau ,R}\parallel \hfill \\ \hfill & =\parallel f^i-s_m^i\widehat{f_m^i}\parallel \hfill \\ \hfill & \le \parallel f^i-\widehat{f_m^i}\parallel \hfill \\ \hfill & =\parallel r_{m-1}^i-{\lambda }_m^i{\phi }_m\parallel .\hfill \end{array}$

We apply Lemma 3 to the latter inequality with $f=r_{m-1}^i,g=\mathrm{sign}\left({\lambda }_m^i\right){\phi }_m,h=\left|{\lambda }_m^i\right|,$ and obtain

$\parallel r_m^i\parallel \le \parallel r_{m-1}^i\parallel +2\parallel r_{m-1}^i\parallel \gamma ·{\left(\frac{|{\lambda }_m^i|}{\parallel r_{m-1}^i\parallel }\right)}^q-{\lambda }_m^i{F}_{f^i-f_{m-1}^{i,v,\tau ,R}}\left({\phi }_m\right).$

By the choice of ${\lambda }_m^i$, we have

(11)$\begin{array}{c}\hfill \parallel r_m^i\parallel \le \parallel r_{m-1}^i\parallel \left\{1-\frac{q-1}{q}{\left(2\gamma q\right)}^{\frac{1}{1-q}}·{\left|F_{f^i-f_{m-1}^{i,v,\tau ,R}}\left({\phi }_m\right)\right|}^{\frac{q}{q-1}}\right\}.\end{array}$

Thus, it is easy to see that $\{\parallel r_m^i{\parallel \}}_{m=0}^{\infty }$ is a decreasing sequence. According to the Monotone Convergence Theorem, we know that ${\displaystyle \underset{m\to \infty }{lim}\parallel r_m^i\parallel }$ for $i=1,\dots ,N$ exists.

Next, we prove that ${\displaystyle \underset{m\to \infty }{lim}\parallel r_m^i\parallel =0}$ by contradiction. Assume ${\displaystyle \underset{m\to \infty }{lim}\parallel r_m^i\parallel \ge a>0,i=1,\dots ,N}$. Then, for any m, we have $\parallel r_m^i\parallel \ge a$. By (11), we obtain that

$\begin{array}{cc}\hfill {\displaystyle \sum _{i=1}^N\parallel r_m^i\parallel }& {\displaystyle \le \sum _{i=1}^N\parallel r_{m-1}^i\parallel -\frac{q-1}{q}{\left(2\gamma q\right)}^{\frac{1}{1-q}}·\sum _{i=1}^N\parallel r_{m-1}^i\parallel ·|F_{f^i-f_{m-1}^{i,v,\tau ,R}}\left({\phi }_m\right){|}^{\frac{q}{q-1}}}\hfill \\ \hfill & {\displaystyle \le \sum _{i=1}^N\parallel r_{m-1}^i\parallel \left\{1-\frac{q-1}{q}{\left(2\gamma q\right)}^{\frac{1}{1-q}}·\frac{\parallel r_{m-1}^{i_m}\parallel ·{\left(F_{f^{i_m}-f_{m-1}^{i_m,v,R,\tau }}\left({\phi }_m\right)\right)}^{\frac{q}{q-1}}}{{\displaystyle \sum _{i=1}^N\parallel r_{m-1}^i\parallel }}\right\}}\hfill \\ \hfill & {\displaystyle \le \sum _{i=1}^N\parallel r_{m-1}^i\parallel \left\{1-\frac{q-1}{q}{\left(2\gamma q\right)}^{\frac{1}{1-q}}·\frac{\parallel r_{m-1}^{i_m}\parallel ·{\left(F_{f^{i_m}-f_{m-1}^{i_m,v,R,\tau }}\left({\phi }_m\right)\right)}^{\frac{q}{q-1}}}{N\parallel r_{m-1}^{i_m}\parallel }\right\}}\hfill \\ \hfill & {\displaystyle \le \sum _{i=1}^N\parallel f^i\parallel \prod _{j=1}^m\left\{1-\frac{1}{N}·\frac{q-1}{q}{\left(2\gamma q\right)}^{\frac{1}{1-q}}·{\left(F_{f^{i_j}-f_{j-1}^{i_j,v,R,\tau }}\left({\phi }_j\right)\right)}^{\frac{q}{q-1}}\right\}.}\hfill \end{array}$

Denote

(12)$x_j=\frac{1}{N}·\frac{q-1}{q}{\left(2\gamma q\right)}^{\frac{1}{1-q}}·{\left(F_{f^{i_j}-f_{j-1}^{i_j,v,R,\tau }}\left({\phi }_j\right)\right)}^{\frac{q}{q-1}}).$

By the inequality $1-x\le \frac{1}{1+x},0\le x\le 1$, we obtain

(13)$\begin{array}{cc}\hfill {\displaystyle \sum _{i=1}^N\parallel r_m^i\parallel }& {\displaystyle \le \sum _{i=1}^N\parallel f^i\parallel \prod _{j=1}^m\frac{1}{1+x_j}}\hfill \\ \hfill & {\displaystyle \le \sum _{i=1}^N\parallel f^i\parallel \frac{1}{{\displaystyle 1+\sum _{j=1}^m{x}_j}}.}\hfill \end{array}$

Then, we proceed with a lower estimate for $x_j,j=1,\dots ,m$.

By Lemma 1, we set $ϵ=\frac{a}{2}$ and find $f_j^{ϵ}$ such that

$\parallel f^{i_j}-f_j^{ϵ}\parallel <ϵ$

and

$\frac{f_j^{ϵ}}{A\left(ϵ\right)}\in A_1\left(\mathcal{D}\right),$

with some number $A\left(ϵ\right)>0$.

We obtain from Lemma 5 that

(14)$\begin{array}{cc}\hfill F_{f^{i_j}-f_{j-1}^{i_j,v,R,\tau }}\left({\phi }_j\right)& {\displaystyle \ge t_j\underset{\phi \in \mathcal{D}}{sup}{F}_{f^{i_j}-f_{j-1}^{i_j,v,R,\tau }}\left(\phi \right)}\hfill \\ \hfill & {\displaystyle =t_j\underset{g\in A_1\left(\mathcal{D}\right)}{sup}{F}_{f^{i_j}-f_{j-1}^{i_j,v,R,\tau }}\left(g\right)}\hfill \\ \hfill & \ge t_{j}A{\left(ϵ\right)}^{-1}{F}_{f^{i_j}-f_{j-1}^{i_j,v,R,\tau }}\left(f_j^{ϵ}\right).\hfill \end{array}$

By Lemma 4, we obtain

(15)$\begin{array}{cc}\hfill F_{f^{i_j}-f_{j-1}^{i_j,v,R,\tau }}\left(f_j^{ϵ}\right)& =F_{f^{i_j}-f_{j-1}^{i_j,v,R,\tau }}(f^{i_j}-(f^{i_j}-f_j^{ϵ}))\hfill \\ \hfill & =F_{f^{i_j}-f_{j-1}^{i_j,v,R,\tau }}\left(f^{i_j}\right)-F_{f^{i_j}-f_{j-1}^{i_j,v,R,\tau }}(f^{i_j}-f_j^{ϵ})\hfill \\ \hfill & >F_{f^{i_j}-f_{j-1}^{i_j,v,R,\tau }}(f^{i_j}-f_{j-1}^{i_j,v,R,\tau }+f_{j-1}^{i_j,v,R,\tau })-ϵ\hfill \\ \hfill & =F_{f^{i_j}-f_{j-1}^{i_j,v,R,\tau }}(f^{i_j}-f_{j-1}^{i_j,v,R,\tau })-ϵ\hfill \\ \hfill & =\parallel r_{j-1}^{i_j}\parallel -ϵ.\hfill \end{array}$

Inequalities (14), (15) and $ϵ=\frac{a}{2}$ result in

(16)$\begin{array}{ccc}\hfill F_{f^{i_j}-f_{j-1}^{i_j,v,R,\tau }}\left({\phi }_j\right)& \ge & t_{j}A{\left(ϵ\right)}^{-1}(\parallel r_{j-1}^{i_j}\parallel -ϵ)\hfill \\ & \ge & t_{j}A{\left(ϵ\right)}^{-1}·\frac{a}{2}.\hfill \end{array}$

Combining (12) with (16), we obtain

(17)$\begin{array}{cc}\hfill x_j& \ge \frac{1}{N}·\frac{q-1}{q}{\left(2\gamma q\right)}^{\frac{1}{1-q}}·{\left(t_{j}A{\left(ϵ\right)}^{-1}·\frac{a}{2}\right)}^{\frac{q}{q-1}}\hfill \\ \hfill & =\frac{1}{N}·\frac{q-1}{q}{\left(2\gamma q\right)}^{\frac{1}{1-q}}·{\left(\frac{a}{2A\left(ϵ\right)}\right)}^p·t_j^p.\hfill \end{array}$

Combining (17) with (13), we have

${\displaystyle \sum _{i=1}^N\parallel r_m^i\parallel \le \sum _{i=1}^N\parallel f^i\parallel ·\frac{1}{{\displaystyle 1+{\displaystyle \frac{1}{N}}·{\displaystyle \frac{q-1}{q}}{\left(2\gamma q\right)}^{\frac{1}{1-q}}·{\left({\displaystyle \frac{a}{2A\left(ϵ\right)}}\right)}^p\sum _{j=1}^m{t}_j^p}}.}$

The assumption ${\displaystyle \sum _{m=1}^{\infty }{t}_m^p=\infty }$ implies that ${\displaystyle \sum _{i=1}^N\parallel r_m^i\parallel \to 0}$ as $m\to \infty$.

Thus, ${\displaystyle \underset{m\to \infty }{lim}\parallel r_m^i\parallel =0}$ for $1=1,\dots ,N.$ We obtain a contradiction which proves this theorem. □

Remark 5.

According to Theorem 3.1 in [32], we know that ${\displaystyle \sum _{m=1}^{\infty }{t}_m^p=\infty }$ is also a necessary condition for the convergence of the VWRPGA.

Remark 6.

Since the WRGA only converges for the target elements from ${\mathcal{A}}_1\left(\mathcal{D}\right)$, see [31], then the VWRGA also only converges for the target elements from ${\mathcal{A}}_1\left(\mathcal{D}\right)$. Thus, the convergence property of the VWRPGA is better than that of the VWRGA.

Remark 7.

For $f^i\in A_1\left(\mathcal{D}\right),i=1,\dots ,N$, the sufficient condition for the convergence of the VWCGA follows from Theorem 12. Theorem 15 gives the convergence condition for any $f^i\in X,i=1,\dots ,N$.

By using the same method, it is not difficult to prove the following theorem on the convergence of the VWCGA.

Theorem 15.

Let X be a Banach space with modulus of smoothness $\rho \left(u\right)\le \gamma u^q,1<q\le 2$. Assume

${\displaystyle \sum _{m=1}^{\infty }{t}_m^p=\infty ,p=\frac{q}{q-1}.}$

Then, for any $f^i\in X,i=1,\dots ,N$ and any dictionary $\mathcal{D}$ the VWCGA converges.

Next, we give the theorem about the error bound of the VWRPGA($X,\mathcal{D}$) on $A_1\left(\mathcal{D}\right)$.

Theorem 16.

Let X be a Banach space with modulus of smoothness $\rho \left(u\right)\le \gamma u^q,1<q\le 2$. Then, for a sequence $\tau :={\left\{t_k\right\}}_{k=1}^{\infty },0<t_k\le 1$ and any $f^i\in A_1\left(\mathcal{D}\right)\subset X,i=1,\dots ,N$, we have

$\parallel f^i-f_m^{i,v,\tau ,R}\parallel \le C_3(q,\gamma )min\left\{1,{\left({\displaystyle \frac{1}{N}\sum _{k=1}^m{t}_k^p}\right)}^{-\frac{1}{p}}\right\},p=\frac{q}{q-1}.$

Proof. 

It is known from (11) that the sequences $\{\parallel f^i-f_m^{i,v,\tau ,R}{\parallel \}}_{m=0}^{\infty },i=1,\cdots ,N$ are decreasing. Fix i. The inequality

$\parallel f^i-f_m^{i,v,\tau ,R}\parallel \le 1$

follows from the assumption $f^i\in A_1\left(\mathcal{D}\right)$ and the fact that $\{\parallel f^i-f_m^{i,v,\tau ,R}{\parallel \}}_{m=0}^{\infty }$ is decreasing.

Thus, we only need to prove the following estimate:

$\parallel f^i-f_m^{i,v,\tau ,R}\parallel \le C(q,\gamma ){\left({\displaystyle \frac{1}{N}\sum _{k=1}^m{t}_k^p}\right)}^{-\frac{1}{p}},i=1,\dots ,N.$

We define the set $E_l:=\left\{k\right|i_k=l,1\le k\le m\}$ just as we did in proof of Theorem 6. It is obvious that

${\displaystyle \sum _{k=1}^m{t}_k^p=\sum _{l=1}^N\sum _{k\in E_l}{t}_k^p.}$

Thus, there exists $l_0\in [1,N]$ such that

${\displaystyle \sum _{k\in E_{l_0}}{t}_k^p\ge \frac{1}{N}\sum _{k=1}^m{t}_k^p.}$

As in proof of Theorem 6, for $f^{l_0}\in X$, the sequences $f_1^{l_0,v,R,\tau },\dots ,f_m^{l_0,v,R,\tau }$ are the outputs of the WRPGA with the weakness sequence ${\tau }^{l_0}:=\left\{t_k^{l_0}\right\}$. Therefore, using Theorem 13, we obtain

$\begin{array}{cc}\hfill \parallel f^{l_0}-f_{k_0-1}^{l_0,v,R,\tau }\parallel & \le C(q,\gamma ){\left({\displaystyle 1+\sum _{k\in E_{l_0}-\left\{k_0\right\}}{t}_k^p}\right)}^{-\frac{1}{p}}\hfill \\ \hfill & \le C(q,\gamma ){\left({\displaystyle 1+\sum _{k\in E_{l_0}}{t}_k^p-1}\right)}^{-\frac{1}{p}}\hfill \\ \hfill & \le C(q,\gamma ){\left({\displaystyle \frac{1}{N}\sum _{k=1}^m{t}_k^p}\right)}^{-\frac{1}{p}}.\hfill \end{array}$

The proof of Theorem 16 is completed. □

Remark 8.

We know from Theorems 12 and 16 that the error bound of the VWRPGA is almost the same as those of the VWCGA and VWRGA. Similarly, the computational complexity of the VWRPGA is essentially smaller than those of the VWCGA and VWRGA.

4. Conclusions

In this paper, we consider the use of vector greedy algorithms for simultaneous approximation. We first work in a Hilbert space H. We propose a new vector greedy algorithm—the Vector Weak Rescaled Pure Greedy Algorithm (VWRPGA)—for simultaneous approximation with respect to a dictionary $\mathcal{D}$ in H. Then, we study the error performances of the VWRPGA. We show that the convergence rate of the VWRPGA on ${\mathcal{A}}_1\left(\mathcal{D}\right)$ is optimal. The VWRPGA has a weaker convergence condition than the VWPGA. The convergence rate of the VWRPGA is better than that of the VWPGA. In particular, this advantage is more obvious when N is large. Moreover, the error performances of the VWRPGA are similar to those of the VWOGA. However, from the viewpoint of computational complexity, the VWRPGA is simpler than the VWOGA. For N target elements, from the definitions of the algorithms, one can see that the VWOGA needs to solve N m-dimensional optimization problems. However, the VWRPGA only needs to solve N one-dimensional optimization problems.

Then, we design the Vector Weak Rescaled Pure Greedy Algorithm (VWRPGA) in a uniformly smooth Banach space setting. We obtain the convergence properties and error bound of the VWRPGA in this case. We also show that the convergence condition of the VWCGA is the same as that of the VWRPGA. We show that when the Banach space is a Lebesgue space, the convergence rate of the VWRPGA on ${\mathcal{A}}_1\left(\mathcal{D}\right)$ is sharp. As for the convergence properties, the VWRGA converges only for the target elements from ${\mathcal{A}}_1\left(\mathcal{D}\right)$, while the VWRPGA converges for any element. Therefore, the VWRPGA has better convergence properties than the VWRGA. The error bounds of the VWRPGA are similar to those of the VWCGA and VWRGA. From the viewpoint of computational complexity, the VWRPGA is simpler than the VWCGA and the VWRGA.

In conclusion, the VWRPGA is the simplest vector greedy algorithm for simultaneous approximation with the best convergence property and the optimal convergence rate.

The VWRGA is more efficient than the WRPGA, since the complexity of its calculation and the storage of information can be reduced greatly by the VWRPGA instead of the N-fold WRPGA. If $\tau :={\left\{t_k\right\}}_{k=1}^{\infty },t_k=1,k=1,2,\cdots$ and $N=1$, then the VWRPGA degenerates into the RPGA. In [5], the authors applied the RPGA to a kernel-based regression. They defined the Rescaled Pure Greedy Learning Algorithm (RPGLA) and studied its efficiency. They showed that the computational complexity of the RPGLA is less than the Orthogonal Greedy Learning Algorithm (OGLA) [37] and Relaxed Greedy Learning Algorithm (RGLA) [38]. When the kernel is infinitely smooth, the learning rate can be arbitrarily close to the best rate $O\left(m^{-1}\right)$ under a mild assumption of the regression function. Since the VWRPGA is more efficient than the RPGA, the VWRPGA can be used to solve the problems of multi-task learning more efficiently. Moreover, it is natural to consider the applications of the VWRPGA to vector signal processing. We will study these applications of the VWRPGA in the future.

Author Contributions

Conceptualization, X.X., P.Y. and W.Z.; methodology, X.X. and P.Y.; formal analysis, J.G.; investigation, all authors; resources, all authors; data curation, all authors; writing—original draft preparation, P.Y. and J.G.; writing—review and editing, X.X. and P.Y.; visualization, all authors; supervision, X.X. and P.Y.; project administration, all authors; funding acquisition, all authors. All authors have read and agreed to the published version of the manuscript.

Data Availability Statement

Not applicable.

Conflicts of Interest

The authors declare no conflict of interest.

Footnotes

Disclaimer/Publisher’s Note: The statements, opinions and data contained in all publications are solely those of the individual author(s) and contributor(s) and not of MDPI and/or the editor(s). MDPI and/or the editor(s) disclaim responsibility for any injury to people or property resulting from any ideas, methods, instructions or products referred to in the content.

References

1. Barron, A.; Cohen, A.; Dahmen, W.; DeVore, R. Approximation and learning by greedy algorithms. Ann. Stat.; 2008; 36, pp. 64-94. [DOI: https://dx.doi.org/10.1214/009053607000000631]

2. Cohen, A.; Dahmen, W.; DeVore, R. Compressed sensing and best k-term approximation. J. Am. Math. Soc.; 2009; 22, pp. 211-231. [DOI: https://dx.doi.org/10.1090/S0894-0347-08-00610-3]

3. Yang, B.; Yang, C.; Huang, G. Efficient image fusion with approximate sparse representation. Int. J. Wavelets Multiresolut. Inf. Process.; 2016; 14, 1650024.

4. Zhang, W.H.; Ye, P.X.; Xing, S.; Xu, X. Optimality of the approximation and learning by the rescaled pure super greedy algorithms. Axioms; 2022; 11, 437. [DOI: https://dx.doi.org/10.3390/axioms11090437]

5. Zhang, W.H.; Ye, P.X.; Xing, S. Optimality of the rescaled pure greedy learning algorithms. Int. J. Wavelets Multiresolut. Inf. Process.; 2023; 21, 2250048. [DOI: https://dx.doi.org/10.1142/S0219691322500485]

6. Nguyen, H.; Petrova, G. Greedy strategies for convex optimization. Calcolo; 2017; 54, pp. 207-224. [DOI: https://dx.doi.org/10.1007/s10092-016-0183-2]

7. Huang, A.T.; Feng, R.Z.; Wang, A.D. The sufficient conditions for orthogonal matching pursuit to exactly reconstruct sparse polynomials. Mathematics; 2022; 10, 3703. [DOI: https://dx.doi.org/10.3390/math10193703]

8. Liu, Z.Y.; Xu, Q.Y. A multiscale RBF collocation method for the numerical solution of partial differential equations. Mathematics; 2019; 7, 964. [DOI: https://dx.doi.org/10.3390/math7100964]

9. Jin, D.F.; Yang, G.; Li, Z.H.; Liu, H.D. Sparse recovery algorithm for compressed sensing using smoothed l₀ norm and randomized coordinate descent. Mathematics; 2019; 7, 834. [DOI: https://dx.doi.org/10.3390/math7090834]

10. Natsiou, A.A.; Gravvanis, G.A.; Filelis-Papadopoulos, C.K.; Giannoutakis, K.M. An aggregation-based algebraic multigrid method with deflation techniques and modified generic factored approximate sparse inverses. Mathematics; 2023; 11, 640. [DOI: https://dx.doi.org/10.3390/math11030640]

11. Argyriou, A.; Evgeniou, T.; Pontil, M. Convex multitask feature learning. Mach. Learn.; 2008; 73, pp. 243-272. [DOI: https://dx.doi.org/10.1007/s10994-007-5040-8]

12. Schmidt, E. Zur Theorie der linearen und nichtlinearen Integralgleichungen. I Math. Annalen.; 1906–1907; 63, pp. 433-476. [DOI: https://dx.doi.org/10.1007/BF01449770]

13. Tropp, J.A.; Gilbert, A.C.; Strauss, M.J. Algorithms for simultaneous sparse approximation. Part I: Greedy pursuit. Signal. Process.; 2006; 86, pp. 572-588. [DOI: https://dx.doi.org/10.1016/j.sigpro.2005.05.030]

14. Wirtz, D.; Haasdonk, B. A vectorial kernel orthogonal greedy algorithm. Proc. DWCAA; 2013; 6, pp. 83-100.

15. DeVore, R.A.; Temlyakov, V.N. Some remarks on greedy algorithms. Adv. Comput. Math.; 1996; 5, pp. 173-187. [DOI: https://dx.doi.org/10.1007/BF02124742]

16. Gao, Z.; Petrova, G. Rescaled pure greedy algorithm for convex optimization. Calcolo; 2019; 56, 15. [DOI: https://dx.doi.org/10.1007/s10092-019-0311-x]

17. Petrova, G. Rescaled pure greedy algorithm for Hilbert and Banach spaces. Appl. Comput. Harmon. Anal.; 2016; 41, pp. 852-866. [DOI: https://dx.doi.org/10.1016/j.acha.2015.10.008]

18. Jiang, B.; Ye, P.; Zhang, W. Unified error estimate for weak biorthogonal greedy algorithms. Int. J. Wavelets Multiresolut. Inform. Process.; 2022; 5, 2150001. [DOI: https://dx.doi.org/10.1142/S0219691322500102]

19. Dereventsov, A.V.; Temlyakov, V.N. A unified way of analyzing some greedy algorithms. J. Funct. Anal.; 2019; 12, pp. 1-30. [DOI: https://dx.doi.org/10.1016/j.jfa.2019.108286]

20. Temlyakov, V.N. A remark on simultaneous greedy approximation. East J. Approx.; 2004; 10, pp. 17-25.

21. Leviatan, D.; Temlyakov, V.N. Simultaneous approximation by greedy algorithms. Adv. Comput. Math.; 2006; 25, pp. 73-90. [DOI: https://dx.doi.org/10.1007/s10444-004-7613-4]

22. Leviatan, D.; Temlyakov, V.N. Simultaneous greedy approximation in Banach spaces. J. Complex.; 2005; 21, pp. 275-293. [DOI: https://dx.doi.org/10.1016/j.jco.2004.09.004]

23. Lutoborski, A.; Temlyakov, V.N. Vector greedy algorithms. J. Complex.; 2003; 19, pp. 458-473. [DOI: https://dx.doi.org/10.1016/S0885-064X(03)00026-8]

24. Mallat, S.; Zhang, Z. Matching pursuit with time-frequency dictionaries. IEEE Trans. Signal Pross.; 1993; 41, pp. 3397-3415. [DOI: https://dx.doi.org/10.1109/78.258082]

25. Konyagin, S.V.; Temlyakov, V.N. Rate of convergence of pure greedy algorithm. East. J. Approx.; 1996; 5, pp. 493-499.

26. Sil^′nichenko, A.V. Rates of convergence of greedy algorithms. Mat. Zametki.; 2004; 76, pp. 628-632.

27. Burusheva, L.; Temlyakov, V. Sparse approximation of individual functions. J. Approx. Theory; 2020; 259, 105471. [DOI: https://dx.doi.org/10.1016/j.jat.2020.105471]

28. Livshitz, D.; Temlyakov, V.N. Two lower estimates in greedy approximation. Constr. Approx.; 2003; 19, pp. 509-524. [DOI: https://dx.doi.org/10.1007/s00365-003-0533-6]

29. Temlyakov, V.N. Greedy Approximation; Cambridge University Press: Cambridge, UK, 2011.

30. Temlyakov, V.N. Weak greedy algorithms. Adv. Comput. Math.; 2000; 12, pp. 213-227. [DOI: https://dx.doi.org/10.1023/A:1018917218956]

31. Temlyakov, V.N. Greedy algorithms in Banach spaces. Adv. Comput. Math.; 2001; 14, pp. 277-292. [DOI: https://dx.doi.org/10.1023/A:1016657209416]

32. Jiang, B.; Ye, P.X. Efficiency of the weak rescaled pure greedy algorithm. Int. J. Wavelets Multiresolut. Inform. Process.; 2021; 4, 2150001. [DOI: https://dx.doi.org/10.1142/S0219691321500016]

33. Donahue, M.; Gurvits, L.; Darken, C.; Sontag, E. Rate of convex approximation in non-Hilbert spaces. Constr. Approx.; 1997; 13, pp. 187-220. [DOI: https://dx.doi.org/10.1007/BF02678464]

34. Lindenstrauss, J.; Tzafriri, L. Classical Banach Spaces I; Springer: Berlin/Heidelberg, Germany, 1977.

35. Temlyakov, V.N.; Yang, M.R.; Ye, P.X. Greedy approximation with regard to non-greedy bases. Adv. Comput. Math.; 2011; 34, pp. 319-337. [DOI: https://dx.doi.org/10.1007/s10444-010-9155-2]

36. Ye, P.X.; Wei, X.J. Efficiency of weak greedy algorithms for m-term approximations. Sci. China Math.; 2016; 59, pp. 697-714. [DOI: https://dx.doi.org/10.1007/s11425-015-5106-1]

37. Chen, H.; Zhou, Y.C.; Tang, Y.Y.; Li, L.Q.; Pan, Z.B. Convergence rate of the semi-supervised greedy algorithm. Neural Netw.; 2013; 44, pp. 44-50. [DOI: https://dx.doi.org/10.1016/j.neunet.2013.03.001]

38. Lin, S.B.; Rong, Y.H.; Sun, X.P.; Xu, Z.B. Learning capability of the relaxed greedy algorithms. IEEE Trans. Neural Netw. Learn. Syst.; 2013; 24, pp. 1598-1608.