Title: On solving certain Semidefinite programs with low-rank solutions
Semidefinite programming has played an important role in mathematical signal processing, information theory, combinatorial optimization, etc. Although large Semidefinite programs are particularly challenging to solve, the solution one seeks is often low-rank. A now somehwat common approach is to constraint the search to low-rank solutions in the hope of reducing the computational cost. While such an approach can in general create new suboptimal local optima, it appears to work remarkably well in practice. We give the first (proof of concept) guarantee by showing that for a certain relevant semidefinite program this procedure indeed does not produce new local optima, and the global optima can be found.
Afonso is an Applied Mathematics Instructor at the MIT Math Department, with a half-time postdoctoral position sponsored by Philippe Rigollet. Starting in the Summer of 2016, he is going to join the Courant Institute of Mathematical Sciences as an Assistant Professor of Mathematics with a joint appointment in the Center for Data Science at NYU.