Exact Minimax Estimation for Phase Synchronization
Authors:
Preprint
Abstract
We study the phase synchronization problem with measurements $Y=z^*z^{*H}+\sigma 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 the minimax lower bound of estimating $z^*$ 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.
Keywords
All Related Versions
This publication has 11 references indexed in Scilit:
- On Recovery Guarantees for Angular SynchronizationJournal of Fourier Analysis and Applications, 2021
- Fundamental limits of symmetric low-rank matrix estimationProbability Theory and Related Fields, 2018
- Message‐Passing Algorithms for Synchronization Problems over Compact GroupsCommunications on Pure and Applied Mathematics, 2018
- Near-Optimal Bounds for Phase SynchronizationSIAM Journal on Optimization, 2018
- On the Estimation Performance and Convergence Rate of the Generalized Power Method for Phase SynchronizationSIAM Journal on Optimization, 2017
- Tightness of the maximum likelihood semidefinite relaxation for angular synchronizationMathematical Programming, 2016
- Sharp nonasymptotic bounds on the norm of random matrices with independent entriesThe Annals of Probability, 2016
- Phase transitions in semidefinite relaxationsProceedings of the National Academy of Sciences, 2016
- Consistency of spectral clustering in stochastic block modelsThe Annals of Statistics, 2015
- Angular synchronization by eigenvectors and semidefinite programmingApplied and Computational Harmonic Analysis, 2011