Tightness of the maximum likelihood semidefinite relaxation for angular synchronization
Preprint
Abstract
Many maximum likelihood estimation problems are, in general, intractable optimization problems. As a result, it is common to approximate the maximum likelihood estimator (MLE) using convex relaxations. Semidefinite relaxations are among the most popular. Sometimes, the relaxations turn out to be tight. In this paper, we study such a phenomenon. The angular synchronization problem consists in estimating a collection of $n$ phases, given noisy measurements of some of the pairwise relative phases. The MLE for the angular synchronization problem is the solution of a (hard) non-bipartite Grothendieck problem over the complex numbers. It is known that its semidefinite relaxation enjoys worst-case approximation guarantees. In this paper, we consider a stochastic model on the input of that semidefinite relaxation. We assume there is a planted signal (corresponding to a ground truth set of phases) and the measurements are corrupted with random noise. Even though the MLE does not coincide with the planted signal, we show that the relaxation is, with high probability, tight. This holds even for high levels of noise. This analysis explains, for the interesting case of angular synchronization, a phenomenon which has been observed without explanation in many other settings. Namely, the fact that even when exact recovery of the ground truth is impossible, semidefinite relaxations for the MLE tend to be tight (in favorable noise regimes).
Keywords
All Related Versions
This publication has 34 references indexed in Scilit:
- Approximating the little Grothendieck problem over the orthogonal and unitary groupsMathematical Programming, 2016
- Stable Optimizationless Recovery from Phaseless Linear MeasurementsJournal of Fourier Analysis and Applications, 2013
- PhaseLift: Exact and Stable Signal Recovery from Magnitude Measurements via Convex ProgrammingCommunications on Pure and Applied Mathematics, 2012
- Exact Matrix Completion via Convex OptimizationFoundations of Computational Mathematics, 2009
- On approximating complex quadratic optimization problems via semidefinite programming relaxationsMathematical Programming, 2006
- Sums of random symmetric matrices and quadratic optimization under orthogonality constraintsMathematical Programming, 2006
- Stable signal recovery from incomplete and inaccurate measurementsCommunications on Pure and Applied Mathematics, 2006
- Reconstruction of Optical Surfaces from Ray DataOptical Review, 2001
- Complementarity and nondegeneracy in semidefinite programmingMathematical Programming, 1997
- Problems of distance geometry and convex properties of quadratic mapsDiscrete & Computational Geometry, 1995