# Rank optimality for the Burer-Monteiro factorization

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

## Key facts

- Cited by 12 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 7 Dec 2018.

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

- [Preconditioned Gradient Descent for Overparameterized Nonconvex Burer--Monteiro Factorization with Global Optimality Certification](https://mlsanity.com/paper/2206.03345/) (2022)
- [Improved Global Guarantees for the Nonconvex Burer--Monteiro Factorization via Rank Overparameterization](https://mlsanity.com/paper/2207.01789/) (2022)
- [Factorization Approach for Low-complexity Matrix Completion Problems: Exponential Number of Spurious Solutions and Failure of Gradient Methods](https://mlsanity.com/paper/2110.10279/) (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)
- [Tight Certification of Adversarially Trained Neural Networks via Nonconvex Low-Rank Semidefinite Relaxations](https://mlsanity.com/paper/2211.17244/) (2022)
- [Fast, Scalable, Warm-Start Semidefinite Programming with Spectral Bundling and Sketching](https://mlsanity.com/paper/2312.11801/) (2023)
- [Generalized Orthogonal Procrustes Problem under Arbitrary Adversaries](https://mlsanity.com/paper/2106.15493/) (2021)
- [Implicit Bias in Matrix Factorization and its Explicit Realization in a New Architecture](https://mlsanity.com/paper/2501.16322/) (2025)
- [Theory of Minimal Weight Perturbations in Deep Networks and its Applications for Low-Rank Activated Backdoor Attacks](https://mlsanity.com/paper/2601.16880/) (2026)
- [Low-Rank Extragradient Methods for Scalable Semidefinite Optimization](https://mlsanity.com/paper/2402.09081/) (2024)
- [Suboptimality bounds for trace-bounded SDPs enable a faster and scalable low-rank SDP solver SDPLR+](https://mlsanity.com/paper/2406.10407/) (2024)
- [Benign landscape for Burer-Monteiro factorizations of MaxCut-type semidefinite programs](https://mlsanity.com/paper/2411.03103/) (2024)

## Abstract (arXiv)

When solving large scale semidefinite programs that admit a low-rank solution, an efficient heuristic is the Burer-Monteiro factorization: instead of optimizing over the full matrix, one optimizes over its low-rank factors. This reduces the number of variables to optimize, but destroys the convexity of the problem, thus possibly introducing spurious second-order critical points. The article [Boumal, Voroninski, and Bandeira, 2018] shows that when the size of the factors is of the order of the square root of the number of linear constraints, this does not happen: for almost any cost matrix, second-order critical points are global solutions. In this article, we show that this result is essentially tight: for smaller values of the size, second-order critical points are not generically optimal, even when the global solution is rank 1.