Local linear convergence of approximate projections onto regularized sets

DOI10.1016/J.NA.2011.08.027zbMATH Open1236.49072arXiv1108.2243OpenAlexW2105685950MaRDI QIDQ654094FDOQ654094

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)

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.

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

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
• On local convergence of the method of alternating projections
• Algorithms for structured nonconvex optimization: theory and practice

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)

Cites Work

• On rings of operators. Reduction theory
• Splitting Algorithms for the Sum of Two Nonlinear Operators
• Variational Analysis
• Local differentiability of distance functions
• Variational Analysis and Generalized Differentiation I
• Title not available (Why is that?)
• A primal-dual projection method for solving systems of linear inequalities
• About regularity of collections of sets
• Inexact Variants of the Proximal Point Algorithm without Monotonicity
• Local Convergence of the Proximal Point Algorithm and Multiplier Methods Without Monotonicity
• Local linear convergence for alternating and averaged nonconvex projections
• 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
• Relaxed averaged alternating reflections for diffraction imaging
• Proximity Maps for Convex Sets
• Convergence of the Proximal Point Method for Metrically Regular Mappings
• Title not available (Why is that?)
• Variational Analysis Applied to the Problem of Optical Phase Retrieval

Cited In (10)

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

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)