Accelerating the convergence of the method of alternating projections
HTML articles powered by AMS MathViewer
- by Heinz H. Bauschke, Frank Deutsch, Hein Hundal and Sung-Ho Park PDF
- Trans. Amer. Math. Soc. 355 (2003), 3433-3461 Request permission
Abstract:
The powerful von Neumann-Halperin method of alternating projections (MAP) is an algorithm for determining the best approximation to any given point in a Hilbert space from the intersection of a finite number of subspaces. It achieves this by reducing the problem to an iterative scheme which involves only computing best approximations from the individual subspaces which make up the intersection. The main practical drawback of this algorithm, at least for some applications, is that the method is slowly convergent. In this paper, we consider a general class of iterative methods which includes the MAP as a special case. For such methods, we study an “accelerated” version of this algorithm that was considered earlier by Gubin, Polyak, and Raik (1967) and by Gearhart and Koshy (1989). We show that the accelerated algorithm converges faster than the MAP in the case of two subspaces, but is, in general, not faster than the MAP for more than two subspaces! However, for a “symmetric” version of the MAP, the accelerated algorithm always converges faster for any number of subspaces. Our proof seems to require the use of the Spectral Theorem for selfadjoint mappings.References
- P. Hebroni, Sur les inverses des éléments dérivables dans un anneau abstrait, C. R. Acad. Sci. Paris 209 (1939), 285–287 (French). MR 14
- Heinz H. Bauschke, Jonathan M. Borwein, and Adrian S. Lewis, The method of cyclic projections for closed convex sets in Hilbert space, Recent developments in optimization theory and nonlinear analysis (Jerusalem, 1995) Contemp. Math., vol. 204, Amer. Math. Soc., Providence, RI, 1997, pp. 1–38. MR 1442992, DOI 10.1090/conm/204/02620
- John B. Conway, A course in functional analysis, 2nd ed., Graduate Texts in Mathematics, vol. 96, Springer-Verlag, New York, 1990. MR 1070713
- Lokenath Debnath and Piotr Mikusiński, Introduction to Hilbert spaces with applications, 2nd ed., Academic Press, Inc., San Diego, CA, 1999. MR 1670332
- Frank Deutsch, Rate of convergence of the method of alternating projections, Parametric optimization and approximation (Oberwolfach, 1983) Internat. Schriftenreihe Numer. Math., vol. 72, Birkhäuser, Basel, 1985, pp. 96–107. MR 882199
- Frank Deutsch, The method of alternating orthogonal projections, Approximation theory, spline functions and applications (Maratea, 1991) NATO Adv. Sci. Inst. Ser. C: Math. Phys. Sci., vol. 356, Kluwer Acad. Publ., Dordrecht, 1992, pp. 105–121. MR 1165964
- Frank Deutsch, The angle between subspaces of a Hilbert space, Approximation theory, wavelets and applications (Maratea, 1994) NATO Adv. Sci. Inst. Ser. C: Math. Phys. Sci., vol. 454, Kluwer Acad. Publ., Dordrecht, 1995, pp. 107–130. MR 1340886
- Frank Deutsch and Hein Hundal, The rate of convergence of Dykstra’s cyclic projections algorithm: the polyhedral case, Numer. Funct. Anal. Optim. 15 (1994), no. 5-6, 537–565. MR 1281561, DOI 10.1080/01630569408816580
- Frank Deutsch and Hein Hundal, The rate of convergence for the method of alternating projections. II, J. Math. Anal. Appl. 205 (1997), no. 2, 381–405. MR 1428355, DOI 10.1006/jmaa.1997.5202
- J. Dyer, Acceleration of the convergence of the Kaczmarz method and iterated homogeneous transformations, doctoral dissertation (1965).
- C. Franchetti and W. Light, On the von Neumann alternating algorithm in Hilbert space, J. Math. Anal. Appl. 114 (1986), no. 2, 305–314. MR 833588, DOI 10.1016/0022-247X(86)90085-5
- K. Friedrichs, On certain inequalities and characteristic value problems for analytic functions and functions of two variables, Trans. Amer. Math. Soc. 41 (1937), 321-364.
- William B. Gearhart and Mathew Koshy, Acceleration schemes for the method of alternating projections, J. Comput. Appl. Math. 26 (1989), no. 3, 235–249. MR 1010558, DOI 10.1016/0377-0427(89)90296-3
- 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(6) (1967), 1-24.
- Israel Halperin, The product of projection operators, Acta Sci. Math. (Szeged) 23 (1962), 96–99. MR 141978
- Martin Hanke and Wilhelm Niethammer, On the acceleration of Kaczmarz’s method for inconsistent linear systems, Linear Algebra Appl. 130 (1990), 83–98. Linear algebra in image reconstruction from projections. MR 1057802, DOI 10.1016/0024-3795(90)90207-S
- Selahattin Kayalar and Howard L. Weinert, Error bounds for the method of alternating projections, Math. Control Signals Systems 1 (1988), no. 1, 43–59. MR 923275, DOI 10.1007/BF02551235
- Morgan Ward and R. P. Dilworth, The lattice theory of ova, Ann. of Math. (2) 40 (1939), 600–608. MR 11, DOI 10.2307/1968944
- A. R. Collar, On the reciprocation of certain matrices, Proc. Roy. Soc. Edinburgh 59 (1939), 195–206. MR 8, DOI 10.1017/S0370164600012281
- Saunders MacLane, Steinitz field towers for modular fields, Trans. Amer. Math. Soc. 46 (1939), 23–45. MR 17, DOI 10.1090/S0002-9947-1939-0000017-3
- R. Smarzewski, Iterative recovering of orthogonal projections, preprint (December, 1996).
- Kennan T. Smith, Donald C. Solmon, and Sheldon L. Wagner, Practical and mathematical aspects of the problem of reconstructing objects from radiographs, Bull. Amer. Math. Soc. 83 (1977), no. 6, 1227–1270. MR 490032, DOI 10.1090/S0002-9904-1977-14406-6
Additional Information
- Heinz H. Bauschke
- Affiliation: Department of Mathematics and Statistics, Okanagan University College, Kelowna, British Columbia, Canada V1V 1V7
- Address at time of publication: Department of Mathematics and Statistics, University of Guelph, Guelph, Ontario, Canada N1G 2W1
- MR Author ID: 334652
- Email: bauschke@cecm.sfu.ca
- Frank Deutsch
- Affiliation: Department of Mathematics, The Pennsylvania State University, University Park, Pennsylvania 16802
- Email: deutsch@math.psu.edu
- Hein Hundal
- Affiliation: NONRAND, 12100 Wiltshire #1650, Los Angeles, California 90025
- Address at time of publication: 146 Cedar Ridge Drive, Port Matilda, Pennsylvania 16870
- Email: hundalhm@vicon.net
- Sung-Ho Park
- Affiliation: Department of Mathematics, Sogang University, Seoul, Korea
- Email: shpark@ccs.sogang.ac.kr
- Received by editor(s): July 30, 1999
- Published electronically: May 29, 2003
- © Copyright 2003 American Mathematical Society
- Journal: Trans. Amer. Math. Soc. 355 (2003), 3433-3461
- MSC (2000): Primary 41A65
- DOI: https://doi.org/10.1090/S0002-9947-03-03136-2
- MathSciNet review: 1990157