Iterative oblique projection onto convex sets and the split feasibility problem

Let C and Q be nonempty closed convex sets in R(N) and R(M), respectively, and A an M by N real matrix. 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. An iterative method for solving the SFP, called the CQ algorithm, has the following iterative step: x(k+1) = P(C)(x(k) + gammaA(T)(P(Q) - I)Ax(k)), where gamma is an element of (0, 2/L) with L the largest eigenvalue of the matrix A(T) A and P(C) and P(Q) denote the orthogonal projections onto C and Q, respectively; that is, P(C)x minimizes parallel toc - xparallel to, over all c is an element of C. The CQ algorithm converges to a solution of the SFP, or, more generally, to a minimizer of parallel toP(Q)Ac - Acparallel to over c in C, whenever such exist. The CQ algorithm involves only the orthogonal projections onto C and Q, which we shall assume are easily calculated, and involves no matrix inverses. If A is normalized so that each row has length one, then L does not exceed the maximum number of nonzero entries in any column of A, which provides a helpful estimate of L for sparse matrices. Particular cases of the CQ algorithm are the Landweber and projected Landweber methods for obtaining exact or approximate solutions of the linear equations Ax = b; the algebraic reconstruction technique of Gordon, Bender and Herman is a particular case of a block-iterative version of the CQ algorithm. One application of the CQ algorithm that is the subject of ongoing work is dynamic emission tomographic image reconstruction, in which the vector x is the concatenation of several images corresponding to successive discrete times. The matrix A and the set Q can then be selected to impose constraints on the behaviour over time of the intensities at fixed voxels, as well as to require consistency (or near consistency) with measured data.