An equivalence between critical points for rank constraints versus low-rank factorizations

Abstract

Two common approaches in low-rank optimization problems are either working directly with a rank constraint on the matrix variable, or optimizing over a low-rank factorization so that the rank constraint is implicitly ensured. In this paper, we study the natural connection between the rank-constrained and factorized approaches. We show that all second-order stationary points of the factorized objective function correspond to fixed points of projected gradient descent run on the original problem (where the projection step enforces the rank constraint). This result allows us to unify many existing optimization guarantees that have been proved specifically in either the rank-constrained or the factorized setting, and leads to new results for certain settings of the problem. We demonstrate application of our results to several concrete low-rank optimization problems arising in matrix inverse problems.

References in corpus (17)

• Guaranteed Minimum-Rank Solutions of Linear Matrix Equations via Nuclear Norm Minimization
• Restricted strong convexity and weighted matrix completion: Optimal bounds with noise
• Global Optimality of Local Search for Low Rank Matrix Recovery
• How to Escape Saddle Points Efficiently
• Implicit Regularization in Nonconvex Statistical Estimation: Gradient Descent Converges Linearly for Phase Retrieval, Matrix Completion, and Blind Deconvolution
• Fast low-rank estimation by projected gradient descent: General statistical and algorithmic guarantees
• Low-rank Solutions of Linear Matrix Equations via Procrustes Flow
• Convergence Analysis for Rectangular Matrix Completion Using Burer-Monteiro Factorization and Gradient Descent
• On Iterative Hard Thresholding Methods for High-dimensional M-Estimation
• A Tight Bound of Hard Thresholding
• The Global Optimization Geometry of Low-Rank Matrix Optimization
• Smoothed analysis for low-rank solutions to semidefinite programs in quadratic penalty form
• Noisy Matrix Completion: Understanding Statistical Guarantees for Convex Relaxation via Nonconvex Optimization
• Randomized Low-Memory Singular Value Projection
• Between hard and soft thresholding: optimal iterative thresholding algorithms
• Fast Low-Rank Matrix Estimation without the Condition Number
• Sharp Restricted Isometry Bounds for the Inexistence of Spurious Local Minima in Nonconvex Matrix Recovery