SDP Achieves Exact Minimax Optimality in Phase Synchronization
share
We study the phase synchronization problem with noisy measurements Y=z^*z^*H+σ W∈ℂ^n× 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))σ^2/2np 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 ℤ_2 synchronization, and we achieve the minimax optimal error (-(1-o(1))np/2σ^2) with a sharp constant in the exponent.
READ FULL TEXT