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 certain

randomized Grothendieck problems. However, for many other problems,

such as the multireference alignment problem in signal processing,

this remains a fascinating open problem.