# SDP Achieves Exact Minimax Optimality in Phase Synchronization

arXiv: https://arxiv.org/abs/2101.02347 · HTML: https://mlsanity.com/paper/2101.02347/

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- Builds on 22 of its 32 references that are in the map.
- First posted on arXiv 7 Jan 2021.

## Builds on (most cited first, 22 of 22)

- [Consistency of spectral clustering in stochastic block models](https://mlsanity.com/paper/1312.2050/) (2013)
- [Statistical and Computational Guarantees of Lloyd's Algorithm and its Variants](https://mlsanity.com/paper/1612.02099/) (2016)
- [Achieving Exact Cluster Recovery Threshold via Semidefinite Programming](https://mlsanity.com/paper/1412.6156/) (2014)
- [Near-optimal bounds for phase synchronization](https://mlsanity.com/paper/1703.06605/) (2017)
- [Nonconvex phase synchronization](https://mlsanity.com/paper/1601.06114/) (2016)
- [Minimax Rates of Community Detection in Stochastic Block Models](https://mlsanity.com/paper/1507.05313/) (2015)
- [Tightness of the maximum likelihood semidefinite relaxation for angular synchronization](https://mlsanity.com/paper/1411.3272/) (2014)
- [On semidefinite relaxations for the block model](https://mlsanity.com/paper/1406.5647/) (2014)
- [Iterative Algorithm for Discrete Structure Recovery](https://mlsanity.com/paper/1911.01018/) (2019)
- [Convexified Modularity Maximization for Degree-corrected Stochastic Block Models](https://mlsanity.com/paper/1512.08425/) (2015)
- [Random Laplacian matrices and convex relaxations](https://mlsanity.com/paper/1504.03987/) (2015)
- [Achieving Exact Cluster Recovery Threshold via Semidefinite Programming: Extensions](https://mlsanity.com/paper/1502.07738/) (2015)
- [Optimal Estimation and Completion of Matrices with Biclustering Structures](https://mlsanity.com/paper/1512.00150/) (2015)
- [Convex Relaxation Methods for Community Detection](https://mlsanity.com/paper/1810.00315/) (2018)
- [Achieving the Bayes Error Rate in Synchronization and Block Models by SDP, Robustly](https://mlsanity.com/paper/1904.09635/) (2019)
- [Solving Orthogonal Group Synchronization via Convex and Low-Rank Optimization: Tightness and Landscape Analysis](https://mlsanity.com/paper/2006.00902/) (2020)
- [The Mixing method: low-rank coordinate descent for semidefinite programming with diagonal constraints](https://mlsanity.com/paper/1706.00476/) (2017)
- [A semidefinite program for unbalanced multisection in the stochastic block model](https://mlsanity.com/paper/1507.05605/) (2015)
- [Convergence Rate of Block-Coordinate Maximization Burer-Monteiro Method for Solving Large SDPs](https://mlsanity.com/paper/1807.04428/) (2018)
- [Multi-Frequency Phase Synchronization](https://mlsanity.com/paper/1901.08235/) (2019)
- [Exact Minimax Estimation for Phase Synchronization](https://mlsanity.com/paper/2010.04345/) (2020)
- [Open problem: Tightness of maximum likelihood semidefinite relaxations](https://mlsanity.com/paper/1404.2655/) (2014)

## Built on by (most cited first, 3 of 3)

- [Approximate message passing from random initialization with applications to mathbbZ2 synchronization](https://mlsanity.com/paper/2302.03682/) (2023)
- [Optimal Orthogonal Group Synchronization and Rotation Group Synchronization](https://mlsanity.com/paper/2109.13491/) (2021)
- [Generalized Orthogonal Procrustes Problem under Arbitrary Adversaries](https://mlsanity.com/paper/2106.15493/) (2021)

## Abstract (arXiv)

We study the phase synchronization problem with noisy measurements Y=z^*z*H+σ W∈mathbbCn× 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 Yjk is observed with probability p. We prove that an SDP relaxation of the MLE achieves the error bound (1+o(1))fracσ22np under a normalized squared ℓ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 mathbbZ2 synchronization, and we achieve the minimax optimal error expleft(-(1-o(1))fracnp2σ2right) with a sharp constant in the exponent.