Tightness of the maximum likelihood semidefinite relaxation for angular synchronization
Afonso S. Bandeira, Nicolas Boumal, Amit Singer Massachusetts Institute of Technology. http://math.mit.edu/~bandeira/.Princeton University. http://www.math.princeton.edu/~nboumal/.Princeton University. http://www.math.princeton.edu/~amits/.
Abstract
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）问题要求从含噪声的两两相位差测量值中恢复一组未知相位，其最大似然估计（MLE）等价于求解一个NP难的复数二次规划，实际中往往通过半正定规划（SDP）松弛来近似求解。以往关于SDP松弛"紧"（即松弛解恰好就是原问题最优解）的理论结果，几乎都要求噪声为零或MLE与真实信号完全一致，但在有噪声的角度同步问题中，MLE并不等于植入的真实信号，这给理论分析带来了根本性困难。本文在随机高斯噪声模型下严格证明：只要噪声水平不超过$n^{1/4}/18$的量级，SDP松弛以高概率给出唯一的秩一解，从而在多项式时间内精确计算出MLE，同时自动附带最优性证书。这一结果首次从理论上解释了此前数值实验中观察到的"高噪声下松弛仍然紧"的现象，也为其他类似问题（如Procrustes对齐、多参考对齐）的理论分析提供了新的思路。
原文 arXiv:1411.3272;中英对照 + 大白话阅读 https://aha.fim.ai/paper/1411.3272v3