Remote Access Transactions of the American Mathematical Society
Green Open Access

Transactions of the American Mathematical Society

ISSN 1088-6850(online) ISSN 0002-9947(print)



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
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.

References [Enhancements On Off] (What's this?)

Similar Articles

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

Frank Deutsch
Affiliation: Department of Mathematics, The Pennsylvania State University, University Park, Pennsylvania 16802

Hein Hundal
Affiliation: NONRAND, 12100 Wiltshire #1650, Los Angeles, California 90025
Address at time of publication: 146 Cedar Ridge Drive, Port Matilda, Pennsylvania 16870

Sung-Ho Park
Affiliation: Department of Mathematics, Sogang University, Seoul, Korea

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