Accelerating the convergence of the method of alternating projections

Bauschke, Heinz; Deutsch, Frank; Hundal, Hein; Park, Sung-Ho

doi:10.1090/S0002-9947-03-03136-2

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