# Regularized Methods for the Split Feasibility Problem

Authors: Yonghong Yao; Wu Jigang; Yeong-Cheng Liou
Journal: Abstract and Applied Analysis
 (2012)

---

## Abstract

Many applied problems such as image reconstructions and signal processing can
be formulated as the split feasibility problem (SFP). Some algorithms have been introduced in the literature for solving the (SFP). In this paper, we will continue to consider the convergence analysis of the regularized methods for the (SFP). Two
regularized methods are presented in the present paper. Under some different control
conditions, we prove that the suggested algorithms strongly converge to the minimum
norm solution of the (SFP).


---

## Body

## 1. Introduction

The well-known convex feasibility problem is to find a pointx* satisfying the following:(1.1)x*∈⋂i=1mCi,
where m≥1 is an integer, and each Ci is a nonempty closed convex subset of a Hilbert space H. Note that the convex feasibility problem has received a lot of attention due to its extensive applications in many applied disciplines as diverse as approximation theory, image recovery and signal processing, control theory, biomedical engineering, communications, and geophysics (see [1–3] and the references therein).A special case of the convex feasibility problem is the split feasibility problem (SFP) which is to find a pointx* such that(1.2)x*∈C,Ax*∈Q,
where C and Q are two closed convex subsets of two Hilbert spaces H1 and H2, respectively, and A:H1→H2 is a bounded linear operator. We use Γ to denote the solution set of the (SFP), that is,(1.3)Γ={x∈C:Ax∈Q}.
Assume that the (SFP) is consistent. A special case of the (SFP) is the convexly constrained linear inverse problem ([4]) in the finite dimensional Hilbert spaces(1.4)x*∈C,Ax*=b
which has extensively been investigated by using the Landweber iterative method ([5]):(1.5)Withx0arbitraryandn=0,1,…,letxn+1=xn+γAT(b-Axn).The (SFP) in finite-dimensional Hilbert spaces was first introduced by Censor and Elfving [6] for modeling inverse problems which arise from phase retrievals and in medical image reconstruction. The original algorithm introduced in [6] involves the computation of the inverse A-1:(1.6)xk+1=A-1PQ(PA(C)(Axk)),k≥0,
where C,Q⊂Rn are closed convex sets, A a full rank n×n matrix, and A(C)={y∈Rn∣y=Ax,x∈C} and thus does not become popular. A more popular algorithm that solves the (SFP) seems to be the CQ algorithm of Byrne ([7, 8]). The CQ algorithm only involves the computations of the projections PC and PQ onto the sets C and Q, respectively, and is therefore implementable in the case where PC and PQ have closed-form expressions (e.g., C and Q are the closed balls or half-spaces). There are a large number of references on the CQ method for the (SFP) in the literature, see, for instance, [9–19]. It remains, however; a challenge how to implement the CQ algorithm in the case where the projections PC and/or PQ fail to have closed-form expressions though theoretically we can prove (weak) convergence of the algorithm.Note thatx∈Γ means that there is an x∈C such that Ax-x*=0 for some x*∈Q. This motivates us to consider the distance function d(Ax,x*)=∥Ax-x*∥ and the minimization problem(1.7)min⁡x∈C,x*∈Q12‖Ax-x*‖2.
Minimizing with respect to x*∈Q first makes us consider the minimization:(1.8)min⁡x∈Cf(x)∶=12‖Ax-PQAx‖2.
However, (1.8) is, in general, ill posed. So regularization is needed. We consider Tikhonov’s regularization(1.9)min⁡x∈Cfα∶=12‖(I-PQ)Ax‖2+12α‖x‖2,
where α>0 is the regularization parameter. We can compute the gradient ∇fα of fα as(1.10)∇fα=∇f(x)+αI=A*(I-PQ)A+αI.
Define a Picard iterates(1.11)xn+1α=PC(I-γ(A*(I-PQ)A+αI))xnα
Xu [20] shown that if the (SFP) (1.2) is consistent, then as n→∞,xnα→xα, and consequently the strong limα→0xα exists and is the minimum-norm solution of the (SFP). Note that (1.11) is a double-step iteration. Xu [20] further suggested a single step-regularized method:(1.12)xn+1=PC(I-γn∇fαn)xn=PC((1-αnγn)xn-γnA*(I-PQ)Axn).
Xu proved that the sequence {xn} converges in norm to the minimum-norm solution of the (SFP) provided that the parameters {αn} and {γn} satisfy the following conditions:(i)
αn→0 and 0<γn≤αn/(∥A∥2+αn),(ii)
∑nαnγn=∞,(iii)
(|γn+1-γn|+γn|αn+1-αn|)/(αn+1γn+1)2→0.Recently, the minimum-norm solution and the minimization problems have been considered extensively in the literature. For related works, please see [21–29]. The main purpose of this paper is to further investigate the regularized method (1.12). Under some different control conditions, we prove that this algorithm strongly converges to the minimum norm solution of the (SFP). We also consider an implicit method for finding the minimum norm solution of the (SFP).


## 2. Preliminaries

LetC be a nonempty closed convex subset of a real Hilbert space H. A mapping T:C→C is called nonexpansive if(2.1)‖Tx-Ty‖≤‖x-y‖,∀x,y∈C.
We will use Fix(T) to denote the set of fixed points of T, that is, Fix(T)={x∈C:x=Tx}. A mapping T:C→C is said to be ν-inverse strongly monotone (ν-ism) if there exists a constant ν>0 such that(2.2)〈x-y,Tx-Ty〉≥ν‖Tx-Ty‖2,∀x,y∈C.
Recall that the (nearest point or metric) projection from H onto C, denoted PC, assigns, to each x∈H, the unique point PC(x)∈C with the property(2.3)‖x-PC(x)‖=inf⁡{‖x-y‖:y∈C}.
It is well known that the metric projection PC of H onto C has the following basic properties:(a)
∥PC(x)-PC(y)∥≤∥x-y∥ for all x,y∈H,(b)
〈x-y,PC(x)-PC(y)〉≥∥PC(x)-PC(y)∥2 for every x,y∈H,(c)
〈x-PC(x),y-PC(x)〉≤0 for all x∈H, y∈C.Next we adopt the following notation:(i)
xn→x means that xn converges strongly to x,(ii)
xn⇀x means that xn converges weakly to x,(iii)
ωw(xn):={x:∃xnj⇀x} is the weak ω-limit set of the sequence {xn}.Lemma 2.1 (see [20]).
Given thatx*∈H1. x* solves the (SFP) if and only if x* solves the fixed point equation
(2.4)x*=PC(x*-γA*(I-PQ)Ax*).Lemma 2.2 (see [8, 20]).
We have the following assertions.(a)
T is nonexpansive if and only if the complement I-T is 1/2-ism.(b)
IfS is ν-ism, then for γ>0, γS is ν/γ-ism.(c)
S is averaged if and only if the complement I-S is ν-ism for some ν>1/2.(d)
IfS and T are both averaged, then the product (composite) ST is averaged.Lemma 2.3 (see [30] Demiclosedness Principle).
LetC be a closed and convex subset of a Hilbert space H and let T:C→C be a nonexpansive mapping with Fix(T)≠∅. If {xn} is a sequence in C weakly converging to x and if {(I-T)xn} converges strongly to y, then
(2.5)(I-T)x=y.
In particular, if y=0, then x∈Fix(T).Lemma 2.4 (see [31]).
Let{xn} and {yn} be bounded sequences in a Banach space X and let {βn} be a sequence in [0,1] with
(2.6)0<liminf⁡n→∞βn≤limsup⁡n→∞βn<1.
Suppose that
(2.7)xn+1=(1-βn)yn+βnxn
for all n≥0 and
(2.8)limsup⁡n→∞(‖yn+1-yn‖-‖xn+1-xn‖)≤0.
Then, limn→∞∥yn-xn∥=0.Lemma 2.5 (see [32]).
Assume that{an} is a sequence of nonnegative real numbers such that
(2.9)an+1≤(1-γn)an+δn,
where {γn} is a sequence in (0,1) and {δn} is a sequence such that(1)
∑n=1∞γn=∞,(2)
limsupn→∞δn/γn≤0 or ∑n=1∞|δn|<∞. Then limn→∞an=0.


## 3. Main Results

In this section, we will state and prove our main results.Theorem 3.1.
Assume that the (SFP) (1.2) is consistent. Let {xn} be a sequence generated by the following algorithm:
(3.1)xn+1=PC((1-αnγn)xn-γnA*(I-PQ)Axn),n≥0,
where the sequences {αn}⊂(0,1) and {γn}⊂(0,(2)/(∥A∥2+2αn) satisfy the following conditions:(C1)
limn→∞αn=0 and ∑n=0∞αn=∞,(C2)
liminfn→∞γn>0 and limn→∞(γn+1-γn)=0.Then the sequence {xn} generated by (3.1) strongly converges to the minimum norm solution x̂ of the (SFP) (1.2).Proof.
It is known thatA*(I-PQ)A is 1/∥A∥2-ism. Then, we have
(3.2)‖PC((1-αγ)x-γA*(I-PQ)Ax)-PC((1-αγ)y-γA*(I-PQ)Ay)‖2≤‖(1-αγ)(x-y)-γ(A*(I-PQ)Ax-A*(I-PQ)Ay)‖2=(1-αγ)2‖x-y‖2-2(1-αγ)γ〈x-y,A*(I-PQ)Ax-A*(I-PQ)Ay〉+γ2‖A*(I-PQ)Ax-A*(I-PQ)Ay‖2≤(1-αγ)2‖x-y‖2-2(1-αγ)γ1‖A‖2‖A*(I-PQ)Ax-A*(I-PQ)Ay‖2+γ2‖A*(I-PQ)Ax-A*(I-PQ)Ay‖2.
If γ∈[0,(2)/∥A∥2+2α], then 2(1-αγ)γ(1/∥A∥2)≥γ2. It follows that
(3.3)‖PC((1-αγ)x-γA*(I-PQ)Ax)-PC((1-αγ)y-γA*(I-PQ)Ay)‖2≤(1-αγ)2‖x-y‖2.
Thus, PC(I-γ(A*(I-PQ)A+αI)) is a contractive mapping with coefficient ρ≤1-αγ.
Pick up anyx*∈Γ. From Lemma 2.1, x*∈C solves the (SFP) if and only if x*=PC(I-γA*(I-PQ)A)x* for any fixed positive number γ. So, we have x*=PC(I-γnA*(I-PQ)A)x* for all n≥0. From (3.1), we get
(3.4)‖xn+1-x*‖=‖PC(I-γn(A*(I-PQ)A+αnI))xn-PC(I-γnA*(I-PQ)A)x*‖≤‖PC(I-γn(A*(I-PQ)A+αnI))xn-PC(I-γn(A*(I-PQ)A+αnI))x*‖+‖PC(I-γn(A*(I-PQ)A+αnI))x*-PC(I-γnA*(I-PQ)A)x*‖≤(1-αnγn)‖xn-x*‖+αnγn‖x*‖≤max⁡{‖xn-x*‖,‖x*‖}.
By induction, we deduce
(3.5)‖xn-x*‖≤max⁡{‖x0-x*‖,‖x*‖}.
This indicates that the sequence {xn} is bounded.
SinceA*(I-PQ)A is ∥A∥2∥-Lipschitz, A*(I-PQ)A is 1/∥A∥2-ism, which then implies that γA*(I-PQ)A is 1/γ∥A∥2-ism. So by Lemma 2.1, I-γnA*(I-PQ)A is γn∥A∥2/2 averaged. That is, I-γnA*(I-PQ)A=(1-(γn∥A∥2/2))I+(γn∥A∥2/2)T for some nonexpansive mapping T. Since PC is 1/2 averaged, PC=(I+S)/2 for some nonexpansive mapping S. Then, we can rewrite xn+1 as
(3.6)xn+1=12(I-γn(A*(I-PQ)A+αnI))xn+12S(I-γn(A*(I-PQ)A+αnI))xn=12(xn-γnA*(I-PQ)Axn)-12γnαnxn+12S(I-γn(A*(I-PQ)A+αnI))xn=2-γn‖A‖24xn+γn‖A‖24Txn-12γnαnxn+12S(I-γn(A*(I-PQ)A+αnI))xn=2-γn‖A‖24xn+2+γn‖A‖24yn,
where
(3.7)yn=42+γn‖A‖2(γn‖A‖24Txn-12γnαnxn+12S(I-γn(A*(I-PQ)A+αnI))xn).
It follows that
(3.8)∥yn+1-yn∥=‖42+γn+1‖A‖2(γn+1‖A‖24Txn+1-12γn+1αn+1xn+1+12S(I-γn+1(A*(I-PQ)A+αn+1I))xn+1γn+1‖A‖24)-42+γn‖A‖2(γn‖A‖24Txn-12γnαnxn+12S(I-γn(A*(I-PQ)A+αnI))xn)‖≤42+γn+1‖A‖2‖(γn+1‖A‖24Txn+1-12γn+1αn+1xn+1+12S(I-γn+1(A*(I-PQ)A+αn+1I))xn+1γn+1‖A‖24)-(γn‖A‖24Txn-12γnαnxn+12S(I-γn(A*(I-PQ)A+αnI))xn)‖+|42+γn+1‖A‖2-42+γn‖A‖2|‖γn‖A‖24Txn-12γnαnxn+12S(I-γn(A*(I-PQ)A+αnI))xnγn‖A‖24‖≤42+γn+1‖A‖2(‖γn+1‖A‖24Txn+1-γn‖A‖24Txn‖+12γn+1αn+1‖xn+1‖+12γnαn‖xn‖)+22+γn+1‖A‖2‖(I-γn+1(A*(I-PQ)A+αn+1I))xn+1-(I-γn(A*(I-PQ)A+αnI))xn‖+|42+γn+1‖A‖2-42+γn‖A‖2|‖γn‖A‖24Txn-12γnαnxn+12S(I-γn(A*(I-PQ)A+αnI))xnγn‖A‖24‖
Now we choose a constant M such that
(3.9)sup⁡n{γn‖A‖24‖xn‖,‖A‖2‖Txn‖,‖A*(I-PQ)Axn‖,‖γn‖A‖24Txn-12γnαnxn+12S(I-γn(A*(I-PQ)A+αnI))xn‖}≤M.
We have the following estimates:
(3.10)‖γn+1‖A‖24Txn+1-γn‖A‖24Txn‖=‖γn+1‖A‖24(Txn+1-Txn)+(γn+1‖A‖24-γn‖A‖24)Txn‖≤γn+1‖A‖24‖Txn+1-Txn‖+|γn+1-γn|‖A‖2‖Txn‖4≤γn+1‖A‖24‖xn+1-xn‖+|γn+1-γn|M,‖(I-γn+1(A*(I-PQ)A+αn+1I))xn+1-(I-γn(A*(I-PQ)A+αnI))xn‖≤‖(I-γn+1A*(I-PQ)A)xn+1-(I-γn+1A*(I-PQ)A)xn‖+|γn+1-γn|‖A*(I-PQ)A(xn)‖+γn+1αn+1‖xn+1‖+γnαn‖xn‖≤‖xn+1-xn‖+(|γn+1-γn|+γn+1αn+1+γnαn)M.
Thus, we deduce that
(3.11)‖yn+1-yn‖≤42+γn+1‖A‖2(γn+1‖A‖24‖xn+1-xn‖+|γn+1-γn|M+(γn+1αn+1+γnαn)M)+22+γn+1‖A‖2(‖xn+1-xn‖+(|γn+1-γn|+γn+1αn+1+γnαn)M)+|42+γn+1‖A‖2-42+γn‖A‖2|M≤‖xn+1-xn‖+62+γn+1‖A‖2(|γn+1-γn|+γn+1αn+1+γnαn)M+4‖A‖2(2+γn+1‖A‖2)(2+γn‖A‖2)|γn+1-γn|M.
Note that αn→0 and γn+1-γn→0. Hence, by Lemma 2.3, we get the following:
(3.12)limsup⁡n→∞(‖yn+1-yn‖-‖xn+1-xn‖)≤0.
It follows that
(3.13)lim⁡n→∞‖yn-xn‖=0.
Consequently,
(3.14)lim⁡n→∞‖xn+1-xn‖=lim⁡n→∞2+γn‖A‖24‖yn-xn‖=0.
Now we show that the weak limit set ωw(xn)⊂Γ. Choose any x̃∈ωw(xn). Since {xn} is bounded, there must exist a subsequence {xnj} of {xn} such that xnj⇀x̃. At the same time, the real number sequence {γnj} is bounded. Thus, there exists a subsequence {γnji} of {γnj} which converges to γ. Without loss of generality, we may assume that γnj→γ. Note that 0<liminfn→∞γn≤limsupn→∞γn<2/∥A∥2. So, γ∈(0,2/∥A∥2). That is, γnj→γ∈(0,2/∥A∥2) as j→∞. Next, we only need to show that x̃∈Γ. First, from (3.14) we have that ∥xnj+1-xnj∥→0. Then, we have the following:
(3.15)‖xnj-PC(I-γA*(I-PQ)A)xnj‖≤‖xnj-xnj+1‖+‖xnj+1-PC(I-γnjA*(I-PQ)A)xnj‖+‖PC(I-γnjA*(I-PQ)A)xnj-PC(I-γA*(I-PQ)A)xnj‖=‖PC(I-γnj(A*(I-PQ)A+αnjI))xnj-PC(I-γnjA*(I-PQ)A)xnj‖+‖PC(I-γnjA*(I-PQ)A)xnj-PC(I-γA*(I-PQ)A)xnj‖+‖xnj-xnj+1‖≤αnjγnj‖xnj‖+|γnj-γ|‖A*(I-PQ)A(xnj)‖+‖xnj-xnj+1‖⟶0.
Since γ∈(0,2/∥A∥2),PC(I-γA*(I-PQ)A) is nonexpansive. It then follows from Lemma 2.4 (demiclosedness principle) that x̃∈Fix(PC(I-γA*(I-PQ)A)). Hence, x̃∈Γ because Ω=Fix(PC(I-γA*(I-PQ)A)). So, ωw(xn)⊂Γ.
Finally, we prove thatxn→x̂, where x̂ is the minimum norm solution of (1.2). First, we show that limsupn→∞〈x̂,xn-x̂〉≥0. Observe that there exists a subsequence {xnj} of {xn} satisfying that
(3.16)limsup⁡n→∞〈x̂,xn-x̂〉=lim⁡j→∞〈x̂,xnj-x̂〉.
Since {xnj} is bounded, there exists a subsequence {xnji} of {xnj} such that xnji⇀x̃. Without loss of generality, we assume that xnj⇀x̃. Then, we obtain the following:
(3.17)limsup⁡n→∞〈x̂,xn-x̂〉=lim⁡j→∞〈x̂,xnj-x̂〉=〈x̂,x̃-x̂〉≥0.
Since γn<2/(∥A∥2+2αn),γn/(1-αnγn)<2/∥A∥2. So, I-(γn/(1-αnγn))A*(I-PQ)A is nonexpansive. By using the property (b) of PC, we have the following:
(3.18)‖xn+1-x̂‖2=‖PC(I-γn(A*(I-PQ)A+αnI))xn-PC(x̂-γnA*(I-PQ)Ax̂)‖2≤〈(I-γn(A*(I-PQ)A+αnI))xn-(x̂-γnA*(I-PQ)Ax̂),xn+1-x̂〉=(1-αnγn)〈(I-γn1-αnγnA*(I-PQ)A)xn-(I-γn1-αnγnA*(I-PQ)A)x̂,xn+1-x̂〉-αnγn〈x̂,xn+1-x̂〉≤(1-αnγn)‖(I-γn1-αnγnA*(I-PQ)A)xn-(I-γn1-αnγnA*(I-PQ)A)x̂‖‖xn+1-x̂‖-αnγn〈x̂,xn+1-x̂〉≤(1-αnγn)‖xn-x̂‖‖xn+1-x̂‖-αnγn〈x̂,xn+1-x̂〉≤1-αnγn2‖xn-x̂‖2+12‖xn+1-x̂‖2-αnγn〈x̂,xn+1-x̂〉.
It follows that
(3.19)‖xn+1-x̂‖2≤(1-αnγn)‖xn-x̂‖2+αnγn〈-x̂,xn+1-x̂〉.
From Lemma 2.5, (3.17), and (3.19), we deduce that xn→x̂. This completes the proof.Remark 3.2.
We obtain the strong convergence of the regularized method (3.1) under control conditions (C1) and (C2). In Xu’s [20] result, γn→0. However, in our result, liminfn→0γn>0.
Finally, we introduce an implicit method for the (SFP).
Take a constantγ such that 0<γ<2/∥A∥2. For t∈(0,1), we define a mapping(3.20)Wt∶=PC[I-γ(A*(I-PQ)A+tI)],t∈(0,2-γ‖A‖22γ).
For t∈(0,1), we know that A*(I-PQ)A+tI is (t+∥A∥2)-Lipschitz and t-strongly monotone. Thus, Wt=PC(I-γ(A*(I-PQ)A+tI)) is a contractive. So, Wt has a unique fixed point in C, denoted by xt, that is,
(3.21)xt=PC[xt-γ(A*(I-PQ)Axt+txt)],t∈(0,2-γ‖A‖22γ).
Next, we show the convergence of the net {xt} defined by (3.21).Theorem 3.3.
Assume that the (SFP) (1.2) is consistent. As t→0+, the net {xt} defined by (3.21) converges to the minimum norm solution of the (SFP).Proof.
Letx̃ be any a point in Γ. We can rewrite (3.21) as
(3.22)xt=PC[(1-tγ)xt-γA*(I-PQ)Axt],t∈(0,2-γ‖A‖22γ).
Since t∈(0,(2-γ∥A∥2)/2γ),I-(γ/(1-tγ))A*(I-PQ)A is nonexpansive. It follows that
(3.23)‖xt-x̃‖=‖PC[(1-tγ)xt-γA*(I-PQ)Axt]-PC[x̃-γA*(I-PQ)Ax̃]‖≤‖(1-tγ)(xt-γ1-tγA*(I-PQ)Axt)-(1-tγ)(x̃-γ1-tγA*(I-PQ)Ax̃)-tγx̃‖≤(1-tγ)‖(xt-γ1-tγA*(I-PQ)Axt)-(x̃-γ1-tγA*(I-PQ)Ax̃)‖+tγ‖x̃‖≤(1-tγ)‖xt-x̃‖+tγ‖x̃‖.
Hence,
(3.24)‖xt-x̃‖≤‖x̃‖.
Then, {xt} is bounded.
From (3.21), we have the following:
(3.25)‖xt-PC[(I-γA*(I-PQ)A)xt]‖≤t‖γxt‖⟶0.
Next we show that {xt} is relatively norm compact as t→0+. Assume that {tn}⊂(0,(2-γ∥A∥2)/2γ) is such that tn→0+ as n→∞. Put xn∶=xtn. From (3.25), we have the following:
(3.26)lim⁡n→∞‖xn-PC[(I-γA*(I-PQ)A)xt]‖=0.
By using the property of the projection, we get the following:
(3.27)‖xt-x̃‖2=‖PC[(1-tγ)xt-γA*(I-PQ)Axt]-PC[x̃-γA*(I-PQ)Ax̃]‖2≤〈[(1-tγ)xt-γA*(I-PQ)Axt]-[x̃-γA*(I-PQ)Ax̃],xt-x̃〉=(1-tγ)〈[xt-γ1-tγA*(I-PQ)Axt]-[x̃-γ1-tγγA*(I-PQ)Ax̃],xt-x̃〉-tγ〈x̃,xt-x̃〉≤(1-tγ)‖xt-x̃‖2-tγ〈x̃,xt-x̃〉.
Hence,
(3.28)‖xt-x̃‖2≤〈-x̃,xt-x̃〉.
In particular,
(3.29)‖xn-x̃‖2≤〈-x̃,xn-x̃〉,x̃∈Γ.
Since {xn} is bounded, there exists a subsequence {xni} of {xn} which converges weakly to a point x*. Without loss of generality, we may assume that {xn} converges weakly to x*. Noticing (3.26) we can use Lemma 2.3 to get x*∈Γ. Therefore, we can substitute x* for x̃ in (3.29) to get the following:
(3.30)‖xn-x*‖2≤〈-x*,xn-x*〉.
Consequently, xn⇀x* actually implies that xn→x*. This has proved the relative norm-compactness of the net {xt} as t→0+. Letting n→∞ in (3.29), we have
(3.31)‖x*-x̃‖2≤〈-x̃,x*-x̃〉,x̃∈Γ.
This implies that
(3.32)〈-x̃,x̃-x*〉≤0,x̃∈Γ,
which is equivalent to the following
(3.33)〈-x*,x̃-x*〉≤0,∀x̃∈Γ.
Hence, x*=PΓ(0). Therefore, each cluster point of {xt} (as t→0+) equals x*. So, xt→x*. This completes the proof.



---

*Source: 140679-2012-02-20.xml*