Accelerating the convergence of the method of alternating projections

Hundal, Hein and Deutsch, F. R. and Park, Sung-Ho and Bauschke, Heinz H. (1999) Accelerating the convergence of the method of alternating projections. [Preprint]

Download (393Kb) | Preview
    Download (339Kb) | Preview


      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 {\it 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 which was considered earlier by Gubin, Polyak, and Raik [14] and by Gearhart and Koshy [13]. We show that the accelerated algorithm converges faster than the MAP in the case of two subspaces, but is in general {\it 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 self-adjoint mappings.

      Item Type: Preprint
      Additional Information: pubdom FALSE
      Uncontrolled Keywords: alternating projections, cyclic projections, accelerating convergence, best approximation from an intersection of subspaces, Hilbert space
      Subjects: 41-xx Approximations and expansions > 41Axx Approximations and expansions
      Faculty: UNSPECIFIED
      Depositing User: Users 1 not found.
      Date Deposited: 28 Nov 2003
      Last Modified: 21 Apr 2010 11:13

      Actions (login required)

      View Item