mlsanityData to 13 Oct 2026

Nonconvex Matrix Factorization is Geodesically Convex: Global Landscape Analysis for Fixed-rank Matrix Optimization From a Riemannian Perspective

arXiv 2209.15130 ↗First posted 29 Sep 2022math.OC cs.IT cs.LGcited by 4

Not on the map. Why?

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.

Key facts. Cited by 4 papers in the map (data through 13 Oct 2026). Builds on 45 of its 92 references that are in the map. First posted on arXiv 29 Sep 2022.

Builds on

45 of 92 references.

References · 45

  1. 2017How to Escape Saddle Points Efficientlycited by 284
  2. 2015Escaping From Saddle Points --- Online Stochastic Gradient for Tensor Decompositioncited by 242
  3. 2017No Spurious Local Minima in Nonconvex Low Rank Problems: A Unified Geometric Analysiscited by 127
  4. 2014Phase Retrieval via Wirtinger Flow: Theory and Algorithmscited by 125
  5. 2015Low-rank Solutions of Linear Matrix Equations via Procrustes Flowcited by 97
  6. 2016A Geometric Analysis of Phase Retrievalcited by 92
  7. 2016Global Optimality of Local Search for Low Rank Matrix Recoverycited by 81
  8. 2017Gradient Descent Can Take Exponential Time to Escape Saddle Pointscited by 74
  9. 2018Gradient Descent with Random Initialization: Fast Global Convergence for Nonconvex Phase Retrievalcited by 71
  10. 2020Accelerating Ill-Conditioned Low-Rank Matrix Estimation via Scaled Gradient Descentcited by 70
  11. 2015Fast low-rank estimation by projected gradient descent: General statistical and algorithmic guaranteescited by 68
  12. 2017Implicit Regularization in Nonconvex Statistical Estimation: Gradient Descent Converges Linearly for Phase Retrieval, Matrix Completion, and Blind Deconvolutioncited by 63
33 more
  1. 2015Complete Dictionary Recovery over the Sphere I: Overview and the Geometric Picturecited by 49
  2. 2021Global Convergence of Gradient Descent for Asymmetric Low-Rank Matrix Factorizationcited by 45
  3. 2015Dropping Convexity for Faster Semi-definite Optimizationcited by 40
  4. 2016Non-square matrix sensing without spurious local minima via the Burer-Monteiro approachcited by 38
  5. 2017Global Optimality in Low-rank Matrix Optimizationcited by 36
  6. 2015A Convergent Gradient Descent Algorithm for Rank Minimization and Semidefinite Programming from Random Linear Measurementscited by 34
  7. 2022Algorithmic Regularization in Model-free Overparametrized Asymmetric Matrix Factorizationcited by 34
  8. 2019Escaping from saddle points on Riemannian manifoldscited by 33
  9. 2019Low-rank matrix recovery with composite optimization: good conditioning and rapid convergencecited by 31
  10. 2015When Are Nonconvex Problems Not Scary?cited by 28
  11. 2019Sharp Restricted Isometry Bounds for the Inexistence of Spurious Local Minima in Nonconvex Matrix Recoverycited by 26
  12. 2017The Global Optimization Geometry of Low-Rank Matrix Optimizationcited by 24
  13. 2019Efficiently escaping saddle points on manifoldscited by 24
  14. 2016A Unified Computational and Statistical Framework for Nonconvex Low-Rank Matrix Estimationcited by 21
  15. 2017A Well-Tempered Landscape for Non-convex Robust Subspace Recoverycited by 18
  16. 2018Deterministic guarantees for Burer-Monteiro factorizations of smooth semidefinite programscited by 17
  17. 2017Robust PCA by Manifold Optimizationcited by 13
  18. 2017Model-free Nonconvex Matrix Completion: Local Minima Analysis and Applications in Memory-efficient Kernel PCAcited by 12
  19. 2018Rank optimality for the Burer-Monteiro factorizationcited by 12
  20. 2021General Low-rank Matrix Optimization: Geometric Analysis and Sharper Boundscited by 12
  21. 2018On the Landscape of Synchronization Networks: A Perspective from Nonconvex Optimizationcited by 11
  22. 2020Recursive Importance Sketching for Rank Constrained Least Squares: Algorithms and High-order Convergencecited by 11
  23. 2020Solving Orthogonal Group Synchronization via Convex and Low-Rank Optimization: Tightness and Landscape Analysiscited by 10
  24. 2020How Many Samples is a Good Initial Point Worth in Low-rank Matrix Recovery?cited by 10
  25. 2017Solving SDPs for synchronization and MaxCut problems via the Grothendieck inequalitycited by 8
  26. 2021Local and Global Linear Convergence of General Low-rank Matrix Recovery Problemscited by 8
  27. 2022Noisy Low-rank Matrix Optimization: Geometry of Local Minima and Convergence Ratecited by 7
  28. 2016The Non-convex Geometry of Low-rank Matrix Optimizationcited by 6
  29. 2021Factorization Approach for Low-complexity Matrix Completion Problems: Exponential Number of Spurious Solutions and Failure of Gradient Methodscited by 6
  30. 2021Nonconvex Factorization and Manifold Formulations are Almost Equivalent in Low-rank Matrix Optimizationcited by 3
  31. 2021On Geometric Connections of Embedded and Quotient Geometries in Riemannian Fixed-rank Matrix Optimizationcited by 3
  32. 2019On The Geometric Analysis of A Quartic-quadratic Optimization Problem under A Spherical Constraintcited by 1
  33. 2022On the analysis of optimization with fixed-rank matrices: a quotient geometric viewcited by 1

Built on by

Cited by year (2026 to 13 Oct)

Citing papers per year: 2023: 3; 2024: 0; 2025: 0; 2026: 1.

4 papers.

  1. 2023Forward-backward Gaussian variational inference via JKO in the Bures-Wasserstein Spacecited by 36
  2. 2023Spectral Neural Networks: Approximation Theory and Optimization Landscapecited by 2
  3. 2023Invex Programs: First Order Algorithms and Their Convergencecited by 1
  4. 2026Rapid mixing for Gibbs measures in Riemannian manifoldscited by 0