Exact Minimax Estimation for Phase Synchronization

Abstract

We study the phase synchronization problem with measurements $Y=z^{\ast }{z}^{\ast H}+\sigma W\in {\mathbb{C}}^{n\times n}$, where $z^{\ast }$ 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 the minimax lower bound of estimating $z^{\ast }$ under the squared ${\ell }_2$ loss is $(1-o(1))\frac{{\sigma }^2}{2p}$. We also show that both generalized power method and maximum likelihood estimator achieve the error bound $(1+o(1))\frac{{\sigma }^2}{2p}$. Thus, $\frac{{\sigma }^2}{2p}$ is the exact asymptotic minimax error of the problem. Our upper bound analysis involves a precise characterization of the statistical property of the power iteration. The lower bound is derived through an application of van Trees' inequality.

References in corpus (5)

• Sharp nonasymptotic bounds on the norm of random matrices with independent entries
• Nonconvex phase synchronization
• Phase Transitions in Semidefinite Relaxations
• Near-optimal bounds for phase synchronization
• Optimal Estimation and Completion of Matrices with Biclustering Structures

Cited by in corpus (2)

• Lecture notes on non-convex algorithms for low-rank matrix recovery
• Depth Descent Synchronization in $\mathrm{SO}(D)$