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

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.**H. H. Bauschke, J. M. Borwein, and A. S. Lewis,*The method of cyclic projections for closed convex sets in Hilbert space*, Recent developments in optimization theory and nonlinear analysis (Jerusalem, 1995), 1-38, Contemporary Mathematics 204, Amer. Math. Soc., Providence, R.I., 1997. MR**98c:49069****3.**J. B. Conway,*A Course in Functional Analysis*(second edition), Graduate Texts in Mathematics 96, Springer-Verlag, New York, 1990. MR**91e:46001****4.**L. Debnath and P. Mikusinski,*Introduction to Hilbert Spaces with Applications*(second edition), Academic Press, San Diego, CA, 1999. MR**99k:46001****5.**F. Deutsch,*Rate of convergence of the method of alternating projections*, Parametric Optimization and Approximation, ISNM 72 (B. Brosowski and F. Deutsch, eds.), Birkhäuser, Basel, 1985, pp. 96-107. MR**88d:41026****6.**F. Deutsch,*The method of alternating orthogonal projections*, in Approximation Theory, Spline Functions and Applications (S. P. Singh, ed.), Kluwer Academic Publ., Dordrecht, 1992, pp. 105-121. MR**93a:41047****7.**F. Deutsch,*The angle between subspaces of a Hilbert space*, in Approximation Theory, Wavelets and Applications (S.P. Singh, ed.), Kluwer Academic Publ., Dordrecht, pp. 107-130. MR**96e:46027****8.**F. Deutsch and H. Hundal,*The rate of convergence of Dykstra's cyclic projections algorithm: the polyhedral case*, Numer. Funct. Anal. and Optimiz.**15**no. 5-6 (1994), 537-565. MR**95f:49047****9.**F. Deutsch and H. Hundal,*The rate of convergence for the method of alternating projections, II*, J. Math. Anal. Appl.**205**(1997), 381-405. MR**97i:41025****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), 305-314. MR**87f:41058****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.**W. B. Gearhart and M. Koshy,*Acceleration schemes for the method of alternating projections*, J. Comp. Appl. Math.**26**(1989), 235-249. MR**90h:65095****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.**I. Halperin,*The product of projection operators*, Acta. Sci. Math. (Szeged)**23**(1962), 96-99. MR**25:5373****16.**M. Hanke and W. Niethammer,*On the acceleration of Kaczmarz's method for inconsistent linear systems*, Linear Algebra Appl.**130**(1990), 83-98. MR**91f:65065****17.**S. Kayalar and H. Weinert,*Error bounds for the method of alternating projections*, Math. Control Signals Systems**1**(1988), 43-59. MR**89b:65137****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.**K. T. Smith, D. C. Solmon, and S. L. Wagner,*Practical and mathematical aspects of the problem of reconstructing objects from radiographs*, Bull. Amer. Math. Soc.**83**(1976), 1227-1270. MR**58:9394a**

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