SDP Achieves Exact Minimax Optimality in Phase Synchronization
This work provides a theoretical guarantee for the exact minimax optimality of SDP for phase synchronization, which is a fundamental problem in signal processing and machine learning. This is significant for researchers and practitioners working on robust and optimal recovery methods.
This paper investigates the phase synchronization problem under noisy and incomplete measurements, where the goal is to recover a complex unit-modulus vector. The authors demonstrate that a semidefinite programming (SDP) relaxation of the maximum likelihood estimator achieves the minimax optimal error bound of (1+o(1))σ^2 / (2np) for phase synchronization and exp(-(1-o(1))np / (2σ^2)) for Z2 synchronization, with sharp leading constants.
We study the phase synchronization problem with noisy measurements $Y=z^*z^{*H}+σ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{σ^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σ^2}\right)$ with a sharp constant in the exponent.