Convex Relaxations for Certain Inverse Problems on Graphs

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. This thesis focuses on a certain class of graph-based inverse problems, referred to as synchronization-type problems. These are problems where the goal is to estimate a set of parameters from pairwise information between them.

In this thesis, we investigate the performance of the SDP based approach for a range of problems of this type. While for many such problems, such as multi-reference alignment in signal processing, a precise explanation of their effectiveness remains a fascinating open problem, we rigorously establish a couple of remarkable phenomena.

For example, in some instances (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 by developing non-asymptotic bounds for the spectral norm of random matrices with independent entries.

On other instances (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 establish this behavior by analyzing the solutions of certain

randomized Grothendieck problems.