Rank Optimality for the Burer-Monteiro Factorization
Waters, Alden
Abstract
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 [N. Boumal, V. Voroninski, and A. S. Bandeira, Deterministic Guarantees for Burer-Monteiro Factorizations of Smooth Semidefinite Programs, https://arxiv.org/abs/1804.02008, 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.