Section: New Results

Rank optimality for the Burer-Monteiro factorization

I. Waldspurger, A. Watersw

In [39], Numerically solving a large scale semidefinite program, in full generality, is a challenge: The complexity of generic algorithms blows up quickly with the size of the unknown matrix. Fortunately, in many situations, the solution of the program has low rank, and this can be exploited to achieve algorithmic speedups. The most classical way to do this is the Burer-Monteiro factorization, introduced in [77]. It consists in writing the unknown matrix as the product of low-rank factors, and optimizing the factors instead of the matrix itself. The first theoretical guarantees for this method appeared in [69], where it was shown that this strategy almost always succeeds when the size of the factors is of the order of the square root of the full matrix. In our article, we show that, up to a marginal improvement, this result is optimal: Contrarily to what numerical experiments might suggest, there exist situations where the method fails if the size of the factors is chosen smaller.