Iterative oblique projection onto convex sets and the split feasibility problem

被引:1025
作者
Byrne, C [1 ]
机构
[1] Univ Massachusetts Lowell, Dept Math Sci, Lowell, MA 01854 USA
关键词
D O I
10.1088/0266-5611/18/2/310
中图分类号
O29 [应用数学];
学科分类号
070104 ;
摘要
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.
引用
收藏
页码:441 / 453
页数:13
相关论文
共 22 条
[1]   SIMULTANEOUS ALGEBRAIC RECONSTRUCTION TECHNIQUE (SART) - A SUPERIOR IMPLEMENTATION OF THE ART ALGORITHM [J].
ANDERSEN, AH ;
KAK, AC .
ULTRASONIC IMAGING, 1984, 6 (01) :81-94
[2]  
[Anonymous], VECTOR SPACE PROJECT
[3]   Projection algorithms for solving convex feasibility problems [J].
Bauschke, HH ;
Borwein, JM .
SIAM REVIEW, 1996, 38 (03) :367-426
[4]  
Bertero M., 1998, Introduction to Inverse Problems in Imaging (Advanced Lectures in Mathematics)
[5]  
Bregman LM, 1967, USSR Computational Mathematics and Mathematical Physics, V7, P200
[6]   Iterative projection onto convex sets using multiple Bregman distances [J].
Byrne, C .
INVERSE PROBLEMS, 1999, 15 (05) :1295-1313
[7]   Iterative image reconstruction algorithms based on cross-entropy minimization [J].
Byrne, Charles L. .
IEEE TRANSACTIONS ON IMAGE PROCESSING, 1993, 2 (01) :96-103
[8]   Block-iterative methods for image reconstruction from projections [J].
Byrne, CL .
IEEE TRANSACTIONS ON IMAGE PROCESSING, 1996, 5 (05) :792-794
[9]  
BYRNE CL, 2001, INHERENTLY PARALLEL, P87, DOI DOI 10.1016/S1570-579X(01)80008-2
[10]  
Censor Y., 1994, Numer. Algorithms, V8, P221, DOI DOI 10.1007/BF02142692