Local Linear Convergence of Approximate Projections onto Regularized Sets
Author:
- D. Russell LukeDLD. Russell Luke
Preprint
Abstract
The numerical properties of algorithms for finding the intersection of sets depend to some extent on the regularity of the sets, but even more importantly on the regularity of the intersection. The alternating projection algorithm of von Neumann has been shown to converge locally at a linear rate dependent on the regularity modulus of the intersection. In many applications, however, the sets in question come from inexact measurements that are matched to idealized models. It is unlikely that any such problems in applications will enjoy metrically regular intersection, let alone set intersection. We explore a regularization strategy that generates an intersection with the desired regularity properties. The regularization, however, can lead to a significant increase in computational complexity. In a further refinement, we investigate and prove linear convergence of an approximate alternating projection algorithm. The analysis provides a regularization strategy that fits naturally with many ill-posed inverse problems, and a mathematically sound stopping criterion for extrapolated, approximate algorithms. The theory is demonstrated on the phase retrieval problem with experimental data. The conventional early termination applied in practice to unregularized, consistent problems in diffraction imaging can be justified fully in the framework of this analysis providing, for the first time, proof of convergence of alternating approximate projections for finite dimensional, consistent phase retrieval problems.Keywords
All Related Versions
This publication has 13 references indexed in Scilit:
- Local Linear Convergence for Alternating and Averaged Nonconvex ProjectionsFoundations of Computational Mathematics, 2008
- Finding Best Approximation Pairs Relative to a Convex and Prox-Regular Set in a Hilbert SpaceSIAM Journal on Optimization, 2008
- Relaxed averaged alternating reflections for diffraction imagingInverse Problems, 2004
- Finding best approximation pairs relative to two closed convex sets in Hilbert spacesJournal of Approximation Theory, 2004
- Variational Analysis Applied to the Problem of Optical Phase RetrievalSIAM Journal on Control and Optimization, 2003
- Inexact Variants of the Proximal Point Algorithm without MonotonicitySIAM Journal on Optimization, 2003
- Local differentiability of distance functionsTransactions of the American Mathematical Society, 2000
- Convex set theoretic image recovery by extrapolated iterations of parallel subgradient projectionsIEEE Transactions on Image Processing, 1997
- A primal-dual projection method for solving systems of linear inequalitiesLinear Algebra and its Applications, 1985
- Splitting Algorithms for the Sum of Two Nonlinear OperatorsSIAM Journal on Numerical Analysis, 1979