Iterative projection onto convex sets using multiple Bregman distances

Publisher Website
Google Scholar
Abstract
A number of inverse problems, in image reconstruction and elsewhere, can be formulated in terms of finding a vector in the intersection of certain convex sets that serve to constrain the solution. Finding such vectors is called the `convex feasibility problem' (CFP). Algorithms to solve the CFP are usually iterative `projection onto convex sets' (POCS) methods that employ orthogonal or more general projections onto the individual convex sets; Bregman's `successive generalized projection' (SGP) is one such method. When the intersection of the convex sets is heterogeneous one may wish to optimize a certain function over that intersection; then we have a constrained optimization problem. Generalized projections come from generalized distances, typically Bregman distances, chosen to incorporate prior information, such as non-negativity, about the image being reconstructed. Calculating a generalized projection onto a convex set can be simplified if the generalized distance can vary with the convex set. Censor and Elfving have discovered a simultaneous multiprojection algorithm that permits just such variation. Because simultaneous methods, which use all the convex sets at each step, can be slow to converge, there is considerable interest in faster, block-iterative methods that employ only some of the convex sets at each step. In this paper we present the first such method that permits multiple generalized projections. We introduce a new notion of convex combination and apply it to obtain an extension of the SGP, called the `multidistance SGP' (MSGP) method, that allows for projecton with respect to multiple generalized distances. We conclude with an extension of the MSGP to block-iterative algorithms involving relaxed generalized projections and paracontractive operators.