SDP Achieves Exact Minimax Optimality in Phase Synchronization
Authors:
- 18 April 2022
- journal article
- research article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Information Theory
- Vol. 68 (8) , 5374-5390
Abstract
We study the phase synchronization problem with noisy measurements $Y=z^{*}z^{* { \mathrm {\scriptscriptstyle 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
Funding Information
- NSF CAREER Award (DMS-1847590)
- NSF (CCF-1934931)
- NSF (DMS-2112988)
This publication has 20 references indexed in Scilit:
- 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
- Sharp nonasymptotic bounds on the norm of random matrices with independent entriesThe Annals of Probability, 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
- Consistency of spectral clustering in stochastic block modelsThe Annals of Statistics, 2015
- 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
- The Rotation of Eigenvectors by a Perturbation. IIISIAM Journal on Numerical Analysis, 1970