On the low-rank approach for semidefinite programs arising in synchronization and community detection

Understand

To address difficult optimization problems, convex relaxations based on semidefinite programming are now common place in many fields.

• Although solvable in polynomial time, large semidefinite programs tend to be computationally challenging.
• Over a decade ago, exploiting the fact that in many applications of interest the desired solutions are low rank, Burer and Monteiro proposed a heuristic to solve such semidefinite programs by restricting the search space to low-rank matrices.
• The accompanying theory does not explain the extent of the empirical success.