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.

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

Speaker:

Afonso S. Bandeira, PACM Graduate Student - Princeton University

Date:

Oct 1 2014 - 3:00pm

Event type:

IDeAS

Room:

110 Fine Hall

Abstract: