zbMATH — the first resource for mathematics

Geometry Search for the term Geometry in any field. Queries are case-independent.
Funct* Wildcard queries are specified by * (e.g. functions, functorial, etc.). Otherwise the search is exact.
"Topological group" Phrases (multi-words) should be set in "straight quotation marks".
au: Bourbaki & ti: Algebra Search for author and title. The and-operator & is default and can be omitted.
Chebyshev | Tschebyscheff The or-operator | allows to search for Chebyshev or Tschebyscheff.
"Quasi* map*" py: 1989 The resulting documents have publication year 1989.
so: Eur* J* Mat* Soc* cc: 14 Search for publications in a particular source with a Mathematics Subject Classification code (cc) in 14.
"Partial diff* eq*" ! elliptic The not-operator ! eliminates all results containing the word elliptic.
dt: b & au: Hilbert The document type is set to books; alternatively: j for journal articles, a for book articles.
py: 2000-2015 cc: (94A | 11T) Number ranges are accepted. Terms can be grouped within (parentheses).
la: chinese Find documents in a given language. ISO 639-1 language codes can also be used.

a & b logic and
a | b logic or
!ab logic not
abc* right wildcard
"ab c" phrase
(ab c) parentheses
any anywhere an internal document identifier
au author, editor ai internal author identifier
ti title la language
so source ab review, abstract
py publication year rv reviewer
cc MSC code ut uncontrolled term
dt document type (j: journal article; b: book; a: book article)
A multiprojection algorithm using Bregman projections in a product space. (English) Zbl 0828.65065

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.

65K05Mathematical programming (numerical methods)
90C30Nonlinear programming
[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).
[2]A Ben-Israel and T.N.E. Greville,Generalized Inverses, Theory and Applications (Wiley, 1974).
[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. · doi:10.1016/0041-5553(67)90040-7
[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 · doi:10.1080/00207169008803865
[5]C.L. Byrne, Iterative image reconstruction algorithms based on cross-entropy minimization, IEEE Trans. Image Proc. IP-2 (1993) 96–103. · doi:10.1109/83.210869
[6]Y. Censor, Row-action methods for huge and sparse systems and their applications, SIAM Rev. 23 (1981) 444–464. · Zbl 0469.65037 · doi:10.1137/1023097
[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.
[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 · doi:10.1007/BF00934676
[9]Y. Censor and J. Segman, On block-iterative entropy maximization. J. Inf. Optim. Sci. 8 (1987) 275–291.
[10]Y. Censor, Parallel application of block-iterative methods in medical imaging and radiation therapy, Math. Progr. 42 (1988) 307–325. · Zbl 0658.90099 · doi:10.1007/BF01589408
[11]Y. Censor and S.A. Zenios, Proximal maximization algorithm with D-functions, J. Optim. Theory Appl. 73 (1992) 451–464. · Zbl 0794.90058 · doi:10.1007/BF00940051
[12]P.L. Combettes, The foundations of set theoretic estimation, Proc. IEEE 81 (1993) 182–208. · doi:10.1109/5.214546
[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 · doi:10.1214/aos/1176348385
[14]J.N. Darroch and D. Ratcliff, Generalized iterative scaling for log-linear models, Ann. Math. Statist. 43 (1972) 1470–1480. · Zbl 0251.62020 · doi:10.1214/aoms/1177692379
[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 · doi:10.1007/BF00940283
[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 · doi:10.1287/moor.18.1.202
[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 · doi:10.1016/0024-3795(81)90139-7
[18]P.P.B. Eggermont, Multiplicative iterative algorithms for convex programming, Lin. Alg. Appl. 130 (1990) 25–42. · Zbl 0715.65037 · doi:10.1016/0024-3795(90)90204-P
[19]T. Elfving, Block-iterative methods for consistent and inconsistent linear equations, Numer. Math. 35 (1980) 1–12. · Zbl 0416.65031 · doi:10.1007/BF01396365
[20]T. Elfving, On some methods for entropy maximization and matrix scaling, Lin. Alg. Appl. 34 (1980) 321–339. · Zbl 0458.65052 · doi:10.1016/0024-3795(80)90171-8
[21]T. Elfving, An algorithm for maximum entropy image reconstruction from noisy data, Math. Comp. Mod. 12 (1989) 729–745. · Zbl 0691.68102 · doi:10.1016/0895-7177(89)90358-0
[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 · doi:10.1016/0041-5553(67)90113-9
[23]S.P. Han, A successive projection method, Math. Progr. 40 (1988) 1–14. · Zbl 0685.90074 · doi:10.1007/BF01580719
[24]N.E. Hurt,Phase Retrieval and Zero Crossings: Mathematical Methods in Image Reconstruction (Kluwer Academic, Dordrecht, The Netherlands, 1989).
[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 · doi:10.1137/0801025
[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 · doi:10.1007/BF01582891
[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 · doi:10.1109/18.50370
[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 · doi:10.1007/BF02612715
[31]R.T. Rockafellar,Convex Analysis (Princeton University Press, Princeton, NJ 1970).
[32]H. Stark (ed.),Image Recovery: Theory and Applications (Academic Press, Orlando, FL, 1987).
[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 · doi:10.1287/moor.17.3.670