Local linear convergence for alternating and averaged nonconvex projections

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

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

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

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

• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• 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
• 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
• The method of projections for finding the common point of convex sets
• Best approximation in inner product spaces
• 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
• Linear programming, complexity theory and elementary functional analysis
• Condition Numbers, the Barrier Method, and the Conjugate-Gradient Method
• 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
• METRIC REGULARITY—A SURVEY PART II. APPLICATIONS
• 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
• Nonconvex Lagrangian-Based Optimization: Monitoring Schemes and Global Convergence
• Activity Identification and Local Linear Convergence of Douglas–Rachford/ADMM under Partial Smoothness
• 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
• On local convergence of the method of alternating projections
• Critical angles between two convex cones. I: General theory
• METRIC REGULARITY—A SURVEY PART 1. 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
• On the convergence of von Neumann's alternating projection algorithm for two sets
• About intrinsic transversality of pairs of sets
• A convergent relaxation of the Douglas-Rachford algorithm
• 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
• 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
• Phase retrieval with one or two diffraction patterns by alternating projections with the null initialization
• 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
• Linear convergence of the Douglas–Rachford method for two closed sets
• Convex combination of alternating projection and Douglas-Rachford operators for phase retrieval
• An infeasible-point subgradient method using adaptive approximate projections
• Convergence Rate Analysis for Averaged Fixed Point Iterations in Common Fixed Point Problems
• Alternating projection, ptychographic imaging and phase synchronization
• The rate of convergence for the cyclic projections algorithm. III: Regularity of convex sets
• 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
• Title not available (Why is that?)
• Linear Convergence of Projection Algorithms
• Transversality and alternating projections for nonconvex sets
• Minimization of non-smooth, non-convex functionals by iterative thresholding
• Local Linear Convergence of the ADMM/Douglas--Rachford Algorithms without Strong Convexity and Application to Statistical Imaging
• 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
• Norm convergence of realistic projection and reflection methods
• Title not available (Why is that?)
• Finding a low-rank basis in a matrix subspace
• Alternating projections on nontangential manifolds
• Transversality in variational analysis
• Duality and Convex Programming
• 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
• Generating Correlation Matrices With Specified Eigenvalues Using the Method of Alternating Projections
• Perturbation of error bounds
• Provable Phase Retrieval with Mirror Descent
• Variational Phase Retrieval with Globally Convergent Preconditioned Proximal Algorithm
• Quantitative Convergence Analysis of Iterated Expansive, Set-Valued Mappings
• SURVEY: SIXTY YEARS OF DOUGLAS–RACHFORD
• A difference-of-convex approach for split feasibility with applications to matrix factorizations and outlier detection
• A Hybrid Penalty Method for a Class of Optimization Problems with Multiple Rank Constraints
• On angles between convex sets in Hilbert spaces
• Necessary conditions for linear convergence of iterated expansive, set-valued mappings
• 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
• A Proximal Average for Prox-Bounded Functions
• 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
• A Subgradient-Based Approach for Finding the Maximum Feasible Subsystem with Respect to a Set
• Low-rank nonnegative tensor approximation via alternating projections and sketching
• Alternating projections with applications to Gerchberg-Saxton error reduction
• APPLICATION OF PROJECTION ALGORITHMS TO DIFFERENTIAL EQUATIONS: BOUNDARY VALUE PROBLEMS
• Accelerated reflection projection algorithm and its application to the LMI problem
• Global convergence and acceleration of projection methods for feasibility problems involving union convex sets

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)