A multiprojection algorithm using Bregman projections in a product space. (English) Zbl 0828.65065

Censor, Yair; Elfving, Tommy

Numer. Algorithms 8, No. 2-4, 221-239 (1994).

Generalized distances give rise to generalized projections into convex sets. An important question is whether or not one can use, within the same projection algorithm, different types of such generalized projections. This question has practical consequences in the area of signal detection and image recovery in situations that can be formulated mathematically as a convex feasibility problem.
Using an extension of Pierra’s product space formalism, it is shown that a multiprojection algorithm converges. The algorithm is fully simultaneous, i.e., it uses all sets of the convex feasibility problem in each iterative step. Different multiprojection algorithms can be derived from this algorithmic scheme by a judicious choice of the Bregman functions that govern the process.
As a by-product of the investigation, the authors obtain block-iterative schemes for certain kinds of linearly constrained optimization problems.

Reviewer: J.Guddat (Berlin)

MSC:

65K05	Numerical mathematical programming methods
90C30	Nonlinear programming

Keywords:

convergence; signal detection; image recovery; convex feasibility problem; Pierra’s product space; multiprojection algorithm; Bregman functions; block-iterative schemes; linearly constrained optimization

References:

[1]	H.H. Bauschke and J.M. Borwein, On projection algorithms for solving convex feasibility problems, Research Report 93-12, Dept. of Mathematics and Statistics, Simon Fraser University, Burnaby, BC, Canada (June 1993). · Zbl 0865.47039
[2]	A Ben-Israel and T.N.E. Greville,Generalized Inverses, Theory and Applications (Wiley, 1974). · Zbl 0305.15001
[3]	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 Comp. Math. Math. Phys. 7 (1967) 200–217. · Zbl 0186.23807
[4]	D. Butnariu and Y. Censor, On the behavior of a block-iterative projection method for solving convex feasibility problems. Int. J. Comp. Math. 34 (1990) 79–94. · Zbl 0708.90064
[5]	C.L. Byrne, Iterative image reconstruction algorithms based on cross-entropy minimization, IEEE Trans. Image Proc. IP-2 (1993) 96–103.
[6]	Y. Censor, Row-action methods for huge and sparse systems and their applications, SIAM Rev. 23 (1981) 444–464. · Zbl 0469.65037
[7]	Y. Censor, A.R. De Pierro, T. Elfving, G.T. Herman and A.N. Iusem, On iterative methods for linearily constrained entropy maximization, in:Numerical Analysis and Mathematical Modelling, ed. A. Wakulicz, Banach Center Publications (PWN-Polish Scientific Publishers, Warsaw, Poland, 1990) pp. 145–163. · Zbl 0718.65047
[8]	Y. Censor and A. Lent, An iterative row-action method for interval convex programming, J. Optim. Theory Appl. 34 (1981) 321–353. · Zbl 0431.49042
[9]	Y. Censor and J. Segman, On block-iterative entropy maximization. J. Inf. Optim. Sci. 8 (1987) 275–291. · Zbl 0631.90087
[10]	Y. Censor, Parallel application of block-iterative methods in medical imaging and radiation therapy, Math. Progr. 42 (1988) 307–325. · Zbl 0658.90099
[11]	Y. Censor and S.A. Zenios, Proximal maximization algorithm with D-functions, J. Optim. Theory Appl. 73 (1992) 451–464. · Zbl 0794.90058
[12]	P.L. Combettes, The foundations of set theoretic estimation, Proc. IEEE 81 (1993) 182–208.
[13]	I. Csiszár, Why least squares and maximum entropy? An axiomatic approach to inference for linear inverse problems. Ann. Statist. 19 (1991) 2032–2066. · Zbl 0753.62003
[14]	J.N. Darroch and D. Ratcliff, Generalized iterative scaling for log-linear models, Ann. Math. Statist. 43 (1972) 1470–1480. · Zbl 0251.62020
[15]	A.R. De Pierro and A.N. Iusem, A relaxed version of Bregman’s method for convex programming, J. Optim. Theory Appl. 51 (1986) 421–440. · Zbl 0581.90069
[16]	J. Eckstein, Nonlinear proximal point algorithms using Bregman functions, with applications to convex programming. Math. Oper. Res. 18 (1993) 202–226. · Zbl 0807.47036
[17]	P.P.B. Eggermont, G.T. Herman and A. Lent, Iterative algorithms for large partitioned linear systems, with applications to image reconstruction, Lin. Alg. Appl. 40 (1981) 37–67. · Zbl 0466.65021
[18]	P.P.B. Eggermont, Multiplicative iterative algorithms for convex programming, Lin. Alg. Appl. 130 (1990) 25–42. · Zbl 0715.65037
[19]	T. Elfving, Block-iterative methods for consistent and inconsistent linear equations, Numer. Math. 35 (1980) 1–12. · Zbl 0416.65031
[20]	T. Elfving, On some methods for entropy maximization and matrix scaling, Lin. Alg. Appl. 34 (1980) 321–339. · Zbl 0458.65052
[21]	T. Elfving, An algorithm for maximum entropy image reconstruction from noisy data, Math. Comp. Mod. 12 (1989) 729–745. · Zbl 0691.68102
[22]	L.G. Gubin, B.T. Polyak and E.V. Raik, The method of projection for finding the common point of convex sets, USSR Comp. Math. Math. Phys. 7 (1967) 1–24. · Zbl 0199.51002
[23]	S.P. Han, A successive projection method, Math. Progr. 40 (1988) 1–14. · Zbl 0685.90074
[24]	N.E. Hurt,Phase Retrieval and Zero Crossings: Mathematical Methods in Image Reconstruction (Kluwer Academic, Dordrecht, The Netherlands, 1989). · Zbl 0687.94001
[25]	A.N. Iusem, On dual convergence and the rate of primal convergence of Bregman’s convex programming method, SIAM J. Optim. 1 (1991) 401–423. · Zbl 0753.90051
[26]	A.N. Iusem, and A.R. De Pierro, On the convergence of Han’s method for convex programming with quadratic objective, Math. Progr. 52 (1991) 265–284. · Zbl 0744.90066
[27]	L.K. Jones and C.L. Byrne, General entropy criteria for inverse problems, with application to data compression, pattern classification and cluster analysis, IEEE Trans. Inf. Theory IT-36 (1990) 23–30. · Zbl 0731.62016
[28]	K.C. Kiwiel, Block-iterative surrogate projection methods for convex feasibility problems, Technical Report, Systems Research Inst., Polish Academy of Sciences, Newelska 6, 01-447, Warsaw, Poland (December 1992).
[29]	T. Kotzer, N. Cohen and J. Shamir, Extended and alternative projections onto convex sets: theory and applications, Technical Report No. EE 900, Dept. of Electrical Engineering, Technion, Haifa, Israel (November 1993).
[30]	G. Pierra, Decomposition through formalization in a product space. Math. Progr. 28 (1984) 96–115. · Zbl 0523.49022
[31]	R.T. Rockafellar,Convex Analysis (Princeton University Press, Princeton, NJ 1970). · Zbl 0193.18401
[32]	H. Stark (ed.),Image Recovery: Theory and Applications (Academic Press, Orlando, FL, 1987). · Zbl 0627.94001
[33]	A.E. Taylor,Introduction to Functional Analysis (Wiley, New York, 1967).
[34]	M. Teboulle, Entropic proximal mappings with applications to nonlinear programming, Math. Oper. Res. 17 (1992) 670–690. · Zbl 0766.90071