  Semidefinite programs (SDPs) can be solved in polynomial time by interior
point methods, but scalability can be an issue. To address this shortcoming,
over a decade ago, Burer and Monteiro proposed to solve SDPs with few equality
constraints via rank-restricted, non-convex surrogates. Remarkably, for some
applications, local optimization methods seem to converge to global optima of
these non-convex surrogates reliably. Although some theory supports this
empirical success, a complete explanation of it remains an open question. In
this paper, we consider a class of SDPs which includes applications such as
max-cut, community detection in the stochastic block model, robust PCA, phase
retrieval and synchronization of rotations. We show that the low-rank
Burer--Monteiro formulation of SDPs in that class almost never has any spurious
local optima.
