Local linear convergence for alternating and averaged nonconvex projections

DOI10.1007/S10208-008-9036-YzbMATH Open1169.49030arXiv0709.0109OpenAlexW2158902838MaRDI QIDQ839655FDOQ839655

Authors: A. S. Lewis, Jérôme Malick, D. Russell Luke 

Publication date: 2 September 2009

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

Abstract: The idea of a finite collection of closed sets having "strongly regular intersection" at a given point is crucial in variational analysis. We show that this central theoretical tool also has striking algorithmic consequences. Specifically, we consider the case of two sets, one of which we assume to be suitably "regular" (special cases being convex sets, smooth manifolds, or feasible regions satisfying the Mangasarian-Fromovitz constraint qualification). We then 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 strongly 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.

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

Recommendations

• Local linear convergence for inexact alternating projections on nonconvex sets
• Transversality and alternating projections for nonconvex sets
• Local linear convergence of alternating projections in metric spaces with bounded curvature
• Alternating Projections on Manifolds

zbMATH Keywords

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

Mathematics Subject Classification ID

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

Cites Work

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

Cited In (only showing first 100 items - show all)

• Variational texture synthesis with sparsity and spectrum constraints
• About subtransversality of collections of sets
• A new projection method for finding the closest point in the intersection of convex sets
• Quantitative characterizations of regularity properties of collections of sets
• Dual sufficient characterizations of transversality properties
• Primal necessary characterizations of transversality properties
• Prox-regularity of rank constraint sets and implications for algorithms
• Restricted normal cones and sparsity optimization with affine constraints
• Linear convergence of the generalized Douglas-Rachford algorithm for feasibility problems
• Local Convergence of a Two-Piece Update of a Projected Hessian Matrix
• Metric regularity -- a survey. II: Applications
• Linear convergence of projection algorithms
• On local convergence of the method of alternating projections
• Critical angles between two convex cones. I: General theory
• Convergence Analysis of the Relaxed Douglas--Rachford Algorithm
• Alternating projection method for a class of tensor equations
• Optimization on Spheres: Models and Proximal Algorithms with Computational Performance Comparisons
• Restricted normal cones and the method of alternating projections: applications
• Restricted normal cones and the method of alternating projections: theory
• Convergence rate analysis for averaged fixed point iterations in common fixed point problems
• Alternating Projections on Manifolds
• Algorithms for structured nonconvex optimization: theory and practice
• On the convergence of von Neumann's alternating projection algorithm for two sets
• About intrinsic transversality of pairs of sets
• Metric regularity -- a survey. I: Theory
• Nonlinear transversality of collections of sets: dual space necessary characterizations
• A convergent relaxation of the Douglas-Rachford algorithm
• Douglas-Rachford splitting for nonconvex optimization with application to nonconvex feasibility problems
• Transversality properties: primal sufficient conditions
• Local linear convergence for alternating and averaged nonconvex projections
• Nonnegative low rank tensor approximations with multidimensional image applications
• Geometric and metric characterizations of transversality properties
• Extremality, stationarity and generalized separation of collections of sets
• Convergence of descent methods for semi-algebraic and tame problems: proximal algorithms, forward-backward splitting, and regularized Gauss-Seidel methods
• Stochastic (Approximate) Proximal Point Methods: Convergence, Optimality, and Adaptivity
• Convergence rates with inexact non-expansive operators
• Set regularities and feasibility problems
• Splitting methods with variable metric for Kurdyka-Łojasiewicz functions and general convergence rates
• Nonconvex Lagrangian-based optimization: monitoring schemes and global convergence
• An infeasible-point subgradient method using adaptive approximate projections
• Alternating projection, ptychographic imaging and phase synchronization
• Regularity of collections of sets and convergence of inexact alternating projections
• The rate of convergence for the cyclic projections algorithm. III: Regularity of convex sets
• Linear convergence of the Douglas-Rachford method for two closed sets
• Local linear convergence of the ADMM/Douglas-Rachford algorithms without strong convexity and application to statistical imaging
• A cyclic Douglas-Rachford iteration scheme
• Regularity properties of non-negative sparsity sets
• Local linear convergence for inexact alternating projections on nonconvex sets
• The method of alternating relaxed projections for two nonconvex sets
• About \([q]\)-regularity properties of collections of sets
• Set intersection problems: supporting hyperplanes and quadratic programming
• Projection methods for quantum channel construction
• Activity identification and local linear convergence of Douglas-Rachford/ADMM under partial smoothness
• Title not available (Why is that?)
• Transversality and alternating projections for nonconvex sets
• Minimization of non-smooth, non-convex functionals by iterative thresholding
• Generalized Newton's method based on graphical derivatives
• Local linear convergence of approximate projections onto regularized sets
• Projection Methods in Conic Optimization
• Calmness of partial perturbation to composite rank constraint systems and its applications
• A Lyapunov-type approach to convergence of the Douglas-Rachford algorithm for a nonconvex setting
• Finding a low-rank basis in a matrix subspace
• Alternating projections on nontangential manifolds
• Transversality in variational analysis
• Duality and Convex Programming
• A proximal average for prox-bounded functions
• On Cluster-Aware Supervised Learning: Frameworks, Convergent Algorithms, and Applications
• Frame completion with prescribed norms via alternating projection method
• Generalized alternating projections on manifolds and convex sets
• Online distributed design for control cost reduction
• Regularity of sets under a reformulation in a product space with reduced dimension
• Method of alternating projections for the general absolute value equation
• A subgradient-based approach for finding the maximum feasible subsystem with respect to a set
• Local linear convergence of alternating projections in metric spaces with bounded curvature
• Generating Correlation Matrices With Specified Eigenvalues Using the Method of Alternating Projections
• Perturbation of error bounds
• Structure-preserving function approximation via convex optimization
• Local convergence of the heavy-ball method and iPiano for non-convex optimization
• Provable Phase Retrieval with Mirror Descent
• Phase retrieval with one or two diffraction patterns by alternating projections with the null initialization
• Quantitative Convergence Analysis of Iterated Expansive, Set-Valued Mappings
• SURVEY: SIXTY YEARS OF DOUGLAS–RACHFORD
• Exact convergence rates of alternating projections for nontransversal intersections
• A difference-of-convex approach for split feasibility with applications to matrix factorizations and outlier detection
• On angles between convex sets in Hilbert spaces
• Necessary conditions for linear convergence of iterated expansive, set-valued mappings
• Convex combination of alternating projection and Douglas-Rachford operators for phase retrieval
• Application of projection algorithms to differential equations: boundary value problems
• On characterizations of submanifolds via smoothness of the distance function in Hilbert spaces
• Alternating conditional gradient method for convex feasibility problems
• Some new characterizations of intrinsic transversality in Hilbert spaces
• Regularity properties in variational analysis and applications in optimisation. (Abstract of thesis)
• Constraint reduction reformulations for projection algorithms with applications to wavelet construction
• Local convergence properties of Douglas-Rachford and alternating direction method of multipliers
• Necessary conditions for non-intersection of collections of sets
• A note on the finite convergence of alternating projections
• Metric subregularity and \(\omega (\cdot)\)-normal regularity properties
• Extremality of families of sets
• Inexact reduced gradient methods in nonconvex optimization
• Low-rank nonnegative tensor approximation via alternating projections and sketching

Uses Software

• LMIRank

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

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