SDP Achieves Exact Minimax Optimality in Phase Synchronization
Chao Gao, Anderson Y. Zhang · IEEE Transactions on Information Theory · 2022
We study the phase synchronization problem with noisy measurements$Y=z^{*}z^{* { \mathrm {\scriptscriptstyle H} }}+\sigma W\in \mathbb {C}^{n\times n}$, where$z^{*}$is an$n$-dimensional complex unit-modulus vector and$W$is a complex-valued Gaussian random matrix. It is assumed that each entry$Y_{jk}$is observed with probability$p$. We prove that an SDP relaxation of the MLE achieves the error bound$(1+o(1))\frac {\sigma ^{2}}{2np}$under a normalized squared$\ell _{2}$loss. This result matches the minimax lower bound of the problem, and even the leading constant is sharp. The analysis of the SDP is based on an equivalent non-convex programming whose solution can be characterized as a fixed point of the generalized power iteration lifted to a higher dimensional space. This viewpoint unifies the proofs of the statistical optimality of three different methods: MLE, SDP, and generalized power method. The technique is also applied to the analysis of the SDP for$\mathbb {Z}_{2}$synchronization, and we achieve the minimax optimal error$\exp \left ({-(1-o(1))\frac {np}{2\sigma ^{2}}}\right)$with a sharp constant in the exponent.