Accelerating the convergence of the method of alternating projections

Abstract. The powerful von Neumann-Halperin method of alternating pro-jections (MAP) is an algorithm for determining the best approximation to any given point in a Hilbert space from the intersection of a nite number of sub-spaces. 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 algo-rithm, 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 " ver-sion of this algorithm that was considered earlier by Gubin, Polyak, and Raik (1967) and by Gearhart and Koshy (1989). We show that the accelerated al-gorithm 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