Abstract
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.
Funding Information
  • NSF CAREER Award (DMS-1847590)
  • NSF (CCF-1934931)
  • NSF (DMS-2112988)

This publication has 20 references indexed in Scilit: