1 Introduction

In this paper we focus on the Split Feasibility Problem (SFP), which is formulated as follows.

$$\begin{aligned} \text {Find a point }\ x^*\in C \ \text {such that} \ Ax^*\in Q, \end{aligned}$$
(1.1)

where \(A:H_1 \rightarrow H_2\) is a bounded and linear operator, \(C\subseteq H_1\) and \(Q\subseteq H_2\) are nonempty, closed and convex sets. The split feasibility problem was first introduced by Censor and Elfving [1] in Euclidean spaces, and later was employed for solving an inverse problem in intensity-modulated radiation therapy (IMRT) treatment planning, see [2]. A more general problem in this area is the Split Inverse Problem (SIP) introduced by Censor et al. [3] as well as Byrne et al. [4]. Observe that in the special case where \(H_1=H_2\) and \(A=I\), that is the identity operator, the SFP (1.1) reduces to the well-known, two-sets Convex Feasibility Problem (CFP). The SFP can be reformulated as the following constrained minimization.

$$\begin{aligned} \min _{x\in C} \Vert P_Q(Ax)-Ax\Vert \end{aligned}$$
(1.2)

Due to this reformulation, Byrne [5, 6] introduced the CQ algorithm which is based on the projected gradient method, see e.g., Goldstein [7]. The iterative step of the CQ algorithm has the following nature:

$$\begin{aligned} x_{k+1}=P_C \left( x_k-\gamma A^T(I-P_Q)Ax_k\right) \end{aligned}$$
(1.3)

where \(A^T\) stands for the transpose of A. This method has been studied extensively and several generalizations were introduced in the literature. For example, Xu [8] showed that the CQ algorithm converges weakly in real Hilbert spaces; this has been shown using the fixed point and the projected gradient approaches. Since the CQ algorithm requires calculating the orthogonal projections onto the sets C and Q per each step, this can be applied only whenever an explicit formula for these projections exist and this is mainly the case when the sets are “simple”. For solving the variational inequality problem, Fukushima in [9] introduced a way which does not require to compute orthogonal projection onto sets, but subgradient projections onto super-sets \(C\subset C_k\) and \(Q \subset Q_k\). Following this idea, Yang in [10], proposed the relaxed CQ algorithm for solving the SFP (1.1), in which \(P_{C_k}\) and \(P_{Q_k}\) are orthogonal projections onto the half-spaces \(C_k\) and \(Q_k\), respectively. Since these projections are easily calculated, this method appears to be very practical. On the other hand, the convergence theorem requires to calculate the spectral norm of the operator A. Hence, one way to avoid this estimation was proposed by Qu and Xiu [11] by adopting an Armijo-line search. Wang et al. [12] proposed an inexact projection method for solving the SFP (1.1) which converges strongly in Euclidean spaces. Lopez et al. [13] studied the SFP in real Hilbert spaces and presented a weak convergence algorithm that does not require evaluating the spectral norm of the operator A. Several other extensions for example, are Dong et al. [14] and Tang et al. [15]. For further projection methods for solving the SFP (1.1) consult [16, 17] and the references therein.

Our work in this paper focuses on the modified relaxation CQ algorithm with the Armijo-line search of Qu and Xiu [11] in real Hilbert spaces. Under mild assupmtions, we present a simple and novel approach to prove the weak convergence of the algorithm. To illustrate the method’s efficiency, we present a comparison with the Yang’s [10] relaxed CQ algorithm for solving the LASSO problem (4.1).

The paper is organized as follows. In Sect. 2, definitions and notions which will be useful for our analysis are presented. In Sect. 3, we analyze the weak convergence of the modified relaxation CQ algorithm. And finally, in Sect. 4, we present numerical examples comparing the modified relaxation CQ algorithm and the Yang’s [10] relaxed CQ algorithm for solving the LASSO problem.

2 Preliminaries

Throughout this paper, H denotes a real Hilbert space endowed with a scalar product \(\langle \cdot , \cdot \rangle \) and its associated norm \(\Vert \cdot \Vert \), and I is the identity operator on H. We denote by \(\Omega \) the solution set of the SFP (1.1). Moreover, \(x^k \rightarrow x\) (\(x^k \rightharpoonup x\)) represents that the sequence \(\{x^k\}\) converges strongly (weakly) to x. Finally, we denote by \(\omega _{w}(x^k)\) all the weak cluster points of \(\{x^k\}\).

Recall that the orthogonal projection \(P_{C}x\) from H onto the nonempty, closed and convex set \(C\subset H\) is defined as follows:

$$\begin{aligned} P_{C}x = \arg \min _{y\in C} \Vert x-y\Vert . \end{aligned}$$
(2.1)

It is well known that the orthogonal projection operator satisfies the following properties (see for example [18]).

Lemma 2.1

Let C be a nonempty, closed and convex subset of H. Then for any \(x\in H\), the following assertions hold:

  1. (i)

    \(\langle x - P_{C}x, z- P_{C}x \rangle \le 0\) for all \(z\in C\);

  2. (ii)

    \(\Vert P_{C}x - P_{C}y\Vert ^{2} \le \langle P_{C}x - P_{C}y, x-y \rangle \) for all \(x,y \in H\);

  3. (iii)

    \(\Vert P_{C}x - z\Vert ^{2} \le \Vert x-z\Vert ^{2} - \Vert P_{C}x -x\Vert ^{2}\) for all \(z\in C\).

Definition 2.1

([18]) A mapping \(T:H\rightarrow H\) is said to be

  1. (i)

    nonexpansive, if and only if \(\Vert Tx-Ty\Vert \le \Vert x-y\Vert \), \(\forall x,y\in H\);

  2. (ii)

    firmly nonexpansive, if and only if \(\langle x-y, Tx - Ty \rangle \ge \Vert Tx-Ty\Vert ^{2}\), \(\forall x,y \in H\).

From Lemma 2.1, it can be seen that the projection operator \(P_{C}\) is nonexpansive and even firmly nonexpansive (this can be easily proved by the Cauchy-Schwartz inequality). In addition, the operator \(I-P_C\) is also firmly nonexpansive, where I denotes the identity operator, i.e., for any \(x,y \in H\),

$$\begin{aligned} \langle (I-P_C)x - (I- P_C)y , x-y\rangle \ge \left\| (I-P_C)x - (I- P_C)y \right\| ^2. \end{aligned}$$
(2.2)

We shall make full use of the following lemma to facilitate our proof.

Lemma 2.2

([19]) Let D be a nonempty, closed and convex subset of H and \(\{x_n\}\) be a sequence in H that satisfies the following properties:

  1. (i)

    \(\lim _{n\rightarrow \infty }\Vert x_n - x\Vert \) exists for each \(x\in D\);

  2. (ii)

    \(\omega _{w}(x_n)\subset D\).

Then \(\{x_n\}\) converges weakly to a point in D.

For the convergence proof of the modified relaxation CQ algorithm, we assume that the following two conditions hold.

(A1) The sets C and Q can be presented as follows.

$$\begin{aligned} C = \{ x\in H_1 | c(x)\le 0 \}, \end{aligned}$$
(2.3)

and

$$\begin{aligned} Q = \{ y\in H_2 | q (y)\le 0 \}, \end{aligned}$$
(2.4)

where \(c : H_1\rightarrow \mathbb {R}\) and \(q: H_2\rightarrow \mathbb {R}\) are convex and subdifferential functions on \(H_1\) and \(H_2\), respectively. Assume also that the subdifferential operators \(\partial c\) and \(\partial q\) of c and q are bounded, i.e., bounded on bounded sets.

(A2) For any \(x\in H_1\) and \(y\in H_2\), at least one subgradient \(\xi \in \partial c(x)\) and \(\eta \in \partial q(y)\) can be calculated, where \(\partial c(x)\) and \(\partial q(y)\) are the subdifferentials of c(x) and q(y) at the points x and y, respectively.

$$\begin{aligned} \partial c(x) = \{ \xi \in H_1 | c(z) \ge c(x) + \langle \xi , z -x \rangle , \quad \forall z \in H_1 \}, \end{aligned}$$
(2.5)

and

$$\begin{aligned} \partial q(y) = \{ \eta \in H_2 | q(u) \ge q(y) + \langle \eta , u -y \rangle ,\quad \forall u\in H_2 \}. \end{aligned}$$
(2.6)

Now, we define the sets \(C_{k}\) and \(Q_{k}\):

$$\begin{aligned} C_{k} =\left\{ x\in H_1 | c(x^k) + \langle \xi ^{k}, x - x^k \rangle \le 0\right\} , \end{aligned}$$
(2.7)

where \(\xi ^{k}\in \partial c(x^k)\), and

$$\begin{aligned} Q_{k} =\left\{ y\in H_2 | q(Ax^k) + \langle \eta ^{k}, y - Ax^k \rangle \le 0\right\} , \end{aligned}$$
(2.8)

where \(\eta ^{k}\in \partial q(Ax^k)\). Observe that if \(\xi ^{k}\ne 0\) and \(\eta ^{k}\ne 0\) then \(C_{k}\) and \(Q_{k}\), respectively, are half-spaces. Otherwise, they are the whole space.

Remark 2.1

By the definition of the subgradient, it is clear that \(C \subseteq C_{k}\), \(Q\subseteq Q_{k}\), and the orthogonal projections onto \(C_{k}\) and \(Q_{k}\) can be directly calculated. For example, for \(\xi ^{k}\in \partial c(x^k)\)

$$\begin{aligned} P_{C_{k}}x^k:= {\left\{ \begin{array}{ll} x^k-\frac{{c(x^k)}}{\Vert \xi ^{k}\Vert ^2}\xi ^{k} &{}\quad \text {if }\xi ^{k}\ne 0,\\ x^k &{}\quad \text { otherwise.} \end{array}\right. } \end{aligned}$$
(2.9)

The following lemma is essential for the algorithm’s analysis.

Lemma 2.3

([20]) Let \(f:\mathbb {R}^{n}\rightarrow \mathbb {R}\) be a convex function, then f is subdifferentiable everywhere and its subdifferentials are uniformly bounded on any bounded subset of \(\mathbb {R}^{n}\).

3 Convergence of the modified relaxation CQ algorithm

In this section, we first recall the modified relaxation CQ algorithm with an Armijo-line search of [11] and afterwards prove its convergence. For the convenience of the reader we define the function \(F_k: H_1 \rightarrow H_1\) by

$$\begin{aligned} F_k(x) = A^{*}(I - P_{Q_k})Ax \end{aligned}$$
(3.1)

where \(A^{*}\) stands for the conjugate of A (transpose in finite dimensional spaces). Next we present the algorithm.

3.1 The modified relaxation CQ algorithm with Armijo-line search

Given constants \(\gamma >0\), \(l\in (0,1)\) and \(\mu \in (0,1)\). Let \(x^{0}\) be arbitrary. For \(k\ge 1\), calculate

$$\begin{aligned} \overline{x}^{k} = P_{C_{k}} \left( x^{k} - \alpha _{k}F_{k}(x^{k}) \right) , \end{aligned}$$
(3.2)

where \(\alpha _k = \gamma l^{m_k}\) and \(m_k\) is the smallest nonnegative integer m such that

$$\begin{aligned} \alpha _k \Vert F_k (x^k) - F_k (\overline{x}^{k}) \Vert \le \mu \Vert x^{k}- \overline{x}^{k}\Vert . \end{aligned}$$
(3.3)

Construct the next iterative step \(x^{k+1}\) by

$$\begin{aligned} x^{k+1} = P_{C_k}\left( x^k - \alpha _k F_{k}(\overline{x}^{k})\right) . \end{aligned}$$
(3.4)

The next lemma shows that the algorithm is well-defined.

Lemma 3.1

([11]) The Armijo-line search (3.3) terminates after a finite number of steps. In addition,

$$\begin{aligned} \frac{\mu l}{L} < \alpha _k \le \gamma , \text { for all }\ k\ge 0 \end{aligned}$$
(3.5)

where \(L = \Vert A\Vert ^2\).

Now, we are finally ready to present our main result, which is the establishment of the weak convergence of the modified relaxation CQ algorithm.

Theorem 3.1

Assume that the solution set \(\Omega \) of the SFP (1.1) is nonempty (consistent) and that assumptions (A1) and (A2) hold. Then any sequence \(\{x^{k}\}\) generated by (3.4) converges weakly to a solution of the SFP (1.1).

Proof

Let \(x^{*}\) be a solution of the SFP. Since \(C\subseteq C_k\), \(Q \subseteq Q_k\), then \(x^{*}=P_{C}(x^{*}) = P_{C_k}(x^{*})\) and \(Ax^{*} = P_{Q}(Ax^{*}) = P_{Q_k}(Ax^{*})\).

These facts imply that \(F_{k}(x^{*}) = 0\). Following Lemma 2.1(iii), we have

$$\begin{aligned} \Vert x^{k+1} - x^{*} \Vert ^2&= \left\| P_{C_k}\left( x^k - \alpha _k F_k (\overline{x}^k)\right) - x^* \right\| ^2 \nonumber \\&\le \left\| x^k - \alpha _k F_k (\overline{x}^k) - x^* \right\| ^2 - \left\| x^{k+1} - x^k + \alpha _k F_k (\overline{x}^k)\right\| ^2 \nonumber \\&=\left\| x^k - x^*\right\| ^2 - 2\alpha _k \left\langle F_k(\overline{x}^k), x^k - x^* \right\rangle - \left\| x^{k+1} - x^k \right\| ^2 \nonumber \\&\quad - 2 \alpha _k\left\langle F_k (\overline{x}^k), x^{k+1} - x^k \right\rangle \nonumber \\&= \left\| x^k - x^* \right\| ^2 - 2\alpha _k \left\langle F_k(\overline{x}^k), x^k - \overline{x}^k \right\rangle - 2\alpha _k \left\langle F_k(\overline{x}^k), \overline{x}^k - x^* \right\rangle \nonumber \\&\quad - \left\| x^{k+1} - x^k \right\| ^2 - 2 \alpha _k \left\langle F_k (\overline{x}^k), x^{k+1} - x^k \right\rangle \nonumber \\&= \left\| x^k - x^* \right\| ^2 - 2\alpha _k \left\langle F_k(\overline{x}^k), \overline{x}^k - x^* \right\rangle - 2\alpha _k \left\langle F_k(\overline{x}^k), x^{k+1}-\overline{x}^k \right\rangle \nonumber \\&\quad -\left\| x^{k+1} - \overline{x}^k + \overline{x}^k - x^k \right\| ^2 \nonumber \\&= \left\| x^k - x^* \right\| ^2 - 2\alpha _k \left\langle F_k(\overline{x}^k), \overline{x}^k - x^* \right\rangle -\left\| x^{k+1} - \overline{x}^k \right\| ^2 \nonumber \\&\quad -\left\| \overline{x}^k - x^k \right\| ^2 - 2 \left\langle \overline{x}^k - x^k + \alpha _k F_k(\overline{x}^k), x^{k+1} - \overline{x}^k \right\rangle . \end{aligned}$$
(3.6)

It follows from (2.2) and \(F_{k}(x^{*}) = 0\) that

$$\begin{aligned} 2 \alpha _k \left\langle F_k (\overline{x}^k), \overline{x}^k - x^* \right\rangle&= 2\alpha _k \left\langle F_k (\overline{x}^k) - F_k(x^*) , \overline{x}^k - x^* \right\rangle \nonumber \\&= 2 \alpha _k \langle A^*(I - P_{Q_k})A\overline{x}^k - A^*(I - P_{Q_k})Ax^*, \overline{x}^k - x^* \rangle \nonumber \\&= 2 \alpha _k \left\langle (I - P_{Q_k})A\overline{x}^k - (I-P_{Q_k})Ax^*, A\overline{x}^k - Ax^* \right\rangle \nonumber \\&\ge 2 \frac{\mu l}{L}\left\| (I-P_{Q_k})A\overline{x}^k \right\| ^2. \end{aligned}$$
(3.7)

Using Lemma 2.1(i) and the definition of \(\overline{x}^{k}\) (\(\overline{x}^{k}\in C_k)\) , we have

$$\begin{aligned} \left\langle \overline{x}^k - x^k + \alpha _k F_{k}(x^k), x^{k+1} - \overline{x}^k \right\rangle \ge 0. \end{aligned}$$
(3.8)

By virtue of the above inequality, for the last term of (3.6), we have

$$\begin{aligned}&-2 \left\langle \overline{x}^k - x^k + \alpha _k F_k(\overline{x}^k), x^{k+1} - \overline{x}^k \right\rangle \nonumber \\&\quad \le 2 \left\langle x^k -\overline{x}^k - \alpha _k F_k(\overline{x}^k), x^{k+1} - \overline{x}^k \right\rangle + 2\left\langle \overline{x}^k - x^k + \alpha _k F_{k}(x^k), x^{k+1} - \overline{x}^k\right\rangle \nonumber \\&\quad = 2 \alpha _k \left\langle F_k(x^k) - F_k (\overline{x}^k), x^{k+1} -\overline{x}^k \right\rangle \nonumber \\&\quad \le 2 \alpha _k \left\| F_k(x^k) - F_k (\overline{x}^k)\right\| \left\| x^{k+1} - \overline{x}^k \right\| \nonumber \\&\quad \le \alpha _{k}^{2} \left\| F_k(x^k) - F_k (\overline{x}^k)\right\| ^2 +\left\| x^{k+1} - \overline{x}^k \right\| ^2 \nonumber \\&\quad \le \mu ^2 \left\| x^{k} - \overline{x}^k \right\| ^2 + \left\| x^{k+1} - \overline{x}^k \right\| ^2. \end{aligned}$$
(3.9)

Combining (3.7)–(3.9) and (3.6), we obtain

$$\begin{aligned} \left\| x^{k+1} - x^*\right\| ^2&\le \left\| x^{k} - x^*\right\| ^2 - \frac{2\mu l}{L}\left\| (I- P_{Q_k})A\overline{x}^k \right\| ^2 \nonumber \\&\quad -(1-\mu ^2)\left\| x^k - \overline{x}^k \right\| ^2, \end{aligned}$$
(3.10)

which implies that

$$\begin{aligned} \left\| x^{k+1} - x^*\right\| \le \left\| x^{k} - x^*\right\| . \end{aligned}$$

Thus \(\lim _{k\rightarrow \infty }\Vert x^{k} - x^*\Vert \) exists and moreover, \(\{x^k\}\) is bounded.

Now, from (3.10), it follows that

$$\begin{aligned} \lim _{k\rightarrow \infty }\left\| x^k - \overline{x}^k \right\| =0, \end{aligned}$$
(3.11)

and

$$\begin{aligned} \lim _{k\rightarrow \infty } \left\| (I - P_{Q_k})A\overline{x}^k \right\| = 0. \end{aligned}$$
(3.12)

Furthermore,

$$\begin{aligned} \left\| x^{k+1} - x^{k} \right\|&\le \left\| x^{k+1} - \overline{x}^k\right\| + \left\| \overline{x}^k - x^k \right\| \nonumber \\&= \left\| P_{C_k}\left( x^k - \alpha _k F_{k}(\overline{x}^{k})\right) - P_{C_{k}} \left( x^{k} - \alpha _{k}F_{k}(x^{k}) \right) \right\| +\left\| \overline{x}^k - x^k \right\| \nonumber \\&\le \alpha _k \left\| F_k (\overline{x}^k) - F_k (x^k) \right\| + \left\| \overline{x}^k - x^k \right\| \nonumber \\&\le (1+\mu ) \left\| \overline{x}^k - x^k \right\| . \end{aligned}$$
(3.13)

By taking \(k\rightarrow \infty \) in the above inequality and using (3.11), we obtain

$$\begin{aligned} \lim _{k\rightarrow \infty } \left\| x^{k+1} - x^k \right\| = 0. \end{aligned}$$
(3.14)

Since \(\{x^k\}\) is bounded, the set \(\omega _{w}(x^k)\) is nonempty. Let \(\widehat{x}\in \omega _{w}(x^k)\), then there exists a subsequence \(\{x^{k_n}\}\) of \(\{x^k\}\) such that \(x^{k_n}\rightharpoonup \widehat{x}\). Next, we show that \(\widehat{x}\) is a solution of the SFP (1.1), which will show that \(\omega _{w}(x^k) \subseteq \Omega \). In fact, since \(x^{k_n +1}\in C_{k_n}\), then by the definition of \(C_{k_n}\), we have

$$\begin{aligned} c(x^{k_n}) + \left\langle \xi ^{k_n}, x^{k_n +1} - x^{k_n} \right\rangle \le 0, \end{aligned}$$
(3.15)

where \(\xi ^{k_n}\in \partial c(x^{k_n})\). Following the assumption (A1) on the boundedness of \(\{\xi ^{k_n}\}\) and (3.14), we have

$$\begin{aligned} c(x^{k_n})&\le \left\langle \xi ^{k_n}, x^{k_n} - x^{k_n +1} \right\rangle \nonumber \\&\le \Vert \xi ^{k_n}\Vert \left\| x^{k_n} - x^{k_n +1}\right\| \nonumber \\&\rightarrow 0, \text { as }\ k_n \rightarrow \infty . \end{aligned}$$
(3.16)

From the weak lower-semicontinousness of the convex function c(x) and since \(x^{k_n}\rightharpoonup \widehat{x}\), we deduce from (3.16) that,

$$\begin{aligned} c(\widehat{x}) \le \liminf _{k_n \rightarrow \infty }c(x^{k_n}) \le 0, \end{aligned}$$
(3.17)

i.e., \(\widehat{x}\in C\).

The fact that \(I-P_{Q_k}\) is nonexpansive, together with (3.11) and (3.12), we get that

$$\begin{aligned}&\left\| (I - P_{Q_k})Ax^k\right\| \nonumber \\&\quad \le \left\| (I - P_{Q_k})Ax^k - (I - P_{Q_k})A\overline{x}^k \right\| + \left\| (I - P_{Q_k})A\overline{x}^k \right\| \nonumber \\&\quad \le \Vert A\Vert \left\| x^k - \overline{x}^k\right\| + \left\| (I - P_{Q_k})A\overline{x}^k \right\| \nonumber \\&\quad \rightarrow 0, \text { as }\ k\rightarrow \infty . \end{aligned}$$
(3.18)

Since \(P_{Q_{k_n}}(Ax^{k_n})\in Q_{k_n}\), we have

$$\begin{aligned} q(Ax^{k_n}) + \left\langle \eta ^{k_n}, P_{Q_{k_n}}(Ax^{k_n}) - Ax^{k_n}\right\rangle \le 0, \end{aligned}$$
(3.19)

where \(\eta ^{k_n}\in \partial q(Ax^{k_n})\). From the boundedness assumption (A1) of \(\{\eta ^{k_n}\}\) and (3.18), we have

$$\begin{aligned} q(Ax^{k_n}) \le \Vert \eta ^{k_n}\Vert \left\| Ax^{k_n} - P_{Q_{k_n}}(Ax^{k_n})\right\| \rightarrow 0, \text { as }\ k_n \rightarrow \infty . \end{aligned}$$
(3.20)

Similarly, we obtain that \(q(A\widehat{x}) \le 0\), which means that \(A\widehat{x}\in Q\). Using Lemma 2.2, we conclude that the sequence \(\{x^k\}\) converges weakly to a solution of the SFP (1.1), and the desired result is obtained. \(\square \)

Remark 3.1

  1. (1)

    Theorem 3.1 extends the main result of Qu and Xiu [11] to infinite dimensional Hilbert spaces. For Euclidean spaces, our proof coincides with the proof of Qu and Xiu.

  2. (2)

    For the special case where \(Q= Q_k = \{b\}\), (3.18) reduces to \(\Vert Ax^k -b\Vert \rightarrow 0\) as \(k\rightarrow \infty \), which means that the sequences \(\{Ax^k\}\) converge to (data vector) b.

4 Applications and numerical experiments

In this section, we apply the modified relaxation CQ algorithm with an Armijo-line search to solve the LASSO problem. Let us first recall the LASSO problem [21] which is the following.

$$\begin{aligned} \begin{aligned} \min _{x\in R^{n}}\&\frac{1}{2} \Vert Ax-b\Vert _{2}^{2}, \\ s.t. \&\Vert x\Vert _{1} \le t, \end{aligned} \end{aligned}$$
(4.1)

where \(A\in R^{m\times n}\), \(b\in R^{m}\) and \(t> 0 \) is a given constant. This problem, (4.1) exhibits the potential of finding a sparse solution of the SFP (1.1) due to the \(\ell _1\) constraint. The LASSO problem is strongly related to the Basis Pursuit denosing problem [22] which has wide application in signal processing theory.

Table 1 Numerical results obtained by the relaxed CQ algorithm [10] and the modified CQ algorithm when \(m =120, n =512\)
Full size table
Table 2 Numerical results obtained by the relaxed CQ algorithm [10] and the modified CQ algorithm when \(m = 240, n = 1024\)
Full size table

Let \(C := \{ x | \Vert x\Vert _{1} \le t \}\) and \(Q=\{b\}\), then the minimization problem (4.1) can be seen as an SFP (1.1). So, we define the convex function \(c(x) = \Vert x\Vert _{1} - t\) and denote the level set \(C_k\) by,

$$\begin{aligned} C_k = \left\{ x | c(x^k) + \langle \xi ^k , x- x^k \rangle \le 0 \right\} , \end{aligned}$$
(4.2)

where \(\xi ^k \in \partial c(x^k)\). The orthogonal projection onto \(C_k\) can be calculated by the following,

$$\begin{aligned} P_{C_k}(y) = {\left\{ \begin{array}{ll} y, &{}\quad \text {if } c(x^k) + \langle \xi ^k, y - x^k \rangle \le 0,\\ y - \frac{c(x^k) + \langle \xi ^k , y - x^k \rangle }{\Vert \xi ^k\Vert ^2} \xi ^k,&{}\quad \text {otherwise}. \end{array}\right. } \end{aligned}$$
(4.3)

The subdifferential \(\partial c\) at \(x^k\) is

$$\begin{aligned} \partial c(x^k)= {\left\{ \begin{array}{ll} 1, &{}\quad x^k >0,\\ {[}-1,1], &{}\quad x^k = 0 ,\\ -1, &{}\quad x^k <0. \end{array}\right. } \end{aligned}$$
(4.4)

It follows from Remark 3.1(2) that the modified relaxation CQ algorithm converges to the solution of the LASSO problem (4.1) and moreover, due to the formulas of \(P_{C_k}(y)\) and \(\partial c(x^k)\), the modified relaxation CQ algorithm can be easily implemented. In the following, we present a sparse signal recovery experiment to demonstrate the efficiency of the modified relaxation CQ algorithm. We also compare the modified relaxation CQ algorithm with the relaxed CQ iterative algorithm proposed by Yang [10]. We would also like to point out that the projected gradient method is also an efficient way to solve the LASSO problem (4.1). Although it requires projection onto the \(\ell _1\) constraint set, and there exists no close formula for it, still it can be evaluated in a polynomial time. There is also commercial software, based on the projected gradient method for solving the LASSO problem, for example SPGL1 [23] and FASTA [24], but this is beyond the scope of this paper. Since the relaxed CQ algorithm [10] and the modified relaxation CQ algorithm with an Armijo-line search use subgradient projection, they both propose an alternative way to solve the LASSO problem and their natures also differ from the projected gradient method.

4.1 Numerical results

In this subsection, we present numerical examples comparing the relaxed CQ algorithm [10] and the modified relaxation CQ algorithm with Armijo-line search. For simplicity, we call the modified relaxation CQ algorithm with Armijo-line search the modified CQ algorithm.

Fig. 1
figure 1

The recovered sparse signal versus the original K-sparse signal, where \(m=120, n = 512\) and \(K=30\)

Full size image
Fig. 2
figure 2

The recovered sparse signal vs the original K-sparse signal, where \(m=240, n = 1024\) and \(K=60\)

Full size image

We are given the following data. The vector \(x\in R^n\) is a K-sparse signal that is generated from uniform distribution in the interval \([-2,2]\) with K non-zero elements. The matrix \(A\in R^{m\times n}\) is generated from a normal distribution with mean zero and one variance. The vector b is taken as equal to Ax, so no noise is assumed. The goal is then to recover the K-sparse signal x by solving the LASSO problem (4.1). All the numerical results are completed on a standard Lenovo laptop with Intel(R) Core(TM) i7-4712MQ CPU 2.3GHz with 4 GB memory. The programme is implemented in MATLAB 2013a.

For the modified CQ algorithm, we set the corresponding iterative parameters \(\gamma =1\), \(l=\mu = 0.5\). We choose the constant stepsize \(0.9*(2/L)\) for the relaxed CQ algorithm [10]. We define the stopping criteria,

$$\begin{aligned} \Vert x^{k+1} -x^k \Vert \le \epsilon , \end{aligned}$$
(4.5)

where \(\epsilon >0\) is a given small constant. The iteration numbers (“Iter”), the objective function value (“Obj”) and the 2-norm error between the recovered solution and the true K-sparse solution (“Err”) are reported when the stopping criteria is reached. The obtained numerical results are listed in Tables 1 and 2, and show that for the given example, both methods are very effective. In Figs. 1 and 2 we plot the exact K-sparse signal against the recovered signals obtained by the two methods when the stopping criteria \(\epsilon = 10^{-8}\). In Fig. 3 we also plot the objective functions value per iterations. It can be seen in Fig. 3 that the objective function values obtained by the modified CQ algorithm decrease faster than the values obtained by the relaxed CQ algorithm.

Fig. 3
figure 3

The objective function value versus the iteration numbers. Left the objective function value is taken from the results of Table 1 when \(K=30\). Right the objective function value is taken from the results of Table 2 when \(K=60\)

Full size image

5 Conclusions

In this note we study the modified relaxation CQ algorithm which is designed to solve the split feasibility problem (1.1) in real Hilbert spaces. We show in a simple and novel way how the sequence generated by the method weakly converges to a solution of the SFP. The effectiveness of the method is illustrated for solving the LASSO problem (4.1) of recovering a K-sparse signal from a limited number of observations. All the results are compared with the Yang’s [10] relaxed CQ algorithm. For future directions of research we aim to study the method in Banach spaces with other kind of projections; for example Bregman projections, see [25, 26].