Skip navigation
Please use this identifier to cite or link to this item:
Title: Convex Relaxations for Certain Inverse Problems on Graphs
Authors: Bandeira, Afonso S.
Advisors: Singer, Amit
Contributors: Applied and Computational Mathematics Department
Subjects: Applied mathematics
Computer science
Issue Date: 2015
Publisher: Princeton, NJ : Princeton University
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.
Alternate format: The Mudd Manuscript Library retains one bound copy of each dissertation. Search for these copies in the library's main catalog
Type of Material: Academic dissertations (Ph.D.)
Language: en
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.