# The Global Optimization Geometry of Low-Rank Matrix Optimization

arXiv: https://arxiv.org/abs/1703.01256 · HTML: https://mlsanity.com/paper/1703.01256/

## Key facts

- Cited by 25 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 3 Mar 2017.

## Built on by (most cited first, 25 of 25)

- [Understanding Incremental Learning of Gradient Descent: A Fine-grained Analysis of Matrix Sensing](https://mlsanity.com/paper/2301.11500/) (2023)
- [How Over-Parameterization Slows Down Gradient Descent in Matrix Sensing: The Curses of Symmetry and Initialization](https://mlsanity.com/paper/2310.01769/) (2023)
- [Noisy Low-rank Matrix Optimization: Geometry of Local Minima and Convergence Rate](https://mlsanity.com/paper/2203.03899/) (2022)
- [Guaranteed Nonconvex Factorization Approach for Tensor Train Recovery](https://mlsanity.com/paper/2401.02592/) (2024)
- [Sharp Restricted Isometry Property Bounds for Low-rank Matrix Recovery Problems with Corrupted Measurements](https://mlsanity.com/paper/2105.08232/) (2021)
- [Escaping strict saddle points of the Moreau envelope in nonsmooth optimization](https://mlsanity.com/paper/2106.09815/) (2021)
- [Federated Representation Learning in the Under-Parameterized Regime](https://mlsanity.com/paper/2406.04596/) (2024)
- [On the Learn-to-Optimize Capabilities of Transformers in In-Context Sparse Recovery](https://mlsanity.com/paper/2410.13981/) (2024)
- [Semidefinite Programming versus Burer-Monteiro Factorization for Matrix Sensing](https://mlsanity.com/paper/2208.07469/) (2022)
- [Nonconvex Factorization and Manifold Formulations are Almost Equivalent in Low-rank Matrix Optimization](https://mlsanity.com/paper/2108.01772/) (2021)
- [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)
- [Computational and Statistical Guarantees for Tensor-on-Tensor Regression with Tensor Train Decomposition](https://mlsanity.com/paper/2406.06002/) (2024)
- [Efficient Over-parameterized Matrix Sensing from Noisy Measurements via Alternating Preconditioned Gradient Descent](https://mlsanity.com/paper/2502.00463/) (2025)
- [Can Learning Be Explained By Local Optimality In Robust Low-rank Matrix Recovery?](https://mlsanity.com/paper/2302.10963/) (2023)
- [Gradient descent in matrix factorization: Understanding large initialization](https://mlsanity.com/paper/2305.19206/) (2023)
- [Implicit Regularization Makes Overparameterized Asymmetric Matrix Sensing Robust to Perturbations](https://mlsanity.com/paper/2309.01796/) (2023)
- [Quantization Avoids Saddle Points in Distributed Optimization](https://mlsanity.com/paper/2403.10423/) (2024)
- [Uncertainty Quantification For Low-Rank Matrix Completion With Heterogeneous and Sub-Exponential Noise](https://mlsanity.com/paper/2110.12046/) (2021)
- [Convergence Analysis for Learning Orthonormal Deep Linear Neural Networks](https://mlsanity.com/paper/2311.14658/) (2023)
- [Euclidean Distance Matrix Completion via Asymmetric Projected Gradient Descent](https://mlsanity.com/paper/2504.19530/) (2025)
- [Robust matrix completion via Novel M-estimator Functions](https://mlsanity.com/paper/2310.04953/) (2023)
- [Community Detection Guarantees Using Embeddings Learned by Node2Vec](https://mlsanity.com/paper/2310.17712/) (2023)
- [ℓ1-norm rank-one symmetric matrix factorization has no spurious second-order stationary points](https://mlsanity.com/paper/2410.05025/) (2024)
- [Learning the Supports for Categorical Critic in Reinforcement Learning](https://mlsanity.com/paper/2607.01880/) (2026)
- [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)

This paper considers general rank-constrained optimization problems that minimize a general objective function f(X) over the set of rectangular n× m matrices that have rank at most r. To tackle the rank constraint and also to reduce the computational burden, we factorize X into UVT where U and V are n× r and m× r matrices, respectively, and then optimize over the small matrices U and V. We characterize the global optimization geometry of the nonconvex factored problem and show that the corresponding objective function satisfies the robust strict saddle property as long as the original objective function f satisfies restricted strong convexity and smoothness properties, ensuring global convergence of many local search algorithms (such as noisy gradient descent) in polynomial time for solving the factored problem. We also provide a comprehensive analysis for the optimization geometry of a matrix factorization problem where we aim to find n× r and m× r matrices U and V such that UVT approximates a given matrix X^star. Aside from the robust strict saddle property, we show that the objective function of the matrix factorization problem has no spurious local minima and obeys the strict saddle property not only for the exact-parameterization case where rank(X^star) = r, but also for the over-parameterization case where rank(X^star) < r and the under-parameterization case where rank(X^star) > r. These geometric properties imply that a number of iterative optimization algorithms (such as gradient descent) converge to a global solution with random initialization.