Accelerating the convergence of the method of alternating projections

Authors:
Heinz H. Bauschke, Frank Deutsch, Hein Hundal and Sung-Ho Park

Journal:
Trans. Amer. Math. Soc. **355** (2003), 3433-3461

MSC (2000):
Primary 41A65

DOI:
https://doi.org/10.1090/S0002-9947-03-03136-2

Published electronically:
May 29, 2003

MathSciNet review:
1990157

Full-text PDF Free Access

Abstract | References | Similar Articles | Additional Information

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.

**1.**N. Aronszajn,*Theory of reproducing kernels*, Trans. Amer. Math. Soc., 68(1950), 337-404. MR**14:479c****2.**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**, https://doi.org/10.1090/conm/204/02620**3.**John B. Conway,*A course in functional analysis*, 2nd ed., Graduate Texts in Mathematics, vol. 96, Springer-Verlag, New York, 1990. MR**1070713****4.**Lokenath Debnath and Piotr Mikusiński,*Introduction to Hilbert spaces with applications*, 2nd ed., Academic Press, Inc., San Diego, CA, 1999. MR**1670332****5.**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****6.**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****7.**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****8.**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**, https://doi.org/10.1080/01630569408816580**9.**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**, https://doi.org/10.1006/jmaa.1997.5202**10.**J. Dyer,*Acceleration of the convergence of the Kaczmarz method and iterated homogeneous transformations*, doctoral dissertation (1965).**11.**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**, https://doi.org/10.1016/0022-247X(86)90085-5**12.**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.**13.**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**, https://doi.org/10.1016/0377-0427(89)90296-3**14.**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.**15.**Israel Halperin,*The product of projection operators*, Acta Sci. Math. (Szeged)**23**(1962), 96–99. MR**0141978****16.**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**, https://doi.org/10.1016/0024-3795(90)90207-S**17.**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**, https://doi.org/10.1007/BF02551235**18.**J. von Neumann,*Functional Operators. II*, Princeton University Press, Princeton, NJ, 1950. [This is a reprint of mimeograghed lecture notes first distributed in 1933.] MR**11:599e****19.**F. Riesz and B. Sz.-Nagy,*Über Kontraktionen des Hilbertschen Raumes*, Acta. Sci. Math.**10**(1941-1943), 202-205. MR**8:35a****20.**F. Riesz and B. Sz.-Nagy,*Functional Analysis*, Ungar, New York, 1955. MR**17:175i****21.**R. Smarzewski,*Iterative recovering of orthogonal projections*, preprint (December, 1996).**22.**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**0490032**, https://doi.org/10.1090/S0002-9904-1977-14406-6

Kennan T. Smith, Donald C. Solmon, and Sheldon L. Wagner,*Addendum to: “Practical and mathematical aspects of the problem of reconstructing objects from radiographs” (Bull. Amer. Math. Soc. 83 (1977), no. 6, 1227–1270)*, Bull. Amer. Math. Soc.**84**(1978), no. 4, 691. MR**0490033**, https://doi.org/10.1090/S0002-9904-1978-14526-1

Retrieve articles in *Transactions of the American Mathematical Society*
with MSC (2000):
41A65

Retrieve articles in all journals with MSC (2000): 41A65

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

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

DOI:
https://doi.org/10.1090/S0002-9947-03-03136-2

Keywords:
Alternating projections,
cyclic projections,
accelerating convergence,
best approximation from an intersection of subspaces,
Hilbert space

Received by editor(s):
July 30, 1999

Published electronically:
May 29, 2003

Article copyright:
© Copyright 2003
American Mathematical Society