Skip navigation
Please use this identifier to cite or link to this item:
Full metadata record
DC FieldValueLanguage
dc.contributor.advisorSinger, Amiten_US
dc.contributor.authorBandeira, Afonso S.en_US
dc.contributor.otherApplied and Computational Mathematics Departmenten_US
dc.description.abstractMany 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.en_US
dc.publisherPrinceton, NJ : Princeton Universityen_US
dc.relation.isformatofThe Mudd Manuscript Library retains one bound copy of each dissertation. Search for these copies in the <a href=> library's main catalog </a>en_US
dc.subject.classificationApplied mathematicsen_US
dc.subject.classificationComputer scienceen_US
dc.titleConvex Relaxations for Certain Inverse Problems on Graphsen_US
dc.typeAcademic dissertations (Ph.D.)en_US
Appears in Collections:Applied and Computational Mathematics

Files in This Item:
File Description SizeFormat 
Bandeira_princeton_0181D_11387.pdf2.8 MBAdobe PDFView/Download

Items in Dataspace are protected by copyright, with all rights reserved, unless otherwise indicated.