A note on the CQ algorithm for the split feasibility problem

Let C and Q be nonempty closed convex sets in R-N and R-M, respectively, and A an M x N real rnatrix. The split feasibility problem (SFP) is to find x is an element of C with Ax is an element of Q, if such x exist. Byrne (2002 Inverse Problems 18 441-53) proposed a CQ algorithm with the following iterative scheme: X (k+1) = Pc(x(k) + gamma A(T)(P-Q - 1)Ax(k)), k = 0, 1,..., where gamma is an element of (0, 2/L), L denotes the largest eigenvalue of the matrix A (T) A, and P-C and P-Q denote the orthogonal projections onto C and Q, respectively. In his algorithm, Byrne assumed that the projections P-C and P-Q are easily calculated. However, in some cases it is impossible or needs too much work to exactly compute the orthogonal projection. Recently, Yang (2004 Inverse Problems 20 1261-6) presented a relaxed CQ algorithm, in which he replaced P-C and P-Q by P-Ck and P-Qk, that is, the orthogonal projections onto two halfspaces C-k and Q(k), respectively. Clearly, the latter is easy to implement. One common advantage of the CQ algorithm and the relaxed C Q algorithm is that computation of the rnatrix inverses is not necessary. However, they use a fixed stepsize related to the largest eigenvalue of the matrix A (T) A, which sometimes affects convergence of the algorithms. In this paper, we present modifications of the CQ algorithm and the relaxed CQ algorithm by adopting Armijo-like searches. The modified algorithms need not compute the matrix inverses and the largest eigenvalue of the matrix A(T) A, and make a sufficient decrease of the objective function at each iteration. We also show convergence of the modified algorithms under mild conditions.