The Method of Alternating Projections

点击翻译按钮获取中文摘要

DMS Award AbstractAward #: 0204569PI: Deutsch, FrankInstitution: Pennsylvania State University, University ParkProgram: Applied MathematicsProgram Manager: Catherine MavriplisTitle: The Method of Alternating ProjectionsThe 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