An inertial parallel algorithm for a finite family of $G$-nonexpansive mappings applied to signal recovery

1.   Introduction

Let $\boldsymbol{H}$ be a real Hilbert space with inner product $\langle., .\rangle$ and the induced norm $\|.\|$. Let $C$ be a nonempty subset of $\boldsymbol{H}$, and let $\triangle$ denotes the diagonal of the cartesian product $C \times C$, i.e., $\bigtriangleup = \{(x, x):x \in C\}$. For a directed graph $G$ such that the set $V(G)$ of its vertices coincides with $C$ and the set $E(G)$ of its edges contains all loops, i.e., $E(G) \supseteq \bigtriangleup$. We assume $G$ has no parallel edge. So we can identify the graph $G$ with the pair $(V(G), E(G))$. A mapping $T:C\rightarrow C$ is said to be $G$-contraction if $T$ satisfies the conditions:

$(G1)$ $T$ is edge-preserving, i.e.,

$(G2)$ $T$ decreases weights of edges of $G$, i.e., there exists $\delta \in (0, 1)$ such that

A mapping $T:C\rightarrow C$ is said to be $G$-nonexpansive if $T$ satisfies the condition $(G1)$ and

$(G3)$ $T$ non-increases weights of edges of $G$, i.e.,

The set of a fixed point of $T$ is denoted by $F(T)$, that is, $F(T) = \{z\in \boldsymbol{H}: Tz = z\}$.

In 2008, by using the concepts in fixed point theory and graph theory, Jachymski ^[17] proved some generalizations of Banach's contraction principle in complete metric spaces endowed with a graph. Then in 2012, Aleomraninejed et al. ^[2] introduced some iterative $G$-contraction schemes with $G$-nonexpansive mappings in Banach spaces endowed with a graph. Recently, Alfuraidan and Khamsi ^[3] studied the existence of fixed points and proved a convergence result of monotone nonexpansive mapping on a Banach space endowed with a directed graph. Later on, many authors have discussed the Browder convergence theorem that deliberated the weak and strong convergence of some methods for $G$-nonexpansive mapping in a Hilbert space with a directed graph (see for example ^{[2,3,4,13,32,33]}).

Motivated by the work of ^[1,23], Suparatulatorn et al. ^[28] scrutinized the following modified $S$-iteration scheme:

where $\{\delta _{n}\}$ and $\{\sigma _{n}\}$ are sequences in $(0, 1)$ and $T_{1}, T_{2}:C\rightarrow C$ are $G$-nonexpansive mappings. Additionally, they proved weak and strong convergence in order to approximate common fixed points of two $G$-nonexpansive mappings in a uniformly convex Banach space $\boldsymbol{X}$ endowed with a graph under this iteration.

Otherwise, speeding up the convergence of the algorithm has been interesting by many mathematicians, one of that is inertial extrapolation, which was initially proposed by Polyak ^[22] as an acceleration process. This algorithm was used to solve various convex minimization problems based on the heavy ball method of the two-order time dynamical system. Inertial type methods involve two iterative steps that the second step is obtained from the previous two iterates. These methods are committed to being considered as an efficient technique to deal with various iterative algorithms, particularly with the projection-based algorithms, see in ^{[5,8,9,21,30,31,34]}.

Very recently, Suantai et al. ^[27] used the idea of Anh and Hieu ^[6,7] to present the convergence of the algorithm using the shrinking projection method with the parallel monotone hybrid method for approximating common fixed points of a finite family of $G$-nonexpansive mappings. The application of the algorithm has been provided to signal recovery in a situation without knowing the type of noise. This algorithm is defined in a real Hilbert space as follows:

where $\{\alpha^i_n\}$ is a sequence in $[0, 1]$ such that $\liminf_{n\rightarrow \infty}\alpha^i_n(1-\alpha^i_n) > 0$ for all $i = 1, 2, ..., N$. $\bar{v}_{n}$ is chosen by the optimization all $v_{n}^{i}$ with $x_{n}$. After that, the closed convex set $C_{n+1}$ was constructed by $\bar{v}_{n}$. Finally, the next approximation $x_{n+1}$ is defined as the projection of $x_{1}$ on to $C_{n+1}$. More recently, Cholamjiak et al. ^[11] proposed an inertial forward-backward splitting algorithm for finding the solution of common variational inclusion problems based on the inertial technique and parallel monotone hybrid methods. They proved strong convergence results under some suitable conditions in Hilbert spaces. Here in this paper, the algorithm was very useful in image restoration. For given initial points $x_0, x_1\in C_1 = \boldsymbol{H}$, let the sequences $\{x_n\}, \{y_n\}$ be generated by

where $A_i:\boldsymbol{H}\to\boldsymbol{H}$ and $B:\boldsymbol{H}\to 2^{\boldsymbol{H}}$ are monotone operator with $J^B_{r_n} = (I + r_nB)^{-1}$, $\{r_n\}\subset (0, 2\alpha), \; \{\theta_n\}\subset [0, \theta]$ for some $\theta\in [0, 1]$ and $\{\alpha_n^i\}$ is a sequence in $[0, 1]$ for all $i = 1, 2, ..., N$. It has been notable that if $\{r_n\}\subset (0, 2\alpha)$ where $\alpha$ is a constant of inverse strongly monotone operator $A$, then the mapping $J^B_{r_n}(I-r_nA)$ is nonexpansive. Later on, there have been some results involving the parallel method for solving the fixed point problem (see ^{[10,12,14,15,16,29]}). One of the algorithms for solving common fixed point problems of the concerned nonexpansive operators is distributed inexact averaged operator algorithm (DIO) which is introduced by Li and Feng ^[20]. The DIO algorithm is proposed as follow:

for all $i = 1, 2, ..., N$, where $\hat{x}_{i, n}$ is defined by $\hat{x}_{i, n}: = \sum_{j = 1}^Na_{ij, n}x_{j, n}$, $\epsilon_{i, n}\in \boldsymbol{H}$ is an error for $F_i(\hat{x}_{i, n})$ and $F_i:\boldsymbol{H}\rightarrow \boldsymbol{H}$ is a nonexpansive for all $i = 1, 2, ..., N$. Under the conditions $\sum_{j = 1}^Na_{ij, n} = 1$ for all $i = 1, 2, ..., N$ with $a_{ij, n}\geq a > 0$ and $\alpha_{i, n}\in[\alpha, 1-\alpha]$ for some constant $\alpha\in (0, \frac{1}{2})$, weak convergence theorem was proved in Hilbert spaces.

In this paper, a parallel algorithm for finding a common fixed point of a finite family of $G$-nonexpansive mappings using inertial technique is proposed. Also, the weak convergence theorem is proved by assuming some control conditions in a Hilbert space endowed with graphs. Furthermore, examples and numerical results for supporting the main results of this study are provided, and the convergence rate of the iterative methods from this study is compared. Moreover, the proposed algorithm is applied to solve signal recovery problems. Finally, the last section presents the numerical results.

2.   Preliminaries

In this section, some known definitions and lemmas which will be used in the later sections are stated.

Lemma 2.1. ^[5] Let $\{\psi_n\}$, $\{\delta_n\}$ and $\{\alpha_n\}$ be the sequences in $[0, +\infty)$ such that $\psi_{n+1}\leq \psi_n+\alpha_n(\psi_n-\psi_{n-1})+\delta_n$ for all $n\geq1$, $\sum_{n = 1}^\infty\delta_n < +\infty$ and there exists a real number $\alpha$ with $0\leq\alpha_n\leq\alpha < 1$ for all $n\geq1$. Then the followings hold:

(i) $\Sigma_{n\geq1}[\psi_n-\psi_{n-1}]_+ < +\infty$, where $[t]_+ = \max\{t, 0\}$;

(ii) There exists $\psi^*\in[0, +\infty)$ such that $\lim_{n\rightarrow +\infty}\psi_n = \psi^*$.

Lemma 2.2. ^[26] Let $\boldsymbol{X}$ be a Banach space satisfying Opial's condition and let $\{x_{n}\}$ be a sequence in $\boldsymbol{X}$. Let $u$, $v$ $\in$ $\boldsymbol{X}$ be such that

If $\{x_{n_{k}}\}$ and $\{x_{m_{k}}\}$ are subsequences of $\{x_{n}\}$ which converge weakly to $u$ and $v$, respectively, then $u = v$.

Definition 2.3. Let $G = (V(G), E(G))$ be a directed graph and $(u, v)$ be a directed edge from vertex $u$ to vertex $v$. A graph $G$ is called transitive if for any $u, v, z\in V(G)$ such that $(u, v)$ and $(v, z)$ are in $E(G)$, then $(u, z)\in E(G)$.

Definition 2.4. ^[28] Let $u_{0 }\in V(G)$ and $A$ subset of $V(G).$ We say that

(i) $A$ is dominated by $u_{0}$ if $(u_{0 }, u)\in E(G)$ for all $u\in A$.

(ii) $A$ dominates $u_{0}$ if for each $u\in A$, $(u, u_{0})\in E(G).$

Definition 2.5. Let $G = (V(G), E(G))$ be a directed graph. The set of edges $E(G)$ is said to be convex if $(u_{i}, v_{i})\in E(G)$ for all $i = 1, 2, ..., N$ and $\alpha_{i}\in (0, 1)$ such that $\sum_{i = 1}^{N}\alpha_{i} = 1$, then $(\sum_{i = 1}^{N}\alpha_{i}u_{i}, \sum_{i = 1}^{N}\alpha_{i}v_{i})\in E(G)$.

Lemma 2.6. ^[24] Let $C$ be a nonempty, closed and convex subset of a Hilbert space $\boldsymbol{H}$ and $G = (V(G), E(G))$ a directed graph such that $V(G) = C$. Let $T:C\rightarrow C$ be a $G-$nonexpansive mapping and $\{u_{n}\}$ be a sequence in $C$ such that $u_{n}\rightharpoonup u$ for some $u\in C$. If there exists a subsequence $\{u_{n_{k}}\}$ of $\{u_{n}\}$ such that $(u_{n_{k}}, u)\in E(G)$ for all $k\in \mathbb{N}$ and $\{u_{n}-Tu_{n}\}\rightarrow v$ for some $v\in\boldsymbol{H}$. Then $(I-T)u = v$.

3.   Main results

In this section, we prove the following weak convergence theorem to find a common fixed point of a finite family of $G$-nonexpansive mappings in Hilbert spaces endowed with a graph.

Theorem 3.1. Let $C$ be a nonempty closed and convex subset of a real Hilbert space $\boldsymbol{H}$ and let $G = (V(G), E(G))$ be a transitive directed graph such that $V(G) = C$ and $E(G)$ is convex. Let $T_{i}: C \longrightarrow C$ be a family of $G$-nonexpansive mappings for all $\: i = 1, 2, ..., N$ such that $F = \bigcap\limits_{i = 1}^{N} F(T_{i}) \neq \emptyset$. Let $\{x_{n}\}$, $\{w_{n}\}$ generated by $x_0, x_{1} \in C$ and

where $\{\theta_{n}\} \subset [0, \theta] \:$ for each $\theta \in (0, 1]$ and $\{\alpha_{n}^{i}\}$ and $\{\beta_{n}^{i}\}$ are sequences in $[0, 1]$. Assume that the following conditions are satisfied:

(i) $\sum_{n = 1}^{\infty}\theta_{n}\|x_{n}-x_{n-1}\| < \infty$;

(ii) $\{w_{n}\}$ is dominated by $t$ and $\{w_{n}\}$ dominates $t$ for all $t \in F$, and if there exists a subsequence $\{w_{n_k}\}$ of $\{w_{n}\}$ such that $\{w_{n_k}\} \rightharpoonup u \in C$, then $(\{w_{n_k}\}, u) \in E(G)$;

(iii) $\liminf\limits_{n \rightarrow \infty} \: \alpha_{n}^{i} > 0$;

(iv) $0 < \liminf\limits_{n \rightarrow \infty} \: \beta_{n}^{i}\leq \limsup\limits_{n \rightarrow \infty} \: \beta_{n}^{i} < 1.$

Then the sequence $\{x_{n}\}$ converges weakly to an element in $F$.

Proof. Let $t \in F$. Since $\{w_{n}\}$ dominates $\: t \:$ and $\: T_{i} \:$ is edge-preserving, we get $(T_{i} w_{n}, t) \in E(G) \:$ for all $\: i = 1, 2, ..., N$. Implying thereby $(y_{n}^{i}, t) = \Big((1-\beta_{n}^{i}) w_{n} + \beta_{n}^{i} T_{i} w_{n}, t \Big) \in E(G)$ by $E(G)$ is convex. For all $i = 1, 2, ..., N$, we get

This implies that $\left\| x_{n+1}-t \right\|\leq \left\| x_{n}-t \right\|+ \theta_{n}\|x_{n}-x_{n-1}\|$. From Lemma 2.1 and the assumption (i), we obtain $\lim_{n\rightarrow \infty}\|x_n-t\|$ exists, in particular, $\{x_n\}$ is bounded and also $\{y^i_n\}$ and $\{z^i_n\}$. By the properties in a real Hilbert space $\boldsymbol{H}$, we have

This implies that there exist $i_n\in\{1, 2, ..., N\}$ such that

By the assumptions (i), (iii) and (iv), from (3.3) and $\lim_{n\rightarrow \infty}\|x_n-t\|$ exist, we have

By the definition of our algorithm and the assumption (iv), we have

as $n\rightarrow \infty$. Since $(w_n, t), (t, y^{i_n})\in E(G)$, so $(w_n, y^{i_n})\in E(G)$. It follows from (3.5) that

as $n\rightarrow \infty$. From (3.4) and (3.6), we have

This implies that

as $n\rightarrow \infty$ for all $i = 1, 2, ..., N$. From (3.2), we have

By our assumptions (iii) and (iv), it follows from (3.8) and (3.9) that

for all $i = 1, 2, ..., N$.

Since $\{w_n\}$ is bounded and $\boldsymbol{H}$ is reflexive, $\omega_w(w_n) = \{x\in \boldsymbol{H} : w_{n_k}\rightharpoonup p, \{w_{n_k}\}\subset\{w_n\}\}$ is nonempty. Let $p\in\omega_w(w_n)$ be an arbitrary element. Then there exists a subsequence $\{w_{n_k}\}\subset\{w_n\}$ converging weakly to $p$. Let $q\in\omega_w(w_n)$ and $\{w_{n_m}\}\subset\{w_n\}$ be such that $w_{n_m}\rightharpoonup q$. From Lemma 2.6 and (3.10), we have $p, q\in F$. Applying Lemma 2.2, we obtain $p = q$.

We know that if $T$ is nonexpansive, that $T$ is $G$-nonexpansive. From direct consequences of Theorem 3.1, we have the following corollary:

Corollary 3.2. Let $C$ be a nonempty closed and convex subset of a real Hilbert space $\boldsymbol{H}$, and let $T_{i}: C \longrightarrow C$ be a family of nonexpansive mappings for all $\: i = 1, 2, ..., N \:$ such that $F = \bigcap\limits_{i = 1}^{N} F(T_{i}) \neq \emptyset$. Let $\{x_{n}\}$, $\{w_{n}\}$ generated by $x_0, x_{1} \in C$ and

where $\{\theta_{n}\} \subset [0, \theta] \:$ for each $\theta \in (0, 1]$ and $\{\alpha_{n}^{i}\}$ and $\{\beta_{n}^{i}\}$ are sequences in $[0, 1]$. Assume that the following conditions are satisfied:

(i) $\sum_{n = 1}^{\infty}\theta_{n}\|x_{n}-x_{n-1}\| < \infty$;

(ii) $\liminf\limits_{n \rightarrow \infty} \: \alpha_{n}^{i} > 0$;

(iii) $0 < \liminf\limits_{n \rightarrow \infty} \: \beta_{n}^{i}\leq \limsup\limits_{n \rightarrow \infty} \: \beta_{n}^{i} < 1.$

Then the sequence $\{x_{n}\}$ converges weakly to an element in $F$.

4.   Application to signal recovery

A signal recovery problem can be modeled as the following underdetermined linear equation system:

where $u\in \mathbb{R}^{\bar{N}}$ is an original signal, $v\in \mathbb{R}^M$ is the observed signal which is squashed by the filter matrix $A:\mathbb{R}^{\bar{N}}\rightarrow \mathbb{R}^M$ and noisy $\epsilon$. It is well known that the problem (4.1) can be solved by the LASSO problem:

where $\lambda > 0$. As a result, various techniques and iterative schemes have been developed over the years to solve the Lasso problem, see ^[18,19,25]. In this case, we set $Tu = \mathrm{prox}_{\lambda g}(u-\lambda\nabla f(u))$, where $f(u) = \frac{1}{2}\|v-Au\|_2^2$ and $g(u) = \lambda\|u\|_1$. It is known that $T$ is a nonexpansive mapping when $\lambda\in(0, 2/L)$ and $L$ is the Lipschitz constant of $\nabla f$.

The goal of this paper is to remove noise without knowing the type of filter and noise. Thus, we are interested in the following common problems which are introduced by Suantai et al. ^[27]:

where $u$ is an original signal, $A_{i}$ is a bounded linear operator and $v_{i}$ is an observed signal with noisy for all $i = 1, 2, ..., N.$ We can apply our proposed algorithm (3.1) to solve the problem (4.3) by setting $T_{i}u = \mathrm{prox}_{\lambda_i g_i}(u-\lambda_i\nabla f_i(u))$.

For all experiments in this section, the size of signal is selected to be $\bar{N} = 1024$ and $M = 512$, where the original signal $x$ is generated by the uniform distribution in $[-2, 2]$ with $m$ nonzero elements. Suppose that

for all $n\in\mathbb{N}.$ In the first part, we solve the problem (4.2) by considering the different components within algorithm (3.1): $\lambda$, $\bar{\theta}_{n}$, $\beta_{n}^{1}$ and $\alpha_{n}^{1}$. Let $A$ be the Gaussian matrix generated by commend $randn(M, \bar{N})$, the observation $b$ be generated by white Gaussian noise with signal-to-noise ratio SNR = 40 and $m = 25$. Given that the initial points $x_{0}$, $x_{1}$ are generated by commend $randn(\bar{N}, 1)$. We use the mean-squared error to measure the restoration accuracy defined as follows: $MSE_{n} = \frac{1}{1024}\|x_{n}-x\|_{2}^{2} < 10^{-5}$. To find suitable parameters for the next numerical experiments, we present numerical results through Tables 1–4 with different parameters $\bar{\theta}_{n}$, $\lambda$, $\beta_{n }^{1}$ and $\alpha_{n}^{1}$, respectively.

Case 1. We compare the performance of the algorithm with different parameters $\bar{\theta}_{n}$ by setting $\lambda = \frac{1}{\|A\|_{2}^2}, \beta_{n}^{1} = 0.5$ and $\alpha_{n}^{1} = \frac{n}{5(n+1)}$ for all $n\in\mathbb{N}$. Then the results are presented in Table 1.

Case 2. We compare the performance of the algorithm with different parameters $\lambda$ by setting $\bar{\theta}_{n} = \frac{1}{(n+100)^{2}}$ and select $\alpha_{n}^{1}$ and $\beta_{n}^{1}$ are the same as in Case 1. Then the results are presented in Table 2.

Case 3. We compare the performance of the algorithm with different parameters $\beta_{n}^{1}$ by setting $\lambda = \frac{18}{10\|A\|_{2}^2}$, $\bar{\theta}_{n} = \frac{1}{(n+100)^{2}}$ and select $\alpha_{n}^{1}$ is the same as in Case 1. Then the results are presented in Table 3.

Case 4. We compare the performance of the algorithm with different parameters $\alpha_{n}^{1}$ by setting $\lambda = \frac{18}{10\|A\|_{2}^2}$, $\bar{\theta}_{n} = \frac{1}{(n+100)^{2}}$ and $\beta_{n}^{1} = 0.99$. Then the results are presented in Table 4.

We noticed that in all the above 4 cases, selecting $\alpha_{n}^{1} = \frac{n}{n+1}$ for all $n\in\mathbb{N}$ and setting $\lambda, \bar{\theta}_{n}$ and $\beta_{n}^{1}$ as in Case 4, yield the best results.

In the next experiment, we would like to compare the performance of the parallel monotone hybrid algorithm (1.1), inertial parallel monotone hybrid algorithm (1.2) and algorithm (3.1) for solving the problem (4.3) with three filters, that is $N = 3$. The original signal is generated by the uniform distribution in the interval $[-2, 2]$ with $m$ nonzero element. Let $A_{i}$ be the Gaussian matrix generated by commend $randn(M, \bar{N})$, the observation $b_{i}$ be generated by white Gaussian noise with signal-to-noise ratio SNR = 40, we choose $\lambda_{i} = \frac{18}{10\|A_{i}\|_{2}^2}$, $\beta_{n}^{i} = 0.99$ and $\alpha_{n}^{i} = \frac{n}{n+1}$ for all $i = 1, 2, 3$, $n\in\mathbb{N}$ and $\bar{\theta}_{n} = \frac{1}{(n+100)^{2}}$ for our algorithm (3.1). Choosing

for all $i = 1, 2, 3$, $n\in\mathbb{N}$ where $K$ is the number of iterations that we want to stop for the parallel monotone hybrid algorithm (1.1) and $\alpha_{n}^{i} = \frac{n}{n+1}$ for all $i = 1, 2, 3$, $n\in\mathbb{N}$ and $\bar{\theta}_{n} = \frac{1}{(n+100)^{2}}$ for the inertial parallel monotone hybrid algorithm (1.2). We use $MSE_{n} < 10^{-5}$. Further, we select $x_{0}$ and $x_{1}$ are the same as in the first part. The results are presented in Table 5.

In the next comparison, we will show the performance of our algorithm comparing with DIO algorithm ^[20] when $N = 3$. The original signal is generated by the uniform distribution in the interval $[-2, 2]$ with $m$ nonzero element. We suppose $A_{i}$, $b_{i}$, $\lambda_{i}$, $\bar{\theta}_{n}$, $\beta_{n}^{i}$, $\alpha_{n}^{i}$, $x_{0}$ and $x_{1}$ are the same as in the second part for our algorithm. For DIO algorithm, we choose $x_{1, 1} = x_{2, 1} = x_{3, 1} = x_1$, $a_{i1, n} = a_{i2, n} = \frac{n}{4n+1}$, $a_{i3, n} = (1-a_{i1, n}-a_{i2, n})$ and $\alpha_{i, n} = 0.3$ for all $i = 1, 2, 3$ and all $n\in\mathbb{N}$. We use $MSE_{n} < 10^{-5}$. The results are presented in Table 6.

Table 5 shows the comparison of the number of iterations and the time elapsed with $m = 50,100,150$ nonzero elements for the three algorithms: Parallel monotone hybrid algorithm, Inertial parallel monotone hybrid algorithm, and our algorithm. For comparison of our algorithm and the DIO are showed in Table 6. In case $m = 150$, the original signal and the measurement of Tables 5 and 6 can be seen in Figures 1 and 4, respectively. The results of the comparison of the three algorithms can be seen in Figures 2 and 3, and the results of DIO algorithm can be seen in Figures 5 and 6. Based on the above results, we can see that our proposed algorithm is less time-consuming and requires fewer iterations than the other three algorithms. We note that the numerical results of the DIO algorithm have been shown for the best of the sequences $\{x_{1, n}\}, \ \{x_{2, n}\}, \ \{x_{3, n}\}$.

The final experiment considers algorithm (3.1) for solving (4.3) with multiple inputs $A_{i}$. The original signal is generated by the uniform distribution in the interval $[-2, 2]$ with $m$ nonzero element. We suppose $A_{i}$, $b_{i}$, $\lambda_{i}$, $\bar{\theta}_{n}$, $\beta_{n}^{i}$, $\alpha_{n}^{i}$, $x_{0}$ and $x_{1}$ are the same as in the second part. We use $MSE_{n} < 5\times10^{-5}$. The results are following presented in Table 7.

Table 7 presents the numerical results of the number of iterations and the time elapsed with multiple inputs $A_{i}$ and $m = 25, 50, 75,100$ nonzero elements for our algorithm. The original signal and the measurement by using $A_{1}$–$A_{3}$ of Table 7 are shown in Figure 7. From Figures 8 and 9, it can be observed that incorporating all 3 Gaussian matrices $(A_ {1}$–$A_ {3})$ into algorithm (3.1) is more effective with respect to time and number of iterations than involving only one or two of them.

5.   Conclusions

We introduce a new inertial parallel algorithm to solve the common fixed point problem for a finite family of $G$-nonexpansive mappings in a Hilbert space with a directed graph. Our primary theorems ensure that this algorithm converges weakly to an element of the problem's solution set under certain conditions. The algorithm is then used to solve the signal recovery problem involving several filters.

Acknowledgments

This research project was supported by the Thailand Science Research and Innovation Fund and the University of Phayao (Grant No. FF64-UoE002).

Conflict of interest

The authors declare that they have no competing interests.