The Method of Alternating Projections

Pennsylvania State Univ University Park, University Park PA

Investigators

Abstract

DMS Award Abstract Award #: 0204569 PI: Deutsch, Frank Institution: Pennsylvania State University, University Park Program: Applied Mathematics Program Manager: Catherine Mavriplis Title: The Method of Alternating Projections The method of alternating projections (MAP) is an iterative procedure for determining nearest points from a set that is the intersection of a finite number of closed convex sets. This method has found use in at least 15 different areas of mathematics, which includes solving linear equations and inequalities, signal analysis, and computed tomography. The main practical drawback of the MAP, at least for some applications, is its slow convergence. We will study rates of convergence for the MAP by extending the notion of ``angle'' between subspaces to that of more general convex sets, as well as determine means for accelerating the convergence of the MAP. In addition, we expect to show that the speed of convergence of the MAP is directly related to a property (the ``strong conical hull intersection'' property) of the convex sets in question that we have studied in several papers over the last 20 years. The method of alternating projections is an algorithm for computing nearest points in certain sets by a repetitive application of the same few simple steps. Since the method has applications to so many different areas of mathematics (one of the earliest being in medical imaging via X-rays), it is important to know how fast (i.e., how many steps) this algorithm needs to take before the results give good accuracy of the exact solution. The ``rate of convergence'' of the algorithm deals with the question of how fast the algorithm is for any given problem. For those problems when the rate of convergence is slow, we will also study ways to make the algorithm work faster by making appropriate modifications of certain steps in the algorithm. Date: May 13, 2002