Nonconvex Factorization and Manifold Formulations are Almost Equivalent in Low-rank Matrix Optimization
arXiv:2108.01772
Abstract
In this paper, we consider the geometric landscape connection of the widely studied manifold and factorization formulations in low-rank positive semidefinite (PSD) and general matrix optimization. We establish a sandwich relation on the spectrum of Riemannian and Euclidean Hessians at first-order stationary points (FOSPs). As a result of that, we obtain an equivalence on the set of FOSPs, second-order stationary points (SOSPs) and strict saddles between the manifold and the factorization formulations. In addition, we show the sandwich relation can be used to transfer more quantitative geometric properties from one formulation to another. Similarities and differences in the landscape connection under the PSD case and the general case are discussed. To the best of our knowledge, this is the first geometric landscape connection between the manifold and the factorization formulations for handling rank constraints, and it provides a geometric explanation for the similar empirical performance of factorization and manifold approaches in low-rank matrix optimization observed in the literature. In the general low-rank matrix optimization, the landscape connection of two factorization formulations (unregularized and regularized ones) is also provided. By applying these geometric landscape connections, in particular, the sandwich relation, we are able to solve unanswered questions in literature and establish stronger results in the applications on geometric analysis of phase retrieval, well-conditioned low-rank matrix optimization, and the role of regularization in factorization arising from machine learning and signal processing.
References in corpus (26)
- Nonconvex Optimization Meets Low-Rank Matrix Factorization: An Overview
- Global rates of convergence for nonconvex optimization on manifolds
- Global Optimality of Local Search for Low Rank Matrix Recovery
- Implicit Regularization in Nonconvex Statistical Estimation: Gradient Descent Converges Linearly for Phase Retrieval, Matrix Completion, and Blind Deconvolution
- Low-rank optimization for semidefinite convex problems
- No Spurious Local Minima in Nonconvex Low Rank Problems: A Unified Geometric Analysis
- Fast low-rank estimation by projected gradient descent: General statistical and algorithmic guarantees
- Matrix Completion from a Few Entries
- The Non-convex Geometry of Low-rank Matrix Optimization
- A Riemannian rank-adaptive method for low-rank matrix completion
- Efficiently escaping saddle points on manifolds
- Beyond Procrustes: Balancing-Free Gradient Descent for Asymmetric Low-Rank Matrix Sensing
- From Symmetry to Geometry: Tractable Nonconvex Problems
- The Global Geometry of Centralized and Distributed Low-rank Matrix Recovery without Regularization
- Model-free Nonconvex Matrix Completion: Local Minima Analysis and Applications in Memory-efficient Kernel PCA
- Escaping from saddle points on Riemannian manifolds
- Solving systems of phaseless equations via Riemannian optimization with optimal sampling complexity
- Fast Global Convergence for Low-rank Matrix Recovery via Riemannian Gradient Descent with Random Initialization
- Rank iterative least squares: efficient recovery of ill-conditioned low rank matrices from few entries
- Recursive Importance Sketching for Rank Constrained Least Squares: Algorithms and High-order Convergence
- Global Convergence of Gradient Descent for Asymmetric Low-Rank Matrix Factorization
- General Low-rank Matrix Optimization: Geometric Analysis and Sharper Bounds
- Riemannian Perspective on Matrix Factorization
- Escape saddle points faster on manifolds via perturbed Riemannian stochastic recursive gradient
- A Line-Search Descent Algorithm for Strict Saddle Functions with Complexity Guarantees
- An equivalent nonlinear optimization model with triangular low-rank factorization for semidefinite programs