mlsanityData to 7 Oct 2026

Nonconvex Factorization and Manifold Formulations are Almost Equivalent in Low-rank Matrix Optimization

arXiv 2108.01772 ↗First posted 3 Aug 2021math.OC cs.IT cs.LGcited by 3

Not on the map. Why?

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.

Key facts. Cited by 3 papers in the map (data through 7 Oct 2026). Builds on 54 of its 98 references that are in the map. First posted on arXiv 3 Aug 2021.

Builds on

54 of 98 references.

References · 54

  1. 2017How to Escape Saddle Points Efficientlycited by 284
  2. 2015Escaping From Saddle Points --- Online Stochastic Gradient for Tensor Decompositioncited by 241
  3. 2018Algorithmic Regularization in Learning Deep Homogeneous Models: Layers are Automatically Balancedcited by 172
  4. 2018Nonconvex Optimization Meets Low-Rank Matrix Factorization: An Overviewcited by 159
  5. 2017No Spurious Local Minima in Nonconvex Low Rank Problems: A Unified Geometric Analysiscited by 127
  6. 2014Phase Retrieval via Wirtinger Flow: Theory and Algorithmscited by 123
  7. 2015Low-rank Solutions of Linear Matrix Equations via Procrustes Flowcited by 97
  8. 2016A Geometric Analysis of Phase Retrievalcited by 92
  9. 2016Global Optimality of Local Search for Low Rank Matrix Recoverycited by 81
  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
38 more
  1. 2016Global rates of convergence for nonconvex optimization on manifoldscited by 61
  2. 2013Phase Retrieval using Alternating Minimizationcited by 58
  3. 2015Solving Random Quadratic Systems of Equations Is Nearly as Easy as Solving Linear Systemscited by 50
  4. 2021Global Convergence of Gradient Descent for Asymmetric Low-Rank Matrix Factorizationcited by 44
  5. 2015Dropping Convexity for Faster Semi-definite Optimizationcited by 40
  6. 2016Non-square matrix sensing without spurious local minima via the Burer-Monteiro approachcited by 38
  7. 2017Global Optimality in Low-rank Matrix Optimizationcited by 35
  8. 2019A Brief Introduction to Manifold Optimizationcited by 35
  9. 2015A Convergent Gradient Descent Algorithm for Rank Minimization and Semidefinite Programming from Random Linear Measurementscited by 34
  10. 2019Escaping from saddle points on Riemannian manifoldscited by 33
  11. 2013Understanding Alternating Minimization for Matrix Completioncited by 32
  12. 2019Low-rank matrix recovery with composite optimization: good conditioning and rapid convergencecited by 31
  13. 2016Solving Systems of Random Quadratic Equations via Truncated Amplitude Flowcited by 28
  14. 2020From Symmetry to Geometry: Tractable Nonconvex Problemscited by 28
  15. 2020Low-Rank Matrix Recovery with Scaled Subgradient Methods: Fast and Robust Convergence Without the Condition Numbercited by 27
  16. 2019Sharp Restricted Isometry Bounds for the Inexistence of Spurious Local Minima in Nonconvex Matrix Recoverycited by 26
  17. 2017The Global Optimization Geometry of Low-Rank Matrix Optimizationcited by 24
  18. 2019Efficiently escaping saddle points on manifoldscited by 24
  19. 2016Finding Low-Rank Solutions via Non-Convex Matrix Factorization, Efficiently and Provablycited by 22
  20. 2016A Unified Computational and Statistical Framework for Nonconvex Low-Rank Matrix Estimationcited by 21
  21. 2013Exact and Stable Covariance Estimation from Quadratic Sampling via Convex Programmingcited by 20
  22. 2014Riemannian preconditioningcited by 19
  23. 2013ROP: Matrix recovery via rank-one projectionscited by 18
  24. 2017A Well-Tempered Landscape for Non-convex Robust Subspace Recoverycited by 18
  25. 2018Deterministic guarantees for Burer-Monteiro factorizations of smooth semidefinite programscited by 17
  26. 2017Robust PCA by Manifold Optimizationcited by 13
  27. 2017A Newton-Based Method for Nonconvex Optimization with Fast Evasion of Saddle Pointscited by 12
  28. 2017Model-free Nonconvex Matrix Completion: Local Minima Analysis and Applications in Memory-efficient Kernel PCAcited by 12
  29. 2021General Low-rank Matrix Optimization: Geometric Analysis and Sharper Boundscited by 12
  30. 2020Recursive Importance Sketching for Rank Constrained Least Squares: Algorithms and High-order Convergencecited by 11
  31. 2018Smoothed analysis for low-rank solutions to semidefinite programs in quadratic penalty formcited by 10
  32. 2020Rank 2r iterative least squares: efficient recovery of ill-conditioned low rank matrices from few entriescited by 10
  33. 2020Fast Global Convergence for Low-rank Matrix Recovery via Riemannian Gradient Descent with Random Initializationcited by 8
  34. 2020The Global Geometry of Centralized and Distributed Low-rank Matrix Recovery without Regularizationcited by 7
  35. 2015The local convexity of solving systems of quadratic equationscited by 6
  36. 2016The Non-convex Geometry of Low-rank Matrix Optimizationcited by 6
  37. 2021A Riemannian rank-adaptive method for low-rank matrix completioncited by 4
  38. 2021Riemannian Perspective on Matrix Factorizationcited by 3

50 most cited of 54 All 54 (JSON)

Built on by

Cited by year

Citing papers per year: 2021: 1; 2022: 1; 2023: 0; 2024: 0; 2025: 1.

3 papers.

  1. 2021On Geometric Connections of Embedded and Quotient Geometries in Riemannian Fixed-rank Matrix Optimizationcited by 3
  2. 2022Nonconvex Matrix Factorization is Geodesically Convex: Global Landscape Analysis for Fixed-rank Matrix Optimization From a Riemannian Perspectivecited by 3
  3. 2025Structured Variational D-Decomposition for Accurate and Stable Low-Rank Approximationcited by 0