A relaxed projection method using a new linesearch for the split feasibility problem

1.   Introduction

In this work, we study the split feasibility problem (shortly, (SFP)) which is formulated as follows:

where $C$ and $Q$ are nonempty closed convex subsets of real Hilbert spaces $H_1$ and $H_2$, respectively, and $A:H_1\rightarrow H_2$ is a bounded linear operator. This problem was first proposed by Censor and Elfving ^[5] in Euclidean spaces (for recent results on the problem (SFP), see ^{[10,12,13,25]}). There are some related topic for splitting problems see ^{[14,17,22,24]}. Many applications in real world such as image reconstruction, signal recovery and intensity-modulated radiation therapy (shortly, (IMRT)) can be seen as solving the problem (SFP).

Byrne ^[3,4] proposed the following projection algorithm for solving the problem (SFP):

where $\alpha\in(0, 2/\|A^*A\|)$, $A^*$ is the adjoint operator of $A$, $P_C$ and $P_Q$ are projections onto $C$ and $Q$, respectively. This method is often called the CQ-algorithm. However, it is observed that, in general, the projections $P_C$ and $P_Q$ are not an easy task to be computed.

To eliminate this difficulty, Fukushima ^[15] introduced the level sets $C$ and $Q$ which are defined by

where $c: H_1\rightarrow\mathbb{R}$ and $q:H_2\rightarrow\mathbb{R}$ are convex and subdifferential functions, and $\partial c$ and $\partial q$ are bounded operators. Fukushima ^[15] also introduced a relaxed projection algorithm for solving variational inequality problem and gave numerical experiments to support main result.

In 2004, Yang ^[27] presented a relaxed CQ-algorithm for solving the problem (SFP), by replacing $P_C$ and $P_Q$ by $P_{C_k}$ and $P_{Q_k}$, respectively. In this case, $C_k$ and $Q_k$ are defined by

where $\xi_k\in\partial c(x_k)$, and

where $\zeta_k\in\partial q(Ax_k)$.

It is easily seen that $C\subset C_k$ and $Q\subset Q_k$ for all $k\geq1$. We note that $P_{C_k}$ and $P_{Q_k}$ are easily computed since these sets are half-spaces.

Precisely, Yang ^[27] proposed the following relaxed CQ-algorithm:

where $\{\alpha_n\}$ is a sequence in $(0, 2/\|A^*A\|)$, $A^*$ is the adjoint operator of $A$ and $C_k$ and $Q_k$ are given by (1.4) and (1.5), respectively.

Recently, Gibali et al. ^[16] (see also Qu and Xiu ^[20]) proposed the modification of the relaxed CQ-algorithm by using the linesearch technique in real Hilbert spaces. For each $k\geq1$, define a mapping $F_k:H_1\rightarrow H_2$ by

They constructed the following algorithm:

Algorithm 1.1. Given constants $\gamma > 0$, $\ell\in(0, 1)$ and $\mu\in(0, 1)$. Let $x_1$ be arbitrary in $H_1$. For each $k\geq1$, calculate

where $\alpha_k = \gamma\ell^{m_k}$ and $m_k$ is the smallest nonnegative integer such that

Construct the next iterative step $x_{k+1}$ by

There have been various methods invented for solving the problem (SFP) (see, for example, ^{[5,6,7,8,9,10,11,12,14,15,16,17,18,19,21,26]}). It is observed that, in each iteration, we have to find the integer $m_k$ such that (1.9) holds. So it takes CPU time and number of iterations in convergence. It is our aim to design new linesearch that takes CPU time less than Algorithm 1.1 and others.

Recently, Tian and Zhang ^[23] proposed a new regularized CQ algorithm without a priori knowledge of the operator norm to solve the split feasibility problem and provided strong convergence theorem in Hilbert spaces. Later, Dang et. al. ^[11] introduced inertial relaxed CQ algorithms for the split feasibility problem and proved asymptotical convergence. In 2018, Dong et. al. ^[13] introduced the projection and contraction methods for solving the split feasibility problem using the inverse strongly monotone property of the underlying operator of the SFP.

Motivated by the previous works, we modify algorithm of Gibali et al. ^[16] and propose the relaxed $CQ$-algorithm with the new linesearch in real Hilbert spaces and prove some weak convergence theorems of the proposed method under mild assumptions. Finally, we give some computational results to compare with the algorithms of Gibali et al. ^[16] and Yang ^[27]. Numerical experiments show that our algorithm has a better performance than others.

2.   Preliminaries

In this section, we give some definitions and lemmas which are used in the proof. Throughout this paper, we use the following notations:

$\bullet$ $\rightharpoonup$ denotes the weak convergence;

$\bullet$ $\omega_{w}(x_k) = \{x\, :\, \exists(x_{k_n}) \subset(x_k)\ \text{such that} \ x_{k_n}\rightharpoonup x\}$ denotes the weak $\omega$-limit set of $(x_k)$.

Let $H$ be a real Hilbert space. We recall the following definition.

(1) A mapping $T : H \rightarrow H$ is said to be firmly nonexpansive if, for all $x, y \in H$,

(2) A function $f : H \rightarrow \mathbb{R}$ is said to be convex if

for all $\lambda\in(0, 1)$ and for all $x, y\in H$.

A differentiable function $f$ is convex if and only if there holds the inequality:

for all $z\in H$.

(3) An element $g \in H$ is called a subgradient of $f : H \rightarrow\mathbb{R}$ at $x$ if

for all $z\in H$, which is called the subdifferentiable inequality. The set of subgradients of $f$ at $x$ is denoted by $\partial f(x)$.

(4) A function $f : H \rightarrow \mathbb{R}$ is said to be subdifferentiable at $x$ if it has at least one subgradient at $x$. A function $f$ is said to be subdifferentiable if it is subdifferentiable at all $x\in H$.

(5) A function $f : H \rightarrow \mathbb{R}$ is said to be weakly lower semi-continuous (shortly, $w$-lsc) at $x$ if $x_k\rightharpoonup x$ implies

(6) A projection of $H$ onto a nonempty closed convex subset $C\subset H$ is defined by

for all $x\in H$.

Next, we give some useful lemmas for our proof.

Lemma 2.1. ^[2] Let $C$ be a nonempty closed convex subset of a real Hilbert space $H$. Then, for any $x \in H$, the following assertions hold:

$\rm (1)$ $\langle x-P_Cx, z-P_Cx\rangle\leq0$ for all $z\in C$;

$\rm (2)$ $\|P_Cx-P_Cy\|^2\leq\langle P_Cx-P_Cy, x-y\rangle$ for all $x, y\in H$;

$\rm (3)$ $\|P_Cx-z\|^2\leq\|x-z\|^2-\|P_Cx-x\|^2$ for all $z\in C$.

From Lemma 2.1, we see that the operator $I - P_C$ is also firmly nonexpansive, where $I$ denotes the identity operator, i.e., for any $x, y \in H$,

Lemma 2.2. ^[1] Let $S$ be a nonempty closed convex subset of a real Hilbert space $H$ and $\{x_n\}$ be a sequence in $H$ satisfying the following properties:

$\rm (a)$ $\lim\limits_{k\rightarrow\infty}\|x_k-x\|$ exists for each $x \in S$;

$\rm (b)$ $\omega_w(x_k)\subset S$.

Then $\{x_k\}$ converges weakly to a point in $S$.

Now, we give our main results in this paper.

3.   Main results

In this section, we introduce a new relaxed projection algorithm using the linesearch technique and prove its weak convergence. We have already defined the mappings $F_k$ and $\nabla F_k$ as in (1.7). Our algorithm is generated by the following manner:

Algorithm 3.1. Given constants $\gamma > 0$, $\ell\in(0, 1)$ and $\mu\in \big(0, \frac{1}{4}\big)$. Let $x_1$ be arbitrary in $H_1$. For each $k\geq1$, calculate

Construct the next iterative step $x_{k+1}$ by

where $\alpha_k = \gamma\ell^{m_k}$ and $m_k$ is the smallest nonnegative integer such that

It is remarked that Algorithm 3.1 is based on extra-gradient type method which was firstly introduced by Noor ^{[28, 29]}.

Following the proof line as in ^[20], we obtain the following lemma:

Lemma 3.1. Let $\gamma > 0$, $\ell\in(0, 1)$ and $\mu\in(0, \frac{1}{4})$. Then, the linesearch $(3.3)$ terminates after a finite number of steps. In addition, we have the following:

for all $k\geq 1$, where $L = \|A\|^2$.

Proof. From ^[20], we know that

and

It follows that

The second part is obtained by ^[20]. Hence the linesearch (3.3) is well-defined. This completes the proof.

In what follows, we denote $S$ by the solution set of the problem (SFP) and also assume that $S$ is nonempty.

Theorem 3.2. The sequence $\{x_k\}$ generated by Algorithm 3.1 converges weakly to a point in $S$.

Proof. Let $z\in S$. Since $C\subseteq C_k$ and $Q\subseteq Q_k$, it follows that $z = P_C(z) = P_{C_k}(z)$ and $Az = P_Q(Az) = P_{Q_k}(Az)$. Hence $\nabla F_k(z) = 0$. Using Lemma 2.1 (c), we get

Also, we obtain

Due to (2.7) and $\nabla F_k(z) = 0$, we have

It also follows that

From (2.3) and (3.8), we have

Also, we have

Combining (3.8)–(3.13), by Lemma $3.2$, we obtain

Using (3.3) and (3.4), we have

This implies that

and hence $\lim\limits_{k\rightarrow\infty}\|x_k-z\|$ exists. Moreover, $\{x_k\}$ is bounded. From (3.15), we also have

and

Moreover, we have

So, we obtain

as $k\rightarrow\infty$. Since $\{x_k\}$ is bounded, assume that $\omega_w(x_k)$ is nonempty. Let $x^*\in\omega_w(x_k)$. Then there exists a subsequence $\{x_{k_n}\}$ of $\{x_k\}$ such that $x_{k_n}\rightharpoonup x^*$.

Now, we show that $x^*\in S$. Since $x_{k_n+1}\in C_{k_n}$ by the definition of $C_{k_n}$, we get

where $\xi_{k_n}\in\partial c(x_{k_n})$. By the boundedness of $\partial c$ and (3.20), we have

as $n\rightarrow\infty$. By the w-lsc of $c$, $x_{k_n}\rightharpoonup x^*$ and (3.22), it follows that

Hence $x^*\in C$.

Next, we show that $Ax^*\in Q$. Since $P_{Q_{k_n}}(Ax_{k_n})\in Q_{k_n}$, we have

where $\eta_{k_n}\in\partial q(Ax_{k_n})$. So, we have

as $n\rightarrow\infty$. Since $x_{k_n}\rightharpoonup x^*$, $Ax_{k_n}\rightharpoonup Ax^*$. The w-lsc of $q$ and (3.25) imply that

Hence $Ax^*\in Q$. Using Lemma 2.2, we conclude that the sequence $\{x_k\}$ converges weakly to a point in $S$. This completes the proof.

Remark 3.4. Algorithm 3.1 in Theorem 3.2 is quite different from that of Gibali et al. ^[16]. To be more precise, the linesearch (3.3) is defined by a new way of two step method.

Remark 3.5. Theorem 3.2 is more convenient than the results of Yang ^[27] in practice. In fact, we do not require the information of the operator norm which is not easy in computation.

4.   Numerical experiments

In this section, we provide some numerical experiments in signal recovery to compare our algorithm with those of Yang ^[27] and Gibali et al. ^[16]. In signal processing, the compressed sensing can be formulated as inverting the equation system:

where $x\in\mathbb{R}^N$ is a vector with $m$ nonzero components to be recovered, $y\in\mathbb{R}^M$ is the observed or measured data with noisy $\varepsilon$ and $A : \mathbb{R}^N\rightarrow \mathbb{R}^M$ $(M < N)$ is a bounded linear observation operator. Here $A$ is sparse and the range of it is not closed in most inverse problems and thus $A$ is often ill-condition and the problem is also ill-posed.

When $x$ is a sparse expansion, to find solutions of the problem (4.1) can be seen as solving the following LASSO problem:

where $t > 0$ is a given constant. The sparse vector $x\in\mathbb{R}^N$ is generated from the uniform distribution in the interval $[-2, 2]$ with $m$ nonzero elements. The matrix $A\in\mathbb{R}^{M\times N}$ is generated from a normal distribution with mean zero and variance one. The observation $y$ is generated by white Gaussian noise with signal-to-noise ratio SNR = 40. The process is started with $t = m$ and initial point $x_1$ is picked randomly.

Let $C = \{x \in \mathbb{R}^N : \|x\|_1\leq t\}$ and $Q = \{y\}$. Then the minimization problem (4.2) can be seen as the problem (SFP) and, since the projection onto the closed convex $C$ does not have a closed form solution, we make use of the subgradient projection. Define a convex function $c(x) = \|x\|_1-t$ and denote the level set $C_k$ by:

where $\xi_k\in\partial c(x_k)$. Then the orthogonal projection onto $C_k$ can be calculated by the following:

The subdifferential $\partial c$ at $x_k$ is

In our experiment, we consider two cases as follows:

Case 1: $N = 512$, $M = 256$ and $m = 10$;

Case 2: $N = 4096$, $M = 2048$ and $m = 100$.

Next, we give some numerical results by using the relaxed $CQ$-algorithms defined by Yang ^[27], Gibali et al. ^[16] and our algorithms (Algorithm 3.1).

The iteration is stopped when the following criteria is satisfied:

where $x^*$ is an estimated signal of $x$.

In what follows, let $\alpha_k = \frac{1}{\|A\|^2}$ in the $CQ$-algorithm by Yang ^[27]. Define $\gamma = 2$, $\ell = 0.5$ and $\mu = 0.2$ in that of Gibali et al. ^[16]. Then the numerical results are reported as follows:

Remark 4.1. (1) In Figures 1 and 4, we see that the signal recovered by Algorithm 3.1 in both Case 1 and Case 2 has number of iterations and cpu time less than algorithm of Yang ^[27] and Gibali et al. ^[16]. In the algorithm of Yang ^[27], the stepsize $\alpha_k$ depends on the operator norm $\|A\|$ whenever the matrix has a large dimension, it may be compute very hard and has a costly cpu time. It is observed that our new linesearch has a less cpu time than that of Gibali et al. ^[16].

(2) In Figures 2 and 5, we plot the error value of iterations. We see that the errors of Algorithm 3.1 decrease faster than those of other algorithms. Also, in Figures 3 and 6, the objective function values obtained by Algorithm 3.1 have a better convergence behaviour than other algorithms.

5.   Conclusions

In this paper, we proposed the relaxed $CQ$-algorithm with new two steps by using a new linesearch in real Hilbert spaces. The computation of matrix inverse and norm of operators is not required in our algorithm. Also, we gave in a simple and novel way how the sequence generated by the method weakly converges to a solution of the problem (SFP). All the results are compared to the relaxed $CQ$-algorithms of Yang ^[27] and Gibali et al. ^[16]. Finally, we found that the proposed algorithm is effective and outruns other known methods in the literature.

Acknowledgments

The first author thanks Chiang Mai University for financial support.

Conflict of interest

The authors declare no conflict of interest.