Local linear convergence for alternating and averaged nonconvex projections

Abstract The idea of a finite collection of closed sets having “linearly regular inter-section ” 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. Communicated by Michael Todd