# Global Optimality in Low-rank Matrix Optimization

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

## Key facts

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

## Built on by (most cited first, 30 of 36)

- [A Geometric Analysis of Neural Collapse with Unconstrained Features](https://mlsanity.com/paper/2105.02375/) (2021)
- [Understanding Incremental Learning of Gradient Descent: A Fine-grained Analysis of Matrix Sensing](https://mlsanity.com/paper/2301.11500/) (2023)
- [Rank Overspecified Robust Matrix Recovery: Subgradient Method and Exact Recovery](https://mlsanity.com/paper/2109.11154/) (2021)
- [The Utility and Complexity of in- and out-of-Distribution Machine Unlearning](https://mlsanity.com/paper/2412.09119/) (2024)
- [LoRA Training Provably Converges to a Low-Rank Global Minimum or It Fails Loudly (But it Probably Won't Fail)](https://mlsanity.com/paper/2502.09376/) (2025)
- [How Over-Parameterization Slows Down Gradient Descent in Matrix Sensing: The Curses of Symmetry and Initialization](https://mlsanity.com/paper/2310.01769/) (2023)
- [Improved Global Guarantees for the Nonconvex Burer--Monteiro Factorization via Rank Overparameterization](https://mlsanity.com/paper/2207.01789/) (2022)
- [GNMR: A provable one-line algorithm for low rank matrix recovery](https://mlsanity.com/paper/2106.12933/) (2021)
- [Noisy Low-rank Matrix Optimization: Geometry of Local Minima and Convergence Rate](https://mlsanity.com/paper/2203.03899/) (2022)
- [A Validation Approach to Over-parameterized Matrix and Image Recovery](https://mlsanity.com/paper/2209.10675/) (2022)
- [Guaranteed Nonconvex Factorization Approach for Tensor Train Recovery](https://mlsanity.com/paper/2401.02592/) (2024)
- [A Bitter Lesson for Data Filtering](https://mlsanity.com/paper/2605.19407/) (2026)
- [Sharp Restricted Isometry Property Bounds for Low-rank Matrix Recovery Problems with Corrupted Measurements](https://mlsanity.com/paper/2105.08232/) (2021)
- [Provably Accelerating Ill-Conditioned Low-rank Estimation via Scaled Gradient Descent, Even with Overparameterization](https://mlsanity.com/paper/2310.06159/) (2023)
- [Sharp Global Guarantees for Nonconvex Low-rank Recovery in the Noisy Overparameterized Regime](https://mlsanity.com/paper/2104.10790/) (2021)
- [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)
- [Inductive Matrix Completion: No Bad Local Minima and a Fast Algorithm](https://mlsanity.com/paper/2201.13052/) (2022)
- [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)
- [A Scalable Factorization Approach for High-Order Structured Tensor Recovery](https://mlsanity.com/paper/2506.16032/) (2025)
- [Sample-Efficient Geometry Reconstruction from Euclidean Distances using Non-Convex Optimization](https://mlsanity.com/paper/2410.16982/) (2024)
- [Beyond Procrustes: Balancing-Free Gradient Descent for Asymmetric Low-Rank Matrix Sensing](https://mlsanity.com/paper/2101.05113/) (2021)
- [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)
- [A Complete Loss Landscape Analysis of Regularized Deep Matrix Factorization](https://mlsanity.com/paper/2506.20344/) (2025)
- [Low-rank Tensor Learning with Nonconvex Overlapped Nuclear Norm Regularization](https://mlsanity.com/paper/2205.03059/) (2022)
- [Absence of spurious solutions far from ground truth: A low-rank analysis with high-order losses](https://mlsanity.com/paper/2403.06056/) (2024)
- [Nonnegative Low-rank Matrix Recovery Can Have Spurious Local Minima](https://mlsanity.com/paper/2505.03717/) (2025)

## Abstract (arXiv)

This paper considers the minimization of a general objective function f(X) over the set of rectangular n× m matrices that have rank at most r. To reduce the computational burden, we factorize the variable X into a product of two smaller matrices and optimize over these two matrices instead of X. Despite the resulting nonconvexity, recent studies in matrix completion and sensing have shown that the factored problem has no spurious local minima and obeys the so-called strict saddle property (the function has a directional negative curvature at all critical points but local minima). We analyze the global geometry for a general and yet well-conditioned objective function f(X) whose restricted strong convexity and restricted strong smoothness constants are comparable. In particular, we show that the reformulated objective function has no spurious local minima and obeys the strict saddle property. These geometric properties imply that a number of iterative optimization algorithms (such as gradient descent) can provably solve the factored problem with global convergence.