Semidefinite programs with a dash of smoothness: why the low-rank approach works

Speaker: 
Nicolas Boumal, Princeton University
Date: 
Mar 2 2016 - 2:30pm
Event type: 
IDeAS
Room: 
Fine 214
Abstract: 

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.