A NEW ITERATIVE METHOD FOR THE SPLIT COMMON FIXED POINT PROBLEM IN HILBERT SPACES Fenghui Wang

PROBLEM IN HILBERT SPACES

Fenghui Wang

Department of Mathematics, Luoyang Normal University, Luoyang 471022, P.R. China E-mail: [email protected]

ABSTRACT. The split common fixed-point problem is an inverse problem that consists in finding an element in a fixed-point set such that its image under a bounded linear operator belongs to another fixed-point set.

In this paper, we propose a new algorithm that is completely different from the existing algorithms. Under standard assumptions, we establish a weak convergence theorem of the proposed algorithm. Applications of the proposed algorithm to special cases as well as compressed sensing are also included.

2010 Mathematics Subject Classification:47J25, 47J20, 49N45, 65J15.

Keywords:split common fixed-point problem, F´ejer monotonicity, demicontractive operators.

1. INTRODUCTION

In recent years there has been growing interest in the study of the split common fixed-point problem (SCFP). This problem aims to find an element in a fixed-point set such that its image under a bounded linear operator belongs to another fixed-point set [6]. More specifically, the SCFP consists in finding

x∈Fix(U), s.t.Ax∈Fix(T), (1.1)

whereA :H → K is a bounded linear operator,Fix(U)andFix(T)stand for respectively the fixed point sets ofU : H → H andT : K → K, and H andK are two Hilbert spaces. In particular, if T andU are projection operators, then the SCFP is reduced to the well-known split feasibility problem [5, 3], which consists in findingxwith the property:

x∈C, s.t. Ax∈Q, (1.2)

whereCandQare nonempty closed convex subsets ofHandK, respectively. It is clear that in this special caseU =PCandT =PQ, wherePC, PQare the orthogonal projections ontoCandQ, respectively.

1

Problem (1.1) can be cast as solving a fixed-point equation:

x=U(I−τ A^∗(I−T)A)x, (1.3)

whereτis a positive real number andA^∗is the corresponding adjoint operator ofA. Based on this equation, Censor and Segal [6] introduced the following algorithm for solving the SCFP:

x_n+1 =U(x_n−τ A^∗(I−T)Ax_n), (1.4)

where τ is a properly chosen stepsize. Algorithm (1.4) was originally designed to solve problem (1.1) whenever the operators involved are directed operators. It is shown that if the stepsizeτ is chosen in the interval(0,2/kAk²), then the iterative sequence generated by (1.4) converges weakly to a solution of the SCFP whenever such a solution exists. Subsequently, this iterative scheme was extended to the case of quasi- nonexpansive operators [11], demicontractive operators [12], and finite many directed operators [4, 17]. In [7], the constant stepsize in (1.4) was replaced by a variable step that does not depend on the operator norm kAk, since the computation of the norm is in general not an easy work in practice. In a recent work [2, 13], a modification of (1.4) was presented so that it generates an iterative sequence with a norm convergent property.

The aim of this paper is to introduce a new algorithm to solve the SCFP. Our idea for designing iterative algorithms is based on an observation: problem (1.1) amounts to solving, instead of (1.3), another fixed- point equation (3.1). In light of this fixed-point equation, we can easily introduce a new algorithm for solving problem (1.1). By using F´ejer monotonicity, we obtain the weak convergence of the iterative sequence to a solution for demicontrcitve operators. As an application, we obtain a new algorithm for solving the SFP.

2. PRELIMINARY AND NOTATION

Throughout the paper, we denote byHandK two Hilbert spaces,I the identity operator,Fix(T)the set of the fixed points of an operatorT, andω_w{x_n}the set of weak cluster points of a sequence {x_n}.The notation “→” stands for strong convergence and “*” stands for weak convergence.

Definition 2.1. An operatorT :H →His callednonexpansive, if kT x−T yk ≤ kx−yk, ∀x, y∈H;

firmly nonexpansive, if

kT x−T yk² ≤ kx−yk²− k(I−T)x−(I−T)yk², ∀x, y∈H.

Definition 2.2. LetT :H → Hbe an operator withFix(T) 6=∅.ThenI−T is said to bedemiclosed at zero, if, for any{x_n}inH, there holds the following implication:

xn* x (I−T)x_n→0

#

⇒x∈Fix(T).

It is well known that nonexpansive operators are demiclosed at zero.

Definition 2.3. LetT :H→Hbe an operator withFix(T)6=∅.Then (i) T :H →His calleddirectedif

hz−T x, x−T xi ≤0, ∀z∈Fix(T), x∈H, or equivalently

hx−z, x−T xi ≥ kx−T xk², ∀z∈Fix(T), x∈H; (2.1) (ii) T :H →His calledquasi nonexpansiveif

kT x−zk ≤ kx−zk, ∀z∈Fix(T), x∈H;

(iii) T :H →His calledκ-demicontractivewithκ <1, if

kT x−zk² ≤ kx−zk²+κk(I−T)xk², ∀z∈Fix(T), x∈H, or equivalently

hx−z, T x−xi ≤ κ−1

2 kx−T xk², ∀z∈Fix(T), x∈H. (2.2) An orthogonal projectionP_C fromHonto a nonempty closed convex subsetC⊂H is defined by

PCx:= arg min

y∈C

kx−yk², x∈H. (2.3)

It is well known that the projectionP_C is characterized by:

hx−PCx, z−PCxi ≤0, ∀z∈C. (2.4)

The concept of F´ejer-monotonicity plays an important role in the subsequent analysis of this paper. Recall that a sequence{x_n}inH is said to be F´ejer-monotone with respect to (w.r.t.) a nonempty closed convex nonempty subsetSofHif

kx_n+1−zk ≤ kx_n−zk, ∀n≥0, ∀z∈S.

Lemma 2.4. [1, 7]LetSbe a nonempty closed convex subset inH. If the sequence{x_n}is F´ejer monotone w.r.t.S,then the following hold:

(i) xn* z∈Sif and only ifωw{x_n} ⊆S;

(ii) the sequence{P_Sx_n}converges strongly;

(iii) ifxn* z∈S,thenz= lim

n→∞PSxn.

3. ANEW ALGORITHM AND ITS CONVERGENCE ANALYSIS

Let us first consider the SCFP (1.1) for demicontractive operators. More specifically, we make use of the following assumptions:

(A1) U isκ1-demicontractive withκ1 <1;

(A2) T isκ2-demicontractive withκ2 <1;

(A3) bothI−U andI−Tare demiclosed at zero;

(A4) it is consistent, i.e., its solution set, denoted byS, is nonempty.

Under these conditions, we propose the following algorithm: In what follows, we will treat problem (1.1) under (A1)-(A4). We first state a theorem, which implies that the SCFP is equivalent to solving a fixed-point equation.

Theorem 3.1. Let condition (A4) be satisfied. Then, for anyτ > 0,xis a solution to problem(1.1)if and only if it solves the following fixed point equation:

x=x−τ[(x−U x) +A^∗(I −T)Ax]. (3.1) Proof. It is trivial to see that ifx∈S,then it solves Eq. (3.1).

To see the converse, letxbe a solution to Eq. (3.1), that is, x−U x+A^∗(I−T)Ax= 0.

Now fix anyz∈S.It then follows from (2.2) that

0 =hx−U x+A^∗(I−T)Ax, x−zi

=hx−U x, x−zi+hA^∗(I−T)Ax, x−zi

=hx−U x, x−zi+h(I−T)Ax, Ax−Azi

≥ 1−κ1

2 kx−U xk²+1−κ2

2 k(I−T)Axk².

Hencex=U xandAx=T(Ax), and the proof is thus complete.

Theorem 3.1 thus enables us to propose a new iterative algorithm for solving problem (1.1).

Algorithm 1. Choose an initial guessx0 ∈ H arbitrarily. Assume that the nth iterate xn has been con- structed; then calculate the(n+ 1)thiteratexn+1via the formula:

xn+1 =xn−τ[(xn−U xn) +A^∗(I−T)Axn],

where the stepsizeτ is a properly chosen real number.

Theorem 3.2. Let conditions (A1)-(A4) be satisfied and let{x_n}be the sequence generated by Algorithm 1. If the stepsizeτ satisfies

0<2τ <min

1−κ₁,1−κ₂ kAk²

, then{x_n}converges weakly to a solutionz∈S, wherez= lim

n→∞PSxn.

Proof. We first show that the sequence{x_n}is F´ejer-monotone w.r.t. S. To this end, letun= (xn−U x_n) + A^∗(I−T)Axn.By inequality (2.2), we have

hx_n−U xn, xn−zi ≥ 1−κ1

2 kU x_n−xnk², and

hA^∗(I−T)Axn, xn−zi=h(I−T)Axn, Axn−Azi

≥ 1−κ1

2 k(I−T)Axnk², Combining these two inequalities, we have

hu_n, xn−zi ≥ 1−κ1

2 kU x_n−xnk²+1−κ1

2 k(I−T)Axnk²

= 1−κ₁

2 kx_n−U x_nk²+1−κ₂

2kAk²kAk²k(I −T)Ax_nk²

≥ 1−κ₁

2 kx_n−U x_nk²+1−κ₂

2kAk²kA^∗(I−T)Ax_nk²

≥min(1−κ₁

2 ,1−κ₂

2kAk²) kx_n−U xnk²+kA^∗(I−T)Axnk²

≥ 1

4min(1−κ1,1−κ2

kAk² ) kx_n−U xnk+kA^∗(I−T)Axnk2

≥ 1

4min(1−κ1,1−κ2

kAk² )k(x_n−U xn) +A^∗(I−T)Axnk²

= 1 4min

1−κ₁,1−κ₂ kAk²

ku_nk². which implies

kx_n+1−zk²=kx_n−zk²−2τhu_n, x_n−zi+ku_nk²

≤ kx_n−zk²−τ 2min

1−κ₁,1−κ₂ kAk²

ku_nk²+τ²ku_nk²

=kx_n−zk²−τ 2

min

1−κ1,1−κ2

kAk²

−2τ

ku_nk².

Let us now define

δ := τ 2

min

1−κ₁,1−κ₂ kAk²

−2τ

. Thus, we have

kx_n+1−zk² ≤ kx_n−zk²−δku_nk². (3.2) Sinceδis clearly a positive number, this implies that{x_n}is F´ejer-monotone.

We next show that every weak cluster point of the sequence {x_n} belongs to the solution set, i.e., ωw{x_n} ⊆ S.As a F´ejer-monotone sequence,{x_n}is bounded, and so is the sequence{u_n}. Moreover it follows from (3.2) that

δku_nk²≤ kx_n−zk²− kx_n+1−zk². By induction, we have

δ

n

X

k=0

ku_kk²≤ kx₀−zk² for alln≥0, so that

∞

X

n=0

ku_nk²<∞, which particularly implies

n→∞lim ku_nk= 0. (3.3)

On the other hand, we deduce from (2.2) that 1−κ₁

2 kx_n−U x_nk²+1−κ₂

2 k(I−T)Ax_nk²

≤ hx_n−U xn, xn−zi+h(I−T)Axn, Axn−Azi

=hx_n−U xn, xn−zi+hA^∗(I −T)Axn, xn−zi

=hu_n, xn−zi ≤ ku_nkkx_n−zk.

Since{x_n}and{u_n}both bounded, this together with (3.3) implies that

n→∞lim kx_n−U x_nk= lim

n→∞k(I−T)Ax_nk= 0.

By our condition (A3), we conclude that every weak cluster point of the sequence {x_n} belongs to the solution set.

Finally, we deduce from Lemma 2.4 that the sequence{x_n}converges weakly to a solutionzof problem (1.1) since we have shown that{x_n}is F´ejer-monotone and every weak cluster point of{x_n}belongs to the

solution set.

4. APPLICATIONS TO SPECIAL CASES

In this section, we study applications of the previous results to various nonlinear operators. We first con- sider the case for quasi-nonexpansive operators. As every quasi-nonexpansive is clearly 0-demicontractive, we can state the following results.

Theorem 4.1. Assume thatU andT in problem(1.1)are quasi-nonexpansive, and bothI −T andI−U are demiclosed at zero. Let{x_n}be the sequence generated by Algorithm 1. If the stepsize satisfies

0< τ < 1

2 max(1,kAk²), then{x_n}converges weakly to a solutionzof problem (1.1).

Since every nonexpansive operator is clearly quasi nonexpansive, and demiclosed at zero, we can easily deduce the following results.

Theorem 4.2. Assume thatU andTin problem(1.1)are nonexpansive operators. Let{x_n}be the sequence generated by Algorithm 1. If the stepsize satisfies

0< τ < 1

2 max(1,kAk²), then{x_n}converges weakly to a solutionzof problem (1.1).

We next consider the case for quasi-nonexpansive operators. As every directed operator is clearly -1- demicontractive, we can state the following results.

Theorem 4.3. Assume thatUandTin problem(1.1)are directed, and bothI−T andI−U are demiclosed at zero. Let{x_n}be the sequence generated by Algorithm 1. If the stepsize satisfies

0< τ < 1 max(1,kAk²), then{x_n}converges weakly to a solutionzof problem (1.1).

Since every firmly nonexpansive operator is clearly directed and nonexpansive, and thus demiclosed at zero, from which we can easily deduce the following results.

Theorem 4.4. Assume thatU andT in problem(1.1)are firmly nonexpansive operators. Let{x_n}be the sequence generated by Algorithm 1. If the stepsize satisfies

0< τ < 1 max(1,kAk²), then{x_n}converges weakly to a solutionzof problem (1.1).

We finally consider the case for projection operators, namely the split feasibility problem (1.2). In this sit- uation, we have the following iterative algorithm for problem (1.2). However, in this special case, conditions posed on the stepsizeτ can be further relaxed.

Algorithm 2. Choose an initial guessx₀ ∈ H arbitrarily. Assume that the nth iterate x_n has been con- structed; then calculate the(n+ 1)thiteratex_n+1via the formula:

x_n+1 =x_n−τ[(x_n−P_Cx_n) +A^∗(I−P_Q)Ax_n], (4.1) where the stepsizeτ is a positive real number.

Theorem 4.5. Assume that problem(1.1)is consistent. Let{x_n}be the sequence generated by Algorithm 2. If the stepsize satisfies

0< τ < 2 1 +kAk², then{x_n}converges weakly to a solutionzof problem (1.2).

Proof. It suffices to show that the sequence{x_n}is F´ejer-monotone w.r.t. S, since the rest proof is similar to that of Theorem 3.2. To this end, let us define

f(x) = 1

2 kx−P_Cxk²+k(I−P_Q)Axk²

, x∈H.

It is clear thatfis differential, and

∇f(x) = (x−PCx) +A^∗(I−PQ)Ax.

It then follows that

k∇f(x)− ∇f(y)k=k(I −P_C)(x−y) +A^∗(I−P_Q)A(x−y)k

≤ k(I −P_C)(x−y)k+kA^∗(I−P_Q)A(x−y)k

≤ kx−yk+kA^∗kk(I−P_Q)A(x−y)k

≤ kx−yk+kA^∗kkA(x−y)k

≤ kx−yk+kAk²kx−yk

= (1 +kAk²)kx−yk,

where we have used the fact that bothI−P_CandI−P_Care nonexpansive, andkAk=kA^∗k.This clearly implies that∇f(x)is Lipschitz continuous with constant1 +kAk². Hence, by Baillon-Haddad theorem, we conclude that∇f(x)is1/(1 +kAk²)-inverse strongly monotone, that is,

h∇f(x)− ∇f(y), x−yi ≥ 1

1 +kAk²k∇f(x)− ∇f(y)k². (4.2)

Let nowu_n= (x_n−P_Cx_n) +A^∗(I−P_Q)Ax_n.Henceu_n=∇f(x_n).In view of (4.2), we have hu_n, xn−zi=h∇f(xn)− ∇f(z), xn−zi

≥ 1

1 +kAk²k∇f(x_n)− ∇f(z)k²

= 1

1 +kAk²k∇f(x_n)k²

= 1

1 +kAk²ku_nk², from which it then follows that

kx_n+1−zk² =kx_n−zk²−2τhu_n, xn−zi+τ²ku_nk²

≤ kx_n−zk²− 2

1 +kAk²ku_nk²+τ²ku_nk²

=kx_n−zk²−τ

2

1 +kAk² −τ

ku_nk². Let us now set

δ :=τ

2

1 +kAk² −τ

.

Thus, the last inequality yields

kx_n+1−zk² ≤ kx_n−zk²−δku_nk².

Sinceδis clearly a positive number, this implies that{x_n}is F´ejer-monotone.

5. APPLICATIONS IN SIGNAL PROCESSING

In this section we consider applications of our algorithm to inverse problems arising from signal process- ing. Compressed sensing is a very active domain of research and applications, based on the fact that an N-sample signalxwith exactlymnonzero components can be recovered frommk < Nmeasurements as long as the number of measurements is smaller than the number of signal samples and at the same time much larger than the sparsity level ofx. Likewise the measurements are required to be incoherent, which means that the information contained in the signal is spread out in the domain. Sincek < N, the problem of recoveringxfromkmeasurements is ill conditioned because we encounter an underdeterminated system of linear equations. But using a sparsity prior, it turns out that reconstructingxfromyis possible as long as the number of nonzero elements is small enough.

More specifically, compressed sensing can be formulated as inverting the equation system

y=Ax+ε, (5.1)

wherex ∈ R^N is the data to be recovered, y ∈ R^k is the vector of noisy observations or measurements, andεrepresents the noise,A : R^N → R^k is a bounded linear observation operator, often ill-conditioned because it models a process with loss of information. A powerful approach for problem (5.1) consists in considering a solutionxrepresented by a sparse expansion, that is, represented by a series expansion with respect to an orthonormal basis that has only a small number of large coefficients. When attempting to find sparse solutions to linear inverse problems of type (5.1), a successful model is the convex unconstraint minimization problem

min

x∈R^N

1

2ky−Axk²+νkxk₁, (5.2)

whereνis a positive parameter, andk · k₁ is the`<sub>1</sub>norm. Problem (5.2) consists in minimizing an objective function, which includes a quadratic error term combined with a sparseness-inducing`1regularization term, which is to make small component ofxto become zero. By means of convex analysis, one is able to show that a solution to the constrained least squares problem

x∈minR^N

1

2ky−Axk²subjet tokxk₁≤t, (5.3)

for any nonnegative real numbert, is a minimizer of (5.2) (cf. [9]). Clearly problem (5.3) is a particular case of (1.2) whereC={x∈R^N :kxk₁ ≤t}andQ={y}, and thus can be solved by the proposed algorithm.

In this case,P_C andP_C is the projection onto the closed`₁-ball inR^N (see [8]).

Algorithm 3. Choose an initial guessx0 ∈ H arbitrarily. Assume that the nth iterate xn has been con- structed; then calculate the(n+ 1)thiteratex_n+1via the formula:

xn+1=xn−τ[(xn−PCxn) +A^∗(Axn−b)], (5.4) where the stepsizeτ is a positive real number.

Theorem 5.1. Assume that problem(5.3)is consistent. Let{x_n}be the sequence generated by Algorithm 3. If the stepsize satisfies

0< τ < 2 1 +kAk², then{x_n}converges weakly to a solutionzof problem (5.3).

REFERENCES

[1] H.H. Bauschke, J.M. Borwein, On projection algorithms for solving convex feasibility problems, SIAM Review, 38 (1996), 367–426.

[2] O. A. Boikanyo, A strongly convergent algorithm for the split common fixed point problem, Appl. Math. Comput., 265 (2015), 844–853.

[3] C. Byrne, Iterative oblique projection onto convex sets and the split feasibility problem, Inverse Problems, 18 (2002), 441–453.

[4] A. Cegielski, General method for solving the split common fixed point problem, J. Optim. Theory Appl., 165(2015), 385–404.

[5] Y. Censor, T. Elfving, A multiprojection algorithms using Bregman projection in a product space, Numer. Algorithm, 8 (1994), 221–239.

[6] Y. Censor, A. Segal, The split common fixed point problem for directed operators, J. Convex Anal., 16 (2009), 587–600.

[7] H. Cui, F. Wang, Iterative methods for the split common fixed point problem in Hilbert spaces, Fixed Point Theory & Appli- cations, 2014, (2014), 1–8.

[8] J.C. Duchi, S. Shalevshwartz, Y. Singer, et al. Efficient projections onto the`1-ball for learning in high dimensions, Interna- tional conference on machine learning, 2008: 272–279.

[9] M. A. Figueiredo, R. D. Nowak and S. J. Wright, Gradient projection for sparse reconstruction: Application to Compressed Sensing and other Inverse Problems, IEEE J. Sel. Top. Signal Process. 1 (2007), 586–598.

[10] G. L´opez et al., Solving the split feasibility problem without prior knowledge of matrix norms, Inverse Problems, 28, (2012), 085004.

[11] A. Moudafi, A note on the split common fixed-point problem for quasi-nonexpansive operators. Nonlinear Anal., 74 (2011), 4083–4087.

[12] A. Moudafi, The split common fixed point problem for demicontractive mappings. Inverse Problems, 26 (2010), 055007.

[13] P. Kraikaew, S. Saejung, On split common fixed point problems, J. Math. Anal. Appl., 415 (2014), 513–524.

[14] F. Sch¨opfer, T. Schuster, A.K. Louis, An iterative regularization method for the solution of the split feasibility problem in Banach spaces, Inverse Problems, 24 (2008), 055008.

[15] K.K. Tan and H.K. Xu, Approximating fixed points of nonexpansive mappings by the Ishikawa iteration process, J. Math.

Anal. Appl., 178 (1993), 301–308.

[16] F. Wang, On the convergence of CQ algorithm with variable steps for the split equality problem, to appear in Numerical Algorithms.

[17] F. Wang, H.K. Xu, Cyclic algorithms for split feasibility problems in Hilbert spaces, Nonlinear Anal., 74 (2011), 4105–4111.

[18] H.K. Xu, Iterative algorithms for nonlinear operators, J. London Math. Soc. 66 (2002), 240-256.

[19] H.K. Xu, A variable Krasnosel’skii-Mann algorithm and the multiple-set split feasibility problem, Inverse Problems, 22 (2006), 2021–2034.

[20] H.K. Xu, Iterative methods for the split feasibility problem in infinite-dimensional Hilbert spaces, Inverse Problems, 26 (2010), 105018.