Average-case tightness of semidefinite relaxations of maximum likelihood estimation problems

Afonso S. Bandeira
Graduate Student, Princeton University
Given on: Oct. 10th, 2014


Many maximum likelihood estimation problems are known to be intractable in the worst case. A common approach is to consider convex relaxations of the maximum likelihood estimator (MLE), and semidefinite relaxations are among the most popular. Fortunately, there are many instances for which, under random models, the solution to the semidefinite programming relaxation can be shown to recover the ground truth parameters. Perhaps more remarkable is that these relaxations are often tight (meaning that their solution exactly recovers the MLE) even when the MLE does not coincide with the ground truth. We treat graph clustering and angular synchronization problems as illustrative examples of this phenomenon. This average case analysis of the MLE is achieved by analyzing the solutions of certain randomized Grothendieck problems.


Afonso is pursuing a Ph.D. in the Program in Applied and Computational Mathematics in Princeton University. He received the BSc and MSc in Mathematics from University of Coimbra (Portugal). His interests span across probability, information theory, convex optimization, algorithm design, and applications of these to, among other things, data analysis and signal processing.