Local Linear Convergence for Alternating and Averaged Nonconvex Projections |
| |
Authors: | A. S. Lewis D. R. Luke J. Malick |
| |
Affiliation: | (1) ORIE, Cornell University, Ithaca, NY 14853, USA;(2) Department of Mathematical Sciences, University of Delaware, Newark, DE 19716, USA;(3) INRIA Rhone-Alpes, 655 avenue de l’Europe, 38334 St Ismier Cedex, France |
| |
Abstract: | The idea of a finite collection of closed sets having “linearly regular intersection” at a point is crucial in variational analysis. This central theoretical condition also has striking algorithmic consequences: in the case of two sets, one of which satisfies a further regularity condition (convexity or smoothness, for example), we prove that von Neumann’s method of “alternating projections” converges locally to a point in the intersection, at a linear rate associated with a modulus of regularity. As a consequence, in the case of several arbitrary closed sets having linearly regular intersection at some point, the method of “averaged projections” converges locally at a linear rate to a point in the intersection. Inexact versions of both algorithms also converge linearly. Research of A.S. Lewis supported in part by National Science Foundation Grant DMS-0504032. Research of D.R. Luke supported in part by National Science Foundation Grant DMS-0712796. |
| |
Keywords: | Alternating projections Averaged projections Linear convergence Metric regularity Distance to ill-posedness Variational analysis Nonconvexity Extremal principle Prox-regularity |
本文献已被 SpringerLink 等数据库收录! |
|