Local linear convergence for alternating and averaged nonconvex projections

DOI10.1007/s10208-008-9036-yzbMath1169.49030arXiv0709.0109OpenAlexW2158902838MaRDI QIDQ839655

Jérôme Malick, Adrian S. Lewis, D. Russell Luke

Publication date: 2 September 2009

Published in: Foundations of Computational Mathematics (Search for Journal in Brave)

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

zbMATH Keywords

linearly regular intersectionNeumann's method of alternating projectionsregularity and convergence rate

Mathematics Subject Classification ID

Nonlinear programming (90C30) Numerical optimization and variational techniques (65K10) Newton-type methods (49M15)

Related Items (96)

Necessary conditions for non-intersection of collections of sets ⋮ On local convergence of the method of alternating projections ⋮ Primal necessary characterizations of transversality properties ⋮ Dual sufficient characterizations of transversality properties ⋮ Critical angles between two convex cones. I: General theory ⋮ Alternating projection method for a class of tensor equations ⋮ Linear convergence of the generalized Douglas-Rachford algorithm for feasibility problems ⋮ Local linear convergence for alternating and averaged nonconvex projections ⋮ Online distributed design for control cost reduction ⋮ Accelerated reflection projection algorithm and its application to the LMI problem ⋮ Local convergence of the heavy-ball method and iPiano for non-convex optimization ⋮ Douglas-Rachford splitting for nonconvex optimization with application to nonconvex feasibility problems ⋮ Convergence rates with inexact non-expansive operators ⋮ Phase retrieval with one or two diffraction patterns by alternating projections with the null initialization ⋮ Alternating projection, ptychographic imaging and phase synchronization ⋮ Local Linear Convergence of the ADMM/Douglas--Rachford Algorithms without Strong Convexity and Application to Statistical Imaging ⋮ Regularity properties of non-negative sparsity sets ⋮ Local convergence properties of Douglas-Rachford and alternating direction method of multipliers ⋮ Local Linear Convergence of Alternating Projections in Metric Spaces with Bounded Curvature ⋮ Restricted normal cones and the method of alternating projections: applications ⋮ Restricted normal cones and the method of alternating projections: theory ⋮ On Cluster-Aware Supervised Learning: Frameworks, Convergent Algorithms, and Applications ⋮ Some new characterizations of intrinsic transversality in Hilbert spaces ⋮ Transversality in variational analysis ⋮ Alternating projections on nontangential manifolds ⋮ Set regularities and feasibility problems ⋮ Perturbation of error bounds ⋮ Restricted normal cones and sparsity optimization with affine constraints ⋮ Geometric and metric characterizations of transversality properties ⋮ Nonnegative low rank tensor approximations with multidimensional image applications ⋮ Convergence Rate Analysis for Averaged Fixed Point Iterations in Common Fixed Point Problems ⋮ Transversality and alternating projections for nonconvex sets ⋮ Low-rank nonnegative tensor approximation via alternating projections and sketching ⋮ Regularity of sets under a reformulation in a product space with reduced dimension ⋮ A Subgradient-Based Approach for Finding the Maximum Feasible Subsystem with Respect to a Set ⋮ A Proximal Average for Prox-Bounded Functions ⋮ Convergence of descent methods for semi-algebraic and tame problems: proximal algorithms, forward-backward splitting, and regularized Gauss-Seidel methods ⋮ Provable Phase Retrieval with Mirror Descent ⋮ A difference-of-convex approach for split feasibility with applications to matrix factorizations and outlier detection ⋮ Calmness of partial perturbation to composite rank constraint systems and its applications ⋮ METRIC REGULARITY—A SURVEY PART 1. THEORY ⋮ METRIC REGULARITY—A SURVEY PART II. APPLICATIONS ⋮ Structure-Preserving Function Approximation via Convex Optimization ⋮ An infeasible-point subgradient method using adaptive approximate projections ⋮ Generalized Newton's method based on graphical derivatives ⋮ Local linear convergence of approximate projections onto regularized sets ⋮ The method of alternating relaxed projections for two nonconvex sets ⋮ Activity Identification and Local Linear Convergence of Douglas–Rachford/ADMM under Partial Smoothness ⋮ About \([q\)-regularity properties of collections of sets] ⋮ A Hybrid Penalty Method for a Class of Optimization Problems with Multiple Rank Constraints ⋮ A Lyapunov-type approach to convergence of the Douglas-Rachford algorithm for a nonconvex setting ⋮ Projection methods for quantum channel construction ⋮ About intrinsic transversality of pairs of sets ⋮ Unnamed Item ⋮ About subtransversality of collections of sets ⋮ A new projection method for finding the closest point in the intersection of convex sets ⋮ Finding a low-rank basis in a matrix subspace ⋮ Frame completion with prescribed norms via alternating projection method ⋮ A cyclic Douglas-Rachford iteration scheme ⋮ Prox-regularity of rank constraint sets and implications for algorithms ⋮ Quantitative characterizations of regularity properties of collections of sets ⋮ Duality and Convex Programming ⋮ A convergent relaxation of the Douglas-Rachford algorithm ⋮ Linear convergence of the Douglas–Rachford method for two closed sets ⋮ Convex combination of alternating projection and Douglas-Rachford operators for phase retrieval ⋮ Variational Phase Retrieval with Globally Convergent Preconditioned Proximal Algorithm ⋮ On angles between convex sets in Hilbert spaces ⋮ The rate of convergence for the cyclic projections algorithm. III: Regularity of convex sets ⋮ Projection Methods in Conic Optimization ⋮ Set intersection problems: supporting hyperplanes and quadratic programming ⋮ Unnamed Item ⋮ Alternating conditional gradient method for convex feasibility problems ⋮ Transversality properties: primal sufficient conditions ⋮ Constraint reduction reformulations for projection algorithms with applications to wavelet construction ⋮ Necessary conditions for linear convergence of iterated expansive, set-valued mappings ⋮ REGULARITY PROPERTIES IN VARIATIONAL ANALYSIS AND APPLICATIONS IN OPTIMISATION ⋮ Convergence Analysis of the Relaxed Douglas--Rachford Algorithm ⋮ Bregman proximal mappings and Bregman-Moreau envelopes under relative prox-regularity ⋮ Quantitative Convergence Analysis of Iterated Expansive, Set-Valued Mappings ⋮ Nonconvex Lagrangian-Based Optimization: Monitoring Schemes and Global Convergence ⋮ Linear Convergence of Projection Algorithms ⋮ A note on the finite convergence of alternating projections ⋮ Norm convergence of realistic projection and reflection methods ⋮ On characterizations of submanifolds via smoothness of the distance function in Hilbert spaces ⋮ Extremality, stationarity and generalized separation of collections of sets ⋮ Stochastic (Approximate) Proximal Point Methods: Convergence, Optimality, and Adaptivity ⋮ Alternating projections with applications to Gerchberg-Saxton error reduction ⋮ SURVEY: SIXTY YEARS OF DOUGLAS–RACHFORD ⋮ Local linear convergence for inexact alternating projections on nonconvex sets ⋮ APPLICATION OF PROJECTION ALGORITHMS TO DIFFERENTIAL EQUATIONS: BOUNDARY VALUE PROBLEMS ⋮ Minimization of non-smooth, non-convex functionals by iterative thresholding ⋮ Generating Correlation Matrices With Specified Eigenvalues Using the Method of Alternating Projections ⋮ Splitting methods with variable metric for Kurdyka-Łojasiewicz functions and general convergence rates ⋮ Method of alternating projections for the general absolute value equation ⋮ Optimization on Spheres: Models and Proximal Algorithms with Computational Performance Comparisons ⋮ Variational texture synthesis with sparsity and spectrum constraints

Uses Software

• LMIRank

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Local linear convergence for alternating and averaged nonconvex projections
• The rate of convergence for the cyclic projections algorithm. I: Angles between convex sets
• The rate of convergence for the cyclic projections algorithm. II: Norms of nonlinear operators
• Generalized pole placement via static output feedback: a methodology based on projections
• A Newton-like method for solving rank constrained linear matrix inequalities
• Method of successive projections for finding a common point of sets in metric spaces
• Failure of metric regularity for major classes of variational systems
• Optimization methods and stability of inclusions in Banach spaces
• Maximum principle in the problem of time optimal response with nonsmooth constraints
• On the convergence of von Neumann's alternating projection algorithm for two sets
• First-order conditions for isolated locally optimal solutions
• On the asymptotics of constrained local \(M\)-estimators.
• Low-order control design for LMI problems using alternating projection methods
• Linear programming, complexity theory and elementary functional analysis
• Subsmooth sets: Functional characterizations and related concepts
• Robust uncertainty principles: exact signal reconstruction from highly incomplete frequency information
• Designing structured tight frames via an alternating projection method
• Decomposition through formalization in a product space
• Existence and Differentiability of Metric Projections in Hilbert Spaces
• Constructing a Hermitian Matrix from Its Diagonal Entries and Eigenvalues
• Variational Analysis
• Inexact Variants of the Proximal Point Algorithm without Monotonicity
• Local differentiability of distance functions
• Optimized Projections for Compressed Sensing
• Proximal Methods for Cohypomonotone Operators
• On Projection Algorithms for Solving Convex Feasibility Problems
• Condition Numbers, the Barrier Method, and the Conjugate-Gradient Method
• The radius of metric regularity
• Incorporating Condition Measures into the Complexity Theory of Linear Programming
• On the Least Squares Solution of Inverse Eigenvalue Problems
• Sparsity and incoherence in compressive sampling
• Alternating Projections on Manifolds
• Convergence of the Proximal Point Method for Metrically Regular Mappings
• Numerical Methods for Solving Inverse Eigenvalue Problems for Nonnegative Matrices
• The method of projections for finding the common point of convex sets
• Local Convergence of the Proximal Point Algorithm and Multiplier Methods Without Monotonicity
• Functional Operators (AM-21), Volume 1
• Compressed sensing
• Best approximation in inner product spaces

This page was built for publication: Local linear convergence for alternating and averaged nonconvex projections