# The Non-convex Geometry of Low-rank Matrix Optimization

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

## Key facts

- Cited by 6 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 9 Nov 2016.

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

- [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)
- [LEARNER: A Transfer Learning Method for Low-Rank Matrix Estimation](https://mlsanity.com/paper/2412.20605/) (2024)
- [Spectral Neural Networks: Approximation Theory and Optimization Landscape](https://mlsanity.com/paper/2310.00729/) (2023)
- [Discrete Aware Matrix Completion via Convexized ℓ0-Norm Approximation](https://mlsanity.com/paper/2405.02101/) (2024)
- [Robust Autoencoders for Collective Corruption Removal](https://mlsanity.com/paper/2303.02828/) (2023)

## Abstract (arXiv)

This work considers two popular minimization problems: (i) the minimization of a general convex function f(X) with the domain being positive semi-definite matrices; (ii) the minimization of a general convex function f(X) regularized by the matrix nuclear norm |X|_* with the domain being general matrices. Despite their optimal statistical performance in the literature, these two optimization problems have a high computational complexity even when solved using tailored fast convex solvers. To develop faster and more scalable algorithms, we follow the proposal of Burer and Monteiro to factor the low-rank variable X = UU^top  (for semi-definite matrices) or X=UV^top  (for general matrices) and also replace the nuclear norm |X|_* with (|U|F2+|V|F2)/2. In spite of the non-convexity of the resulting factored formulations, we prove that each critical point either corresponds to the global optimum of the original convex problems or is a strict saddle where the Hessian matrix has a strictly negative eigenvalue. Such a nice geometric structure of the factored formulations allows many local search algorithms to find a global optimizer even with random initializations.