Semidefinite programs with few equality constraints typically have low rank solutions. This has motivated the development of low-rank heuristics to solve them, by reduction to lower-dimensional but nonconvex problems. In certain cases of importance (such as synchronization and community detection in the stochastic block model), the heuristics work fantastically despite nonconvexity. In this talk, I will give a geometric perspective on why this is so under smoothness assumptions. Then I will quantify the phenomenon more precisely for particular examples. This is ongoing work with Afonso S. Bandeira and Vladislav Voroninski.
Semidefinite programs with a dash of smoothness: why the low-rank approach works
Nicolas Boumal, Princeton University
Mar 2 2016 - 2:30pm