Prox-regularity of rank constraint sets and implications for algorithms
Author:
- D. Russell LukeDLD. Russell Luke
Preprint
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 on the boundary defined by points with rank exactly equal to s. 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.
Keywords
All Related Versions
This publication has 5 references indexed in Scilit:
- Local linear convergence of approximate projections onto regularized setsNonlinear Analysis, 2012
- Guaranteed Minimum-Rank Solutions of Linear Matrix Equations via Nuclear Norm MinimizationSIAM Review, 2010
- Local Linear Convergence for Alternating and Averaged Nonconvex ProjectionsFoundations of Computational Mathematics, 2008
- The charge flipping algorithmActa Crystallographica Section A Foundations of Crystallography, 2007
- Local differentiability of distance functionsTransactions of the American Mathematical Society, 2000