Near-Optimal Bounds for Phase Synchronization

The problem of estimating the phases (angles) of a complex unit-modulus vector zfrom their noisy pairwise relative measurements C = zz^* + \sigma W where Wis a complex-valued Gaussian random matrix, is known as phase synchronization. The maximum likelihood estimator (MLE) is a solution to a unit--modulus-constrained quadratic programming problem, which is nonconvex. Existing works have proposed polynomial-time algorithms such as a...