# Nonconvex Factorization and Manifold Formulations are Almost Equivalent in Low-rank Matrix Optimization arXiv: https://arxiv.org/abs/2108.01772 ยท HTML: https://mlsanity.com/paper/2108.01772/ ## Key facts - Cited by 4 papers in the map (data through 14 Oct 2026). - Builds on 54 of its 98 references that are in the map. - First posted on arXiv 3 Aug 2021. ## Builds on (most cited first, 30 of 54) - [How to Escape Saddle Points Efficiently](https://mlsanity.com/paper/1703.00887/) (2017) - [Escaping From Saddle Points --- Online Stochastic Gradient for Tensor Decomposition](https://mlsanity.com/paper/1503.02101/) (2015) - [Algorithmic Regularization in Learning Deep Homogeneous Models: Layers are Automatically Balanced](https://mlsanity.com/paper/1806.00900/) (2018) - [Nonconvex Optimization Meets Low-Rank Matrix Factorization: An Overview](https://mlsanity.com/paper/1809.09573/) (2018) - [No Spurious Local Minima in Nonconvex Low Rank Problems: A Unified Geometric Analysis](https://mlsanity.com/paper/1704.00708/) (2017) - [Phase Retrieval via Wirtinger Flow: Theory and Algorithms](https://mlsanity.com/paper/1407.1065/) (2014) - [Low-rank Solutions of Linear Matrix Equations via Procrustes Flow](https://mlsanity.com/paper/1507.03566/) (2015) - [A Geometric Analysis of Phase Retrieval](https://mlsanity.com/paper/1602.06664/) (2016) - [Global Optimality of Local Search for Low Rank Matrix Recovery](https://mlsanity.com/paper/1605.07221/) (2016) - [Accelerating Ill-Conditioned Low-Rank Matrix Estimation via Scaled Gradient Descent](https://mlsanity.com/paper/2005.08898/) (2020) - [Fast low-rank estimation by projected gradient descent: General statistical and algorithmic guarantees](https://mlsanity.com/paper/1509.03025/) (2015) - [Implicit Regularization in Nonconvex Statistical Estimation: Gradient Descent Converges Linearly for Phase Retrieval, Matrix Completion, and Blind Deconvolution](https://mlsanity.com/paper/1711.10467/) (2017) - [Global rates of convergence for nonconvex optimization on manifolds](https://mlsanity.com/paper/1605.08101/) (2016) - [Phase Retrieval using Alternating Minimization](https://mlsanity.com/paper/1306.0160/) (2013) - [Solving Random Quadratic Systems of Equations Is Nearly as Easy as Solving Linear Systems](https://mlsanity.com/paper/1505.05114/) (2015) - [Global Convergence of Gradient Descent for Asymmetric Low-Rank Matrix Factorization](https://mlsanity.com/paper/2106.14289/) (2021) - [Dropping Convexity for Faster Semi-definite Optimization](https://mlsanity.com/paper/1509.03917/) (2015) - [Non-square matrix sensing without spurious local minima via the Burer-Monteiro approach](https://mlsanity.com/paper/1609.03240/) (2016) - [Global Optimality in Low-rank Matrix Optimization](https://mlsanity.com/paper/1702.07945/) (2017) - [A Brief Introduction to Manifold Optimization](https://mlsanity.com/paper/1906.05450/) (2019) - [A Convergent Gradient Descent Algorithm for Rank Minimization and Semidefinite Programming from Random Linear Measurements](https://mlsanity.com/paper/1506.06081/) (2015) - [Escaping from saddle points on Riemannian manifolds](https://mlsanity.com/paper/1906.07355/) (2019) - [Understanding Alternating Minimization for Matrix Completion](https://mlsanity.com/paper/1312.0925/) (2013) - [Low-rank matrix recovery with composite optimization: good conditioning and rapid convergence](https://mlsanity.com/paper/1904.10020/) (2019) - [Solving Systems of Random Quadratic Equations via Truncated Amplitude Flow](https://mlsanity.com/paper/1605.08285/) (2016) - [From Symmetry to Geometry: Tractable Nonconvex Problems](https://mlsanity.com/paper/2007.06753/) (2020) - [Low-Rank Matrix Recovery with Scaled Subgradient Methods: Fast and Robust Convergence Without the Condition Number](https://mlsanity.com/paper/2010.13364/) (2020) - [Sharp Restricted Isometry Bounds for the Inexistence of Spurious Local Minima in Nonconvex Matrix Recovery](https://mlsanity.com/paper/1901.01631/) (2019) - [The Global Optimization Geometry of Low-Rank Matrix Optimization](https://mlsanity.com/paper/1703.01256/) (2017) - [Efficiently escaping saddle points on manifolds](https://mlsanity.com/paper/1906.04321/) (2019) ## Built on by (most cited first, 4 of 4) - [Nonconvex Matrix Factorization is Geodesically Convex: Global Landscape Analysis for Fixed-rank Matrix Optimization From a Riemannian Perspective](https://mlsanity.com/paper/2209.15130/) (2022) - [On Geometric Connections of Embedded and Quotient Geometries in Riemannian Fixed-rank Matrix Optimization](https://mlsanity.com/paper/2110.12121/) (2021) - [Structured Variational D-Decomposition for Accurate and Stable Low-Rank Approximation](https://mlsanity.com/paper/2506.08535/) (2025) - [Over-parameterization Is Neither Robust nor Fragile in Matrix Sensing: A Geometric Theory of Solution Robustness](https://mlsanity.com/paper/2610.18318/) (2026) ## Abstract (arXiv) 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.