SDP Achieves Exact Minimax Optimality in Phase Synchronization

We study the phase synchronization problem with noisy measurements Y=z^*z*H+σ W∈mathbbCn× 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 Yjk is observed with probability p. We prove that an SDP relaxation of the MLE achieves the error bound (1+o(1))fracσ22np under a normalized squared ℓ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 mathbbZ2 synchronization, and we achieve the minimax optimal error expleft(-(1-o(1))fracnp2σ2right) with a sharp constant in the exponent.