Prox-regularity of rank constraint sets and implications for algorithms

Abstract

We present an analysis of sets of matrices with rank less than or equal to a specified number $s$. We provide a simple formula for the normal cone to such sets, and use this to show that these sets are prox-regular at all points with rank exactly equal to $s$. The normal cone formula appears to be new. This allows for easy application of prior results guaranteeing local linear convergence of the fundamental alternating projection algorithm between sets, one of which is a rank constraint set. We apply this to show local linear convergence of another fundamental algorithm, approximate steepest descent. Our results apply not only to linear systems with rank constraints, as has been treated extensively in the literature, but also nonconvex systems with rank constraints.

12 pages, 24 references. Revised manuscript to appear in the Journal of Mathematical Imaging and Vision

References in corpus (1)

• Local Linear Convergence of Approximate Projections onto Regularized Sets

Cited by in corpus (9)

• Alternating Projections and Douglas-Rachford for Sparse Affine Feasibility
• Quantitative Characterizations of Regularity Properties of Collections of Sets
• Convergence of the Forward-Backward Algorithm: Beyond the Worst Case with the Help of Geometry
• Regularity Properties of Non-Negative Sparsity Sets
• Low-rank nonnegative tensor approximation via alternating projections and sketching
• Multi-Group Multicast Beamforming by Superiorized Projections onto Convex Sets
• About [q]-regularity properties of collections of sets
• Local Convergence of Proximal Splitting Methods for Rank Constrained Problems
• Quasioptimal alternating projections and their use in low-rank approximation of matrices and tensors