×

Iterative oblique projection onto convex sets and the split feasibility problem. (English) Zbl 0996.65048

Let \(C\) and \(Q\) be nonempty closed convex sets in \({\mathbb R}^N\) and \({\mathbb R}^M\), respectively, and \(A\) an \(M\) by \(N\) real matrix. The split feasibility problem (SFP) is to find \(x\in C\) with \(Ax\in Q\), if such \(x\) exits. The author presents an iterative method for solving the SFP, called the \(CQ\) algorithm, which has the following iterative step: \(x^{k+1}=P_C(x^k+\gamma A^T(P_Q-I)Ax^k)\), where \(\gamma\in(0,2/L)\) with \(L\) the largest eigenvalue of \(A^TA\) and \(P_C\) and \(P_Q\) denote the orthogonal projections onto \(C\) and \(Q\), respectively.
It is shown that the \(CQ\) algorithm converges to a solution of the SFP, or, more generally, to a minimizer of \(\|P_CAc-Ac\|\) over \(c\in C\), whenever such \(c\) exists. The \(CQ\) algorithm involves only the easily calculated projections \(P_C\) and \(P_Q\), but 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\). This estimation of \(L\) accelerates the convergence by permitting the relaxation parameter \(\gamma\) to take on larger values.
The \(CQ\) algorithm can be extended to a block-iterative version which may provide further acceleration. One promising application of the \(CQ\) algorithm is dynamic emission tomographic image reconstruction.

MSC:

65F30 Other matrix algorithms (MSC2010)
65F10 Iterative numerical methods for linear systems
PDF BibTeX XML Cite
Full Text: DOI Link