SDP Achieves Exact Minimax Optimality in Phase Synchronization
Authors:
Preprint
Abstract
We study the phase synchronization problem with noisy 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 an SDP relaxation of the MLE achieves the error bound $(1+o(1))\frac{\sigma^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\sigma^2}\right)$ with a sharp constant in the exponent.
Keywords
All Related Versions
This publication has 22 references indexed in Scilit:
- Solving orthogonal group synchronization via convex and low-rank optimization: tightness and landscape analysisMathematical Programming, 2022
- Convergence rate of block-coordinate maximization Burer–Monteiro method for solving large SDPsMathematical Programming, 2021
- Achieving the Bayes Error Rate in Synchronization and Block Models by SDP, RobustlyIEEE Transactions on Information Theory, 2020
- Tightness of the maximum likelihood semidefinite relaxation for angular synchronizationMathematical Programming, 2016
- Achieving Exact Cluster Recovery Threshold via Semidefinite Programming: ExtensionsIEEE Transactions on Information Theory, 2016
- Achieving Exact Cluster Recovery Threshold via Semidefinite ProgrammingIEEE Transactions on Information Theory, 2016
- Phase transitions in semidefinite relaxationsProceedings of the National Academy of Sciences, 2016
- Angular synchronization by eigenvectors and semidefinite programmingApplied and Computational Harmonic Analysis, 2011
- A nonlinear programming algorithm for solving semidefinite programs via low-rank factorizationMathematical Programming, 2003
- Perturbation bounds in connection with singular value decompositionBIT Numerical Mathematics, 1972