Local linear convergence for alternating and averaged nonconvex projections

DOI10.1007/s10208-008-9036-yzbMath1169.49030arXiv0709.0109MaRDI 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 intersection; Neumann's method of alternating projections; regularity and convergence rate

Mathematics Subject Classification ID

90C30: Nonlinear programming

65K10: Numerical optimization and variational techniques

49M15: Newton-type methods

Related Items

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

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