# Nonconvex Matrix Factorization is Geodesically Convex: Global Landscape Analysis for Fixed-rank Matrix Optimization From a Riemannian Perspective arXiv: https://arxiv.org/abs/2209.15130 ยท HTML: https://mlsanity.com/paper/2209.15130/ ## Key facts - Cited by 4 papers in the map (data through 14 Oct 2026). - Builds on 45 of its 92 references that are in the map. - First posted on arXiv 29 Sep 2022. ## Builds on (most cited first, 30 of 45) - [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) - [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) - [Gradient Descent Can Take Exponential Time to Escape Saddle Points](https://mlsanity.com/paper/1705.10412/) (2017) - [Gradient Descent with Random Initialization: Fast Global Convergence for Nonconvex Phase Retrieval](https://mlsanity.com/paper/1803.07726/) (2018) - [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) - [Complete Dictionary Recovery over the Sphere I: Overview and the Geometric Picture](https://mlsanity.com/paper/1511.03607/) (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 Convergent Gradient Descent Algorithm for Rank Minimization and Semidefinite Programming from Random Linear Measurements](https://mlsanity.com/paper/1506.06081/) (2015) - [Algorithmic Regularization in Model-free Overparametrized Asymmetric Matrix Factorization](https://mlsanity.com/paper/2203.02839/) (2022) - [Escaping from saddle points on Riemannian manifolds](https://mlsanity.com/paper/1906.07355/) (2019) - [Low-rank matrix recovery with composite optimization: good conditioning and rapid convergence](https://mlsanity.com/paper/1904.10020/) (2019) - [When Are Nonconvex Problems Not Scary?](https://mlsanity.com/paper/1510.06096/) (2015) - [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) - [A Unified Computational and Statistical Framework for Nonconvex Low-Rank Matrix Estimation](https://mlsanity.com/paper/1610.05275/) (2016) - [Deterministic guarantees for Burer-Monteiro factorizations of smooth semidefinite programs](https://mlsanity.com/paper/1804.02008/) (2018) - [A Well-Tempered Landscape for Non-convex Robust Subspace Recovery](https://mlsanity.com/paper/1706.03896/) (2017) - [Robust PCA by Manifold Optimization](https://mlsanity.com/paper/1708.00257/) (2017) - [Model-free Nonconvex Matrix Completion: Local Minima Analysis and Applications in Memory-efficient Kernel PCA](https://mlsanity.com/paper/1711.01742/) (2017) ## Built on by (most cited first, 4 of 4) - [Forward-backward Gaussian variational inference via JKO in the Bures-Wasserstein Space](https://mlsanity.com/paper/2304.05398/) (2023) - [Spectral Neural Networks: Approximation Theory and Optimization Landscape](https://mlsanity.com/paper/2310.00729/) (2023) - [Invex Programs: First Order Algorithms and Their Convergence](https://mlsanity.com/paper/2307.04456/) (2023) - [Rapid mixing for Gibbs measures in Riemannian manifolds](https://mlsanity.com/paper/2606.13453/) (2026) ## Abstract (arXiv) We study a general matrix optimization problem with a fixed-rank positive semidefinite (PSD) constraint. We perform the Burer-Monteiro factorization and consider a particular Riemannian quotient geometry in a search space that has a total space equipped with the Euclidean metric. When the original objective f satisfies standard restricted strong convexity and smoothness properties, we characterize the global landscape of the factorized objective under the Riemannian quotient geometry. We show the entire search space can be divided into three regions: (R1) the region near the target parameter of interest, where the factorized objective is geodesically strongly convex and smooth; (R2) the region containing neighborhoods of all strict saddle points; (R3) the remaining regions, where the factorized objective has a large gradient. To our best knowledge, this is the first global landscape analysis of the Burer-Monteiro factorized objective under the Riemannian quotient geometry. Our results provide a fully geometric explanation for the superior performance of vanilla gradient descent under the Burer-Monteiro factorization. When f satisfies a weaker restricted strict convexity property, we show there exists a neighborhood near local minimizers such that the factorized objective is geodesically convex. To prove our results, we provide a comprehensive landscape analysis of a matrix factorization problem with a least squares objective, which serves as a critical bridge. Our conclusions are also based on a result of independent interest stating that the geodesic ball centered at Y with a radius 1/3 of the least singular value of Y is a geodesically convex set under the Riemannian quotient geometry, which as a corollary, also implies a quantitative bound of the convexity radius in the Bures-Wasserstein space. The convexity radius obtained is sharp up to constants.