EECS Department Colloquium Series
Tightness of convex relaxations for certain inverse problems on graphs 
 |
Wednesday, February 18, 2015 Afonso Bandeira
|
ABSTRACT:
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 relaxations based on semidefinite programming (SDP) are among the most popular. We will focus our attention on a certain class of graph-based inverse problems and show a couple of remarkable phenomena.
In some instances of these problems (such as community detection under the stochastic block model) the solution to the SDP matches the ground truth parameters (i.e. achieves exact recovery) for information theoretically optimal regimes. This is established using new nonasymptotic bounds for the spectral norm of random matrices with independent entries.
On other instances of these problems (such as angular synchronization), the MLE itself tends to not coincide with the ground truth (although maintaining favorable statistical properties). Remarkably, these relaxations are often still tight (meaning that the solution of the SDP matches the MLE). For angular synchronization we can understand this behavior by analyzing the solutions of certainrandomized Grothendieck problems. However, for many other problems, such as the multireference alignment problem in signal processing, this remains a fascinating open problem.
BIOGRAPHY:
Afonso S. Bandeira received the BSc and MSc degrees in mathematics from the University of Coimbra, Portugal, and is working toward the Ph.D. degree at the Program in Applied and Computational Mathematics, Princeton University. His interests span across probability, information theory, convex optimization, algorithm design, and applications of these to, among other things, data analysis, and signal processing.
| Return to EECS Joint Colloquium |