Tightness of the maximum likelihood semidefinite relaxation for angular synchronization
Tightness of the maximum likelihood semidefinite relaxation for angular synchronization
复制标题
DOI：
10.1007/s10107-016-1059-6
复制
发表时间：
2017-05-01
影响因子：
2.7
通讯作者：
Singer, Amit
中科院分区：
文献类型：
--
作者：
Bandeira, Afonso S.;Boumal, Nicolas;Singer, Amit
最大似然估计问题通常是难以解决的最优化问题。因此，使用凸松弛近似最大似然估计(MLE)是很常见的。在某些情况下，放松是严格的：它恢复了真正的MLE。大多数密封性证明仅适用于MLE准确恢复种植的溶液(分析师已知)的情况。然后，足以确定最优条件在种植信号处成立。本文研究了一个估计问题(角同步)，它的最大似然估计不是种植解的简单函数，但它的凸松弛是紧的。在这种情况下，为了建立紧密性，证明不那么直接，因为验证最优化条件的点是不明确的。角同步包括在给定成对相对相位的噪声测量的情况下估计n个相位的集合。角同步的最大似然估计是一个复数上(硬)非二部Grothendieck问题的解。我们考虑了一个数据的随机模型：种植信号(即，相位的地面真实集)被非对抗性随机噪声破坏。即使最大似然估计与注入信号不重合，我们也证明了经典的半定松弛是紧的，概率很大。即使在高水平的噪音下，这一点也是成立的。
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. In some cases, the relaxation is tight: it recovers the true MLE. Most tightness proofs only apply to situations where the MLE exactly recovers a planted solution (known to the analyst). It is then sufficient to establish that the optimality conditions hold at the planted signal. In this paper, we study an estimation problem (angular synchronization) for which the MLE is not a simple function of the planted solution, yet for which the convex relaxation is tight. To establish tightness in this context, the proof is less direct because the point at which to verify optimality conditions is not known explicitly. Angular synchronization consists in estimating a collection of n phases, given noisy measurements of the pairwise relative phases. The MLE for angular synchronization is the solution of a (hard) non-bipartite Grothendieck problem over the complex numbers. We consider a stochastic model for the data: a planted signal (that is, a ground truth set of phases) is corrupted with non-adversarial random noise. Even though the MLE does not coincide with the planted signal, we show that the classical semidefinite relaxation for it is tight, with high probability. This holds even for high levels of noise.