Abstract
Problems in signal detection and image recovery can sometimes be formulated as a convex feasibility problem (CFP) of finding a vector in the intersection of a finite family of closed convex sets. Algorithms for this purpose typically employ orthogonal or generalized projections onto the individual convex sets. The simultaneous multiprojection algorithm of Censor and Elfving for solving the CFP, in which different generalized projections may be used at the same time, has been shown to converge for the case of nonempty intersection; still open is the question of its convergence when the intersection of the closed convex sets is empty.
Motivated by the geometric alternating minimization approach of Csiszár and Tusnády and the product space formulation of Pierra, we derive a new simultaneous multiprojection algorithm that employs generalized projections of Bregman to solve the convex feasibility problem or, in the inconsistent case, to minimize a proximity function that measures the average distance from a point to all convex sets. We assume that the Bregman distances involved are jointly convex, so that the proximity function itself is convex. When the intersection of the convex sets is empty, but the closure of the proximity function has a unique global minimizer, the sequence of iterates converges to this unique minimizer. Special cases of this algorithm include the “Expectation Maximization Maximum Likelihood” (EMML) method in emission tomography and a new convergence result for an algorithm that solves the split feasibility problem.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
R. Aharoni and Y. Censor, Block-iterative projection methods for parallel computation of solutions to convex feasibility problems, Linear Algebra and its Applications 120 (1989) 165–175.
A. Auslender, Optimisation: Méthodes Numériques (Masson, Paris, France, 1976).
H.H. Bauschke and J.M. Borwein, On projection algorithms for solving convex feasibility problems, SIAM Review 38 (1996) 367–426.
H.H. Bauschke and J.M. Borwein, Legendre functions and the method of random Bregman projections, Journal of Convex Analysis 4 (1997) 27–67.
L.M. Bregman, The relaxation method of finding the common point of convex sets and its application to the solution of problems in convex programming, USSR Computational Mathematics and Mathematical Physics 7 (1967) 200–217.
L.M. Bregman, Y. Censor and S. Reich, Dykstra's algorithm as the nonlinear extension of Bregman's optimization method, Journal of Convex Analysis 6 (1999) 319–333.
D. Butnariu, C. Byrne and Y. Censor, What is a Bregman function? Technical Report (August 2000).
D. Butnariu and Y. Censor, On the behavior of a block-iterative projection method for solving convex feasibility problems, International Journal of Computer Mathematics 34 (1990) 79–94.
D. Butnariu and Y. Censor, Strong convergence of almost simultaneous block-iterative projection methods in Hilbert spaces, Journal of Computational and Applied Mathematics 53 (1994) 33–42.
D. Butnariu, Y. Censor and S. Reich, Iterative averaging of entropic projections for solving stochastic convex feasibility, Computational Optimization and Applications 8 (1997) 21–39.
D. Butnariu, Y. Censor and S. Reich, eds., Inherently Parallel Algorithms in Feasibility and Optimization and Their Applications (Elsevier Science, Amsterdam, The Netherlands, 2001).
D. Butnariu, A.N. Iusem and R.S. Burachik, Iterative methods for solving stochastic convex feasibility problems and applications, Computational Optimization and Applications 14 (2000) 269–307.
C.L. Byrne, Iterative image reconstruction algorithms based on cross-entropy minimization, IEEE Transactions on Image Processing IP-2 (1993) 96–103.
C.L. Byrne, Erratum and addendum to “Iterative image reconstruction algorithms based on crossentropy minimization”, IEEE Transactions on Image Processing IP-4 (1995) 225–226.
C.L. Byrne, Iterative reconstruction algorithms based on cross-entropy minimization, in: Image Models (and their Speech Model Cousins), eds. S.E. Levinson and L. Shepp, IMA Volumes in Mathematics and its Applications, Vol. 80 (Springer, New York, 1996) pp. 1–11.
C.L. Byrne, Iterative projection onto convex sets using multiple Bregman distances, Inverse Problems 15 (1999) 1295–1313.
C.L. Byrne, Block-iterative interior point optimization methods for image reconstruction from limited data, Inverse Problems 16 (2000) 1405–1419.
C.L. Byrne and Y. Censor, Proximity function minimization for separable, jointly convex Bregman distances, with applications, Technical Report (February 1998).
Y. Censor, Row-action methods for huge and sparse systems and their applications, SIAM Review 23 (1981) 444–464.
Y. Censor, Parallel application of block-iterative methods in medical imaging and radiation therapy, Mathematical Programming 42 (1988) 307–325.
Y. Censor and T. Elfving, A multiprojection algorithm using Bregman projections in a product space, Numerical Algorithms 8 (1994) 221–239.
Y. Censor, D. Gordon and R. Gordon, Component averaging: an efficient iterative parallel algorithm for large and sparse unstructured problems, Parallel Computing 27 (2001) 777–808.
Y. Censor and G.T. Herman, On some optimization techniques in image reconstruction from projections, Applied Numerical Mathematics 3 (1987) 365–391.
Y. Censor, A.N. Iusem and S.A. Zenios, An interior point method with Bregman functions for the variational inequality problem with paramonotone operators, Mathematical Programming 81 (1998) 373–400.
Y. Censor and A. Lent, An iterative row-action method for interval convex programming, Journal of Optimization Theory and Applications 34 (1981) 321–353.
Y. Censor and A. Lent, Cyclic subgradient projections, Mathematical Programming 24 1996) 323–339.
Y. Censor and S. Reich, The Dykstra algorithm with Bregman projections, Communications in Applied Analysis 2 (1998) 407–419.
Y. Censor and S.A. Zenios, Parallel Optimization: Theory, Algorithms and Applications (Oxford University Press, New York, NY, USA 1997).
P.L. Combettes, The foundations of set theoretic estimation, Proceedings of the IEEE 81 (1993) 182–208.
P.L. Combettes, Inconsistent signal feasibility: Least-squares solutions in a product space, IEEE Transactions on Signal Processing SP-42 (1994) 2955–2966.
I. Csiszár and G. Tusnády, Information geometry and alternating minimization procedures, Statistics and Decisions, Supp. 1 (1984) 205-237.
A.P. Dempster, N.M. Laird and D.B. Rubin, Maximum likelihood from incomplete data via the EM algorithm, Journal of the Royal Statistical Society, Series B 37 (1977) 1–38.
R. Dykstra, An algorithm for restricted least squares regression, Journal of the American Statistical Society 78 (1983) 837–842.
R. Dykstra, An iterative procedure for obtaining I-projections onto the intersection of convex sets, The Annals of Probability 13 (1985) 975–984.
P.P.B. Eggermont and V.N. LaRiccia, On EM-like algorithms with EM-like properties for smoothed minimum distance estimation, Technical Report DE 19716, Department of Mathematical Sciences, University of Delaware, Newark, USA (March 1998).
L.G. Gubin, B.T. Polyak and E.V. Raik, The method of projections for finding the common point of convex sets, USSR Computational Mathematics and Mathematical Physics 7 (1967) 1–24.
A.N. Iusem, Convergence analysis for a multiplicatively relaxed EM algorithm, Mathematical Methods in the Applied Sciences 14 (1991) 573–593.
A.N. Iusem, A short convergence proof of the EM algorithm for a specific Poisson model, Revista Brasileira de Probabilidade e Estatistica 6 (1992) 57–67.
A.N. Iusem and A.R. De Pierro, Convergence results for an accelerated nonlinear Cimmino algorithm, Numerische Mathematik 49 (1986) 367–378.
K.C. Kiwiel, Block iterative surrogate projection methods for convex feasibility problems, Linear Algebra and its Applications 215 (1995) 225–259.
K.C. Kiwiel, Free-steering relaxation methods for problems with strictly convex costs and linear constraints, Mathematics of Operations Research 22 (1997) 326–349.
S. Kullback and R. Leibler, On information and sufficiency, Annals of Mathematical Statistics 22 (1951) 79–86.
K. Lange and R. Carson, EM reconstruction algorithms for emission and transmission tomography, Journal of Computer Assisted Tomography 8 (1984) 306–316.
F. Matúš, On iterated averages of I-projections, Technical Report (March 1997).
G.J. McLachlan and T. Krishnan, The EM Algorithm and Extensions (Wiley, New York, NY, 1997).
G. Pierra, Decomposition through formalization in a product space, Mathematical Programming 28 (1984) 96–115.
R.T. Rockafellar, Convex Analysis (Princeton University Press, Princeton, NJ, 1970).
M.V. Solodov and B.F. Svaiter, An inexact hybrid generalized proximal point algorithm and some new results on the theory of Bregman functions, Mathematics of Operations Research 25 (2000) 214–230.
H. Stark and Y. Yang, Vector Space Projections: A Numerical Approach to Signal and Image Processing, Neural Nets and Optics (Wiley, New York, NY, 1998).
E. Tanaka, A fast reconstruction algorithm for stationary positron emission tomography based on a modified EM algorithm, IEEE Transactions on Medical Imaging MI-6 (1987) 98–105.
Y. Vardi, L.A. Shepp and L. Kaufman, A statistical model for positron emission tomography, Journal of the American Statistical Association 80 (1985) 8–20.
D.C. Youla, Mathematical theory of image restoration by the method of convex projections, in: Image Recovery: Theory and Applications, ed. H. Stark (Academic Press, Orlando, FL, 1987) pp. 29–78.
Author information
Authors and Affiliations
Rights and permissions
About this article
Cite this article
Byrne, C., Censor, Y. Proximity Function Minimization Using Multiple Bregman Projections, with Applications to Split Feasibility and Kullback–Leibler Distance Minimization. Annals of Operations Research 105, 77–98 (2001). https://doi.org/10.1023/A:1013349430987
Issue Date:
DOI: https://doi.org/10.1023/A:1013349430987