# A Note on Approximating Curve with 1-Norm Regularization Method for the Split Feasibility Problem

Authors: Songnian He; Wenlong Zhu
Journal: Journal of Applied Mathematics
 (2012)

---

## Abstract

Inspired by the very recent results of Wang and Xu (2010), we study properties of the approximating curve with 1-norm regularization method for
the split feasibility problem (SFP). The concept of the minimum-norm solution
set of SFP in the sense of 1-norm is proposed, and the relationship between the approximating curve and the minimum-norm solution set is obtained.


---

## Body

## 1. Introduction

LetC and Q be nonempty closed convex subsets of real Hilbert spaces H1 and H2, respectively. The problem under consideration in this paper is formulated as finding a point x satisfying the property:
(1.1)x∈C,Ax∈Q,
where A:H1→H2 is a bounded linear operator. Problem (1.1), referred to by Censor and Elfving [1] as the split feasibility problem (SFP), attracts many authors’ attention due to its application in signal processing [1]. Various algorithms have been invented to solve it (see [2–13] and references therein).Using the idea of Tikhonov's regularization, Wang and Xu [14] studied the properties of the approximating curve for the SFP. They gave the concept of the minimum-norm solution of the SFP (1.1) and proved that the approximating curve converges strongly to the minimum-norm solution of the SFP (1.1). Together with some properties of this approximating curve, they introduced a modification of Byrne’s CQ algorithm [2] so that strong convergence is guaranteed and its limit is the minimum-norm solution of SFP (1.1).In the practical application,H1 and H2 are often ℝN and ℝM, respectively. Moreover, scientists and engineers are more willing to use 1-norm regularization method in the calculation process (see, e.g., [15–18]). Inspired by the above results of Wang and Xu [14], we study properties of the approximating curve with 1-norm regularization method. We also define the concept of the minimum-norm solution set of SFP (1.1) in the sense of 1-norm. The relationship between the approximating curve and the minimum-norm solution set is obtained.


## 2. Preliminaries

LetX be a normed linear space with norm ∥·∥, and let X* be the dual space of X. We use the notation 〈x,f〉 to denote the value of f∈X* at x∈X. In particular, if X is a Hilbert space, we will denote it by H, and 〈·,·〉 and ∥·∥ are the inner product and its induced norm, respectively.We recall some definitions and facts that are needed in our study.LetPC denote the projection from H onto a nonempty closed convex subset C of H; that is,
(2.1)PCx=argmin⁡y∈C∥x-y∥,x∈H.
It is well known that PCx is characterized by the inequality
(2.2)〈x-PCx,y-PCx〉≤0,∀y∈C.Definition 2.1.
Letφ:X→ℝ∪{+∞} be a convex functional, x0∈dom(φ)={x∈X:φ(x)<+∞}. Set
(2.3)∂φ(x0)={ξ∈X*:φ(x)≥φ(x0)+〈x-x0,ξ〉,∀x∈X}.
If ∂φ(x0)≠∅, φ is said to be subdifferentiable at x0 and ∂φ(x0) is called the subdifferential of φ at x0. For any ξ∈∂φ(x0), we say ξ is a subgradient of φ at x0.Lemma 2.2.
There holds the following property:(2.4)∂(∥x∥)={{x*∈X*:∥x*∥=1,〈x,x*〉=∥x∥},x≠0,{x*∈X*:∥x*∥≤1},x=0,
where ∂(∥x∥) denotes the subdifferential of the functional ∥x∥ at x∈X.Proof.
The process of the proof will be divided into two parts.
Case  1. In the case of x=0, for any x*∈X* such that ∥x*∥≤1 and any y∈X, there holds the inequality
(2.5)∥y∥≥〈y,x*〉=∥x∥+〈y-x,x*〉,
so we have x*∈∂(∥x∥), and thus,
(2.6){x*∈X*:∥x*∥≤1}⊂∂(∥x∥).
Conversely, for any x*∈∂(∥x∥), we have from the definition of subdifferential that
(2.7)∥y∥≥∥x∥+〈y-x,x*〉=〈y,x*〉,∀y∈X,∥y∥=∥-y∥≥〈-y,x*〉=-〈y,x*〉.
Consequently,
(2.8)|〈y,x*〉|≤∥y∥,∀y∈X,
and this implies that ∥x*∥≤1. Thus, we have verified that
(2.9)∂(∥x∥)⊂{x*∈X*:∥x*∥≤1}.
Combining (2.6) and (2.9), we immediately obtain
(2.10)∂(∥x∥)={x*∈X*:∥x*∥≤1}.
Case  2. If x≠0, for any x*∈{x*∈X*:∥x*∥=1,〈x,x*〉=∥x∥}, we obviously have
(2.11)〈y-x,x*〉=〈y,x*〉-∥x∥≤∥y∥-∥x∥,∀y∈X,
which means that x*∈∂(∥x∥), and thus,
(2.12){x*∈X*:∥x*∥=1,〈x,x*〉=∥x∥}⊂∂(∥x∥).
Conversely, if x*∈∂(∥x∥), we have
(2.13)〈-x,x*〉≤0-∥x∥=-∥x∥,〈x,x*〉≤2∥x∥-∥x∥=∥x∥;
hence,
(2.14)〈x,x*〉=∥x∥.
On the other hand, using (2.14), we get
(2.15)∥y∥≥∥x∥+〈y-x,x*〉=∥x∥+〈y,x*〉-〈x,x*〉=〈y,x*〉,∀y∈X,
and consequently,
(2.16)‖y‖=‖-y‖≥‖x‖+〈-y-x,x*〉=‖x‖-〈y,x*〉-〈x,x*〉=-〈y,x*〉;
that is,
(2.17)-∥y∥≤〈y,x*〉.
Equation (2.17) together with (2.15) implies that
(2.18)|〈y,x*〉|≤∥y∥,∀y∈X;
hence, ∥x*∥≤1. Note that (2.14) implies that ∥x*∥≥〈x,x*〉/∥x∥=1; we assert that
(2.19)∥x*∥=1.
Thus we have from (2.14) and (2.19) that
(2.20){x*∈X*:∥x*∥=1,〈x,x*〉=∥x∥}⊃∂(∥x∥).
The proof is finished by combining (2.12) and (2.20).∥
·
∥
∞ and ∥·∥1 will stand for ∞-norm and 1-norm of any Euclidean space; respectively, that is, for any x=(x1,x2,…,xl)∈ℝl, we have
(2.21)∥x∥∞=max⁡1≤j≤l|xj|,‖x‖1=∑j=1l‍|xj|.Corollary 2.3.
In l-dimensional Euclidean spaceℝl, there holds the following result:
(2.22)∂(‖x‖1)={{ξ∈Rl:‖ξ‖∞=1,〈x,ξ〉=‖x‖1},x≠0,{ξ∈Rl:‖ξ‖∞≤1},x=0,={{ξ∈Rl:ξi=xi|xi|,ifxi≠0;ξi∈[-1,1],ifxi=0},x≠0,{ξ∈Rl:‖ξ‖∞≤1},x=0.
Let H be a Hilbert space and f:H→ℝ a functional. Recall that  (i)
fis convex if f(λx+(1-λ)y)≤λf(x)+(1-λ)f(y), for all 0<λ<1, for all x,y∈H;(ii)
f is strictly convex if f(λx+(1-λ)y)<λf(x)+(1-λ)f(y), for all 0<λ<1, for all x,y∈H with x≠y;(iii)
f is coercive if f(x)→∞ whenever ∥x∥→∞. See [19] for more details about convex functions.The following lemma gives the optimality condition for the minimizer of a convex functional over a closed convex subset.Lemma 2.4 (see [20]).
LetH be a Hilbert space and C a nonempty closed convex subset of H. Let f:H→ℝ be a convex and subdifferentiable functional. Then x∈C is a solution of the problem
(2.23)min⁡x∈Cf(x)
if and only if there exists some ξ∈∂f(x) satisfying the following optimality condition:
(2.24)〈ξ,v-x〉≥0,∀v∈C.


## 3. Main Results

It is well known that SFP (1.1) is equivalent to the minimization problem
(3.1)min⁡x∈C‖(I-PQ)Ax‖2.
Using the idea of Tikhonov's regularization method, Wang and Xu [14] studied the minimization problem in Hilbert spaces:
(3.2)min⁡x∈C‖(I-PQ)Ax‖2+α‖x‖2,
where α>0 is the regularization parameter.In what follows,H1 and H2 in SFP (1.1) are restricted to ℝN and ℝM, respectively, and ∥·∥ will stand for the usual 2-norm of any Euclidean space ℝl; that is, for any x=(x1,x2,…,xl)∈ℝl,
(3.3)‖x‖=x12+⋯+xl2.
Inspired by the above work of Wang and Xu, we study properties of the approximating curve with 1-norm regularization scheme for the SFP, that is, the following minimization problem:
(3.4)min⁡x∈C12‖(I-PQ)Ax‖2+α‖x‖1,
where α>0 is the regularization parameter. Let
(3.5)fα(x)=12‖(I-PQ)Ax‖2+α‖x‖1.
It is easy to see that fα is convex and coercive, so problem (3.4) has at least one solution. However, the solution of problem (3.4) may not be unique since fα is not necessarily strictly convex. Denote by Sα the solution set of problem (3.4); thus we can assert that Sα is a nonempty closed convex set but may contain more than one element. The following simple example illustrates this fact.Example 3.1.
LetC={(x,y):x+y=1}, Q={(x,y):x+y=1/2} and
(3.6)A=(120012).
Then A:ℝ2→ℝ2 is a bounded linear operator. Obviously, Sα={(x,y):x+y=1,x≥0,y≥0} and it contains more than one element.Proposition 3.2.
For anyα>0, xα∈Sα if and only if there exists some ξ∈∂(∥x∥1) satisfying the following inequality:
(3.7)〈A*(I-PQ)Axα+αξ,v-xα〉≥0,∀v∈C.Proof.
Let(3.8)f(x)=12‖(I-PQ)Ax‖2,
then
(3.9)fα(x)=f(x)+α‖x‖1.
Since f is convex and differentiable with gradient
(3.10)∇f(x)=A*(I-PQ)Ax,fα is convex, coercive, and subdifferentiable with the subdifferential
(3.11)∂fα(x)=∂f(x)+α∂(‖x‖1);
that is,
(3.12)∂fα(x)=A*(I-PQ)Ax+α∂(‖x‖1).
By Corollary 2.3 and Lemma 2.4, the proof is finished.Theorem 3.3.
Denote byxα an arbitrary element of Sα, then the following assertions hold:(i)
∥xα∥1 is decreasing for α∈(0,∞);(ii)
∥(I-PQ)Axα∥ is increasing for α∈(0,∞).Proof.
Letα>β>0, for any xα∈Sα, xβ∈Sβ. We immediately obtain
(3.13)12‖(I-PQ)Axα‖2+α‖xα‖1≤12‖(I-PQ)Axβ‖2+α‖xβ‖1,(3.14)12‖(I-PQ)Axβ‖2+β‖xβ‖1≤12‖(I-PQ)Axα‖2+β‖xα‖1.
Adding up (3.13) and (3.14) yields
(3.15)α‖xα‖1+β‖xβ‖1≤α‖xβ‖1+β‖xα‖1,
which implies ∥xα∥1≤∥xβ∥1. Hence (i) holds.
Using (3.14) again, we have
(3.16)12‖(I-PQ)Axβ‖2≤12‖(I-PQ)Axα‖2+β(‖xα‖1-‖xβ‖1),
which together with (i) implies
(3.17)‖(I-PQ)Axβ‖2≤‖(I-PQ)Axα‖2,
and hence (ii) holds.Letℱ=C∩A-1(Q), where A-1(Q)={x∈ℝN:Ax∈Q}. In what follows, we assume that ℱ≠∅; that is, the solution set of SFP (1.1) is nonempty. The fact that ℱ is nonempty closed convex set thus allows us to introduce the concept of minimum-norm solution of SFP (1.1) in the sense of norm ∥·∥ (induced by the inner product).Definition 3.4 (see [14]).
An elementx†∈ℱ is said to be the minimum-norm solution of SFP (1.1) in the sense of norm∥·∥ if ∥x†∥=infx∈ℱ∥x∥. In other words, x† is the projection of the origin onto the solution set ℱ of SFP (1.1). Thus there exists only one minimum-norm solution of SFP (1.1) in the sense of norm ∥·∥, which is always denoted by x†.
We can also give the concept of minimum-norm solution of SFP (1.1) in other senses.Definition 3.5.
An elementx~∈ℱ is said to be a minimum-norm solution of SFP (1.1) in the senseof 1-norm if ∥x~∥1=infx∈ℱ∥x∥1. We use ℱ1 to stand for all minimum-norm solutions of SFP (1.1) in the sense of 1-norm and ℱ1 is called the minimum-norm solution set of SFP (1.1) in the sense of 1-norm.
Obviously,ℱ1 is a closed convex subset of ℱ. Moreover, it is easy to see that ℱ1≠∅. Indeed, taking a sequence {xn}⊂ℱ such that ∥xn∥1→infx∈ℱ∥x∥1 as n→∞, then {xn} is bounded. There exists a convergent subsequence {xnk} of {xn}. Set x-=limk→∞xnk, then x-∈ℱ since ℱ is closed. On the other hand, using lower semicontinuity of the norm, we have
(3.18)‖x-‖≤lim⁡k→∞‖xnk‖=inf⁡x∈F‖x‖1,
and this implies that x-∈ℱ1.
However,ℱ1 may contain more than one elements, in general (see Example 3.1, ℱ1={(x,y):x+y=1,x,y≥0}).Theorem 3.6.
Letα>0 and xα∈Sα. Then ω(xα)⊂ℱ1, where ω(xα)={x:∃{xαk}⊂{xα},xαk→xweakly}.Proof.
Takingx~∈ℱ1 arbitrarily, for any α∈(0,∞), we always have
(3.19)12‖(I-PQ)Axα‖2+α‖xα‖1≤12‖(I-PQ)Ax~‖2+α∥x~∥1.
Since x~ is a solution of SFP (1.1), ∥(I-PQ)Ax~∥=0. This implies that
(3.20)12‖(I-PQ)Axα‖2+α‖xα‖1≤α‖x~‖1,
then,
(3.21)‖xα‖1≤‖x~‖1;
thus {xα} is bounded.
Takeω∈ω(xα) arbitrarily, then there exists a sequence {αn} such that αn→0 and xαn→ω as n→∞. Put xαn=xn. By Proposition 3.2, we deduce that there exists some ξn∈∂(∥xn∥1) such that
(3.22)〈A*(I-PQ)Axn+αnξn,x~-xn〉≥0.
This implies that
(3.23)〈(I-PQ)Axn,A(x~-xn)〉≥αn〈ξn,xn-x~〉.
Since Ax~∈Q, the characterizing inequality (2.2) gives
(3.24)〈(I-PQ)Axn,Ax~-PQ(Axn)〉≤0,
then,
(3.25)‖(I-PQ)Axn‖2≤〈(I-PQ)Axn,A(xn-x~)〉.
Combining (3.23) and (3.25), we have
(3.26)‖(I-PQ)Axn‖2≤αn〈ξn,x~-xn〉≤αn‖ξn‖∞‖x~-xn‖1≤2αn‖x~‖1.
Consequently, we get
(3.27)lim⁡n→∞‖(I-PQ)Axn‖=0.
Furthermore, noting the fact that xn→ω and I-PQ and A are all continuous operators, we have (I-PQ)Aω=0; that is, Aω∈Q; thus, ω∈ℱ. Since x~ is a minimum-norm solution of SFP (1.1) in the sense of 1-norm, using (3.21) again, we get
(3.28)‖ω‖1≤liminf⁡n→∞‖xn‖1≤‖x~‖1=min⁡{‖x‖1:x∈F}.
Thus we can assert that ω∈ℱ1 and this completes the proof.Corollary 3.7.
Ifℱ1 contains only one element x~, then xα→x~, (α→0).Remark 3.8.
It is worth noting that the minimum-norm solution of SFP (1.1) in the sense of norm ∥·∥ is very different from the minimum-norm solution of SFP (1.1) in the sense of 1-norm. In fact, x† may not belong to ℱ1! The following simple example shows this fact.Example 3.9.
LetC={(x,y):x+2y≥2,x≥0,y≥0},  Q={(x,y):x+y=1,x≥0,y≥0}, and
(3.29)A=(12001).
It is not hard to see that A:ℝ2→ℝ2 is a bounded linear operator and A(x,y)T=((1/2)x,y)T, for  all (x,y)∈C. Obviously, ℱ={(x,y):x+2y=2,x≥0,y≥0}, x†=(2/5,4/5), but ℱ1={(0,1)}. Hence, x†∈ℱ∖ℱ1.



---

*Source: 683890-2012-07-17.xml*