Local linear convergence of approximate projections onto regularized sets

DOI10.1016/J.NA.2011.08.027MaRDI QIDQ654094zbMATH OpenOpenAlexFDO

Authors D. Russell Luke

Publication date 21 December 2011

Published in Nonlinear Analysis. Theory, Methods \& Applications. Series A: Theory and Methods (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1108.2243

zbMATH Keywords

computational complexityregularizationmetric regularityvariational analysisextremal principlelinear convergencenonconvexityalternating projections of von Neumann typedistance to ill-posednessprox-regular sets

Mathematics Subject Classification ID

Numerical optimization and variational techniques (65K10) Nonlinear programming (90C30) Numerical methods of relaxation type (49M20)

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.

Recommendations

• Local linear convergence for alternating and averaged nonconvex projections
• Local linear convergence for inexact alternating projections on nonconvex sets
• Regularity of collections of sets and convergence of inexact alternating projections
• Algorithms for structured nonconvex optimization: theory and practice

Cites work

• scientific article; zbMATH DE number 3888400 (Why is no real title available?)
• scientific article; zbMATH DE number 823375 (Why is no real title available?)
• A primal-dual projection method for solving systems of linear inequalities
• About regularity of collections of sets
• Convergence of the Proximal Point Method for Metrically Regular Mappings
• Finding Best Approximation Pairs Relative to a Convex and Prox-Regular Set in a Hilbert Space
• Finding best approximation pairs relative to two closed convex sets in Hilbert spaces
• Inexact Variants of the Proximal Point Algorithm without Monotonicity
• Local Convergence of the Proximal Point Algorithm and Multiplier Methods Without Monotonicity
• Local differentiability of distance functions
• Local linear convergence for alternating and averaged nonconvex projections
• On rings of operators. Reduction theory
• Proximity Maps for Convex Sets
• Relaxed averaged alternating reflections for diffraction imaging
• Splitting Algorithms for the Sum of Two Nonlinear Operators
• Variational Analysis
• Variational Analysis Applied to the Problem of Optical Phase Retrieval
• Variational Analysis and Generalized Differentiation I

Cited in

(10)

• Local linear convergence of the ADMM/Douglas-Rachford algorithms without strong convexity and application to statistical imaging
• Quantitative characterizations of regularity properties of collections of sets
• Quantitative Convergence Analysis of Iterated Expansive, Set-Valued Mappings
• Provable Phase Retrieval with Mirror Descent
• Prox-regularity of rank constraint sets and implications for algorithms
• Optimization on Spheres: Models and Proximal Algorithms with Computational Performance Comparisons
• About \([q]\)-regularity properties of collections of sets
• Convex combination of alternating projection and Douglas-Rachford operators for phase retrieval
• Restricted normal cones and the method of alternating projections: applications
• Restricted normal cones and sparsity optimization with affine constraints

This page was built for publication: Local linear convergence of approximate projections onto regularized sets

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q654094)