Local linear convergence for alternating and averaged nonconvex projections
From MaRDI portal
(Redirected from Publication:839655)
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.
Recommendations
Cites work
- scientific article; zbMATH DE number 3888400 (Why is no real title available?)
- scientific article; zbMATH DE number 3539991 (Why is no real title available?)
- scientific article; zbMATH DE number 1113627 (Why is no real title available?)
- scientific article; zbMATH DE number 1424235 (Why is no real title available?)
- scientific article; zbMATH DE number 3229228 (Why is no real title available?)
- A Newton-like method for solving rank constrained linear matrix inequalities
- Alternating Projections on Manifolds
- Alternating proximal algorithms for weakly coupled convex minimization problems. Applications to dynamical games and PDE's
- Best approximation in inner product spaces
- Compressed sensing
- Condition Numbers, the Barrier Method, and the Conjugate-Gradient Method
- Constructing a Hermitian Matrix from Its Diagonal Entries and Eigenvalues
- Convergence of the Proximal Point Method for Metrically Regular Mappings
- Decomposition through formalization in a product space
- Designing structured tight frames via an alternating projection method
- Existence and Differentiability of Metric Projections in Hilbert Spaces
- Failure of metric regularity for major classes of variational systems
- First-order conditions for isolated locally optimal solutions
- Functional Operators (AM-21), Volume 1
- Generalized pole placement via static output feedback: a methodology based on projections
- Incorporating Condition Measures into the Complexity Theory of Linear Programming
- Inexact Variants of the Proximal Point Algorithm without Monotonicity
- Linear programming, complexity theory and elementary functional analysis
- 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
- Low-order control design for LMI problems using alternating projection methods
- Maximum principle in the problem of time optimal response with nonsmooth constraints
- Method of successive projections for finding a common point of sets in metric spaces
- Numerical Methods for Solving Inverse Eigenvalue Problems for Nonnegative Matrices
- On Projection Algorithms for Solving Convex Feasibility Problems
- On the Least Squares Solution of Inverse Eigenvalue Problems
- On the asymptotics of constrained local M-estimators.
- On the convergence of von Neumann's alternating projection algorithm for two sets
- Optimization methods and stability of inclusions in Banach spaces
- Optimized Projections for Compressed Sensing
- Proximal Methods for Cohypomonotone Operators
- Robust uncertainty principles: exact signal reconstruction from highly incomplete frequency information
- Sparsity and incoherence in compressive sampling
- Subsmooth sets: Functional characterizations and related concepts
- The method of projections for finding the common point of convex sets
- The radius of metric regularity
- 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
- Variational Analysis
Cited in
(only showing first 100 items - show all)- Generalized Newton's method based on graphical derivatives
- Local linear convergence of approximate projections onto regularized sets
- Projection Methods in Conic Optimization
- A Lyapunov-type approach to convergence of the Douglas-Rachford algorithm for a nonconvex setting
- Finding a low-rank basis in a matrix subspace
- Calmness of partial perturbation to composite rank constraint systems and its applications
- Norm convergence of realistic projection and reflection methods
- 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
- Global convergence of a second-order augmented Lagrangian method under an error bound condition
- 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
- Dual sufficient characterizations of transversality properties
- Primal necessary characterizations of transversality properties
- Quantitative characterizations of regularity properties of collections of sets
- Frame completion with prescribed norms via alternating projection method
- Prox-regularity of rank constraint sets and implications for algorithms
- Restricted normal cones and sparsity optimization with affine constraints
- Online distributed design for control cost reduction
- Linear convergence of the generalized Douglas-Rachford algorithm for feasibility problems
- Method of alternating projections for the general absolute value equation
- Generalized alternating projections on manifolds and convex sets
- 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
- Local Convergence of a Two-Piece Update of a Projected Hessian Matrix
- Metric regularity -- a survey. II: Applications
- Critical angles between two convex cones. I: General theory
- Local linear convergence of alternating projections in metric spaces with bounded curvature
- Alternating projection method for a class of tensor equations
- Linear convergence of projection algorithms
- Restricted normal cones and the method of alternating projections: applications
- Restricted normal cones and the method of alternating projections: theory
- Convergence Analysis of the Relaxed Douglas--Rachford Algorithm
- Optimization on Spheres: Models and Proximal Algorithms with Computational Performance Comparisons
- Generating Correlation Matrices With Specified Eigenvalues Using the Method of Alternating Projections
- Convergence rate analysis for averaged fixed point iterations in common fixed point problems
- On the convergence of von Neumann's alternating projection algorithm for two sets
- Perturbation of error bounds
- Local convergence of the error-reduction algorithm for real-valued objects
- Alternating Projections on Manifolds
- Algorithms for structured nonconvex optimization: theory and practice
- About intrinsic transversality of pairs of sets
- Local geometry of feasible regions via smooth paths
- Structure-preserving function approximation via convex optimization
- A convergent relaxation of the Douglas-Rachford algorithm
- Metric regularity -- a survey. I: Theory
- Douglas-Rachford splitting for nonconvex optimization with application to nonconvex feasibility problems
- Local convergence of the heavy-ball method and iPiano for non-convex optimization
- Nonlinear transversality of collections of sets: dual space necessary characterizations
- Local linear convergence for alternating and averaged nonconvex projections
- Transversality properties: primal sufficient conditions
- Provable Phase Retrieval with Mirror Descent
- 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
- A difference-of-convex approach for split feasibility with applications to matrix factorizations and outlier detection
- Extremality, stationarity and generalized separation of collections of sets
- Quantitative Convergence Analysis of Iterated Expansive, Set-Valued Mappings
- SURVEY: SIXTY YEARS OF DOUGLAS–RACHFORD
- Convergence of descent methods for semi-algebraic and tame problems: proximal algorithms, forward-backward splitting, and regularized Gauss-Seidel methods
- Exact convergence rates of alternating projections for nontransversal intersections
- Convergence rates with inexact non-expansive operators
- Splitting methods with variable metric for Kurdyka-Łojasiewicz functions and general convergence rates
- Set regularities and feasibility problems
- Stochastic (Approximate) Proximal Point Methods: Convergence, Optimality, and Adaptivity
- On angles between convex sets in Hilbert spaces
- Nonconvex Lagrangian-based optimization: monitoring schemes and global convergence
- An infeasible-point subgradient method using adaptive approximate projections
- Necessary conditions for linear convergence of iterated expansive, set-valued mappings
- Convex combination of alternating projection and Douglas-Rachford operators for phase retrieval
- On characterizations of submanifolds via smoothness of the distance function in Hilbert spaces
- Application of projection algorithms to differential equations: boundary value problems
- Alternating projection, ptychographic imaging and phase synchronization
- Alternating conditional gradient method for convex feasibility problems
- The rate of convergence for the cyclic projections algorithm. III: Regularity of convex sets
- Regularity of collections of sets and convergence of inexact alternating projections
- Linear convergence of the Douglas-Rachford method for two closed sets
- Some new characterizations of intrinsic transversality in Hilbert spaces
- Local linear convergence of the ADMM/Douglas-Rachford algorithms without strong convexity and application to statistical imaging
- 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
- Regularity properties of non-negative sparsity sets
- A cyclic Douglas-Rachford iteration scheme
- Quasioptimal alternating projections and their use in low-rank approximation of matrices and tensors
- The method of alternating relaxed projections for two nonconvex sets
- About \([q]\)-regularity properties of collections of sets
- Local linear convergence for inexact alternating projections on nonconvex sets
- A note on the finite convergence of alternating projections
- Necessary conditions for non-intersection of collections of sets
- Metric subregularity and \(\omega (\cdot)\)-normal regularity properties
- Extremality of families of sets
- Inexact reduced gradient methods in nonconvex optimization
- Set intersection problems: supporting hyperplanes and quadratic programming
- Projection methods for quantum channel construction
- Alternating projections with applications to Gerchberg-Saxton error reduction
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)
