# Near-optimal bounds for phase synchronization

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

## Key facts

- Cited by 32 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 20 Mar 2017.

## Built on by (most cited first, 30 of 32)

- [Advances in Global Solvers for 3D Vision](https://mlsanity.com/paper/2602.14662/) (2026)
- [Randomly Initialized Alternating Least Squares: Fast Convergence for Matrix Sensing](https://mlsanity.com/paper/2204.11516/) (2022)
- [Approximate message passing from random initialization with applications to mathbbZ2 synchronization](https://mlsanity.com/paper/2302.03682/) (2023)
- [On the Local Linear Rate of Consensus on the Stiefel Manifold](https://mlsanity.com/paper/2101.09346/) (2021)
- [Estimating Higher-Order Mixed Memberships via the ℓ2,∞ Tensor Perturbation Bound](https://mlsanity.com/paper/2212.08642/) (2022)
- [On the Tightness of Semidefinite Relaxations for Rotation Estimation](https://mlsanity.com/paper/2101.02099/) (2021)
- [Deflated HeteroPCA: Overcoming the curse of ill-conditioning in heteroskedastic PCA](https://mlsanity.com/paper/2303.06198/) (2023)
- [Optimal Orthogonal Group Synchronization and Rotation Group Synchronization](https://mlsanity.com/paper/2109.13491/) (2021)
- [Orthogonal Group Synchronization with Incomplete Measurements: Error Bounds and Linear Convergence of the Generalized Power Method](https://mlsanity.com/paper/2112.06556/) (2021)
- [Robust Matrix Completion with Heavy-tailed Noise](https://mlsanity.com/paper/2206.04276/) (2022)
- [SDP Achieves Exact Minimax Optimality in Phase Synchronization](https://mlsanity.com/paper/2101.02347/) (2021)
- [A Spectral Method for Joint Community Detection and Orthogonal Group Synchronization](https://mlsanity.com/paper/2112.13199/) (2021)
- [Low-Rank Extragradient Method for Nonsmooth and Low-Rank Matrix Optimization Problems](https://mlsanity.com/paper/2202.04026/) (2022)
- [ReSync: Riemannian Subgradient-based Robust Rotation Synchronization](https://mlsanity.com/paper/2305.15136/) (2023)
- [Towards Understanding The Semidefinite Relaxations of Truncated Least-Squares in Robust Rotation Search](https://mlsanity.com/paper/2207.08350/) (2022)
- [Community Detection in the Hypergraph SBM: Exact Recovery Given the Similarity Matrix](https://mlsanity.com/paper/2208.12227/) (2022)
- [Improved theoretical guarantee for rank aggregation via spectral method](https://mlsanity.com/paper/2309.03808/) (2023)
- [NS-RGS: Newton-Schulz based Riemannian gradient method for orthogonal group synchronization](https://mlsanity.com/paper/2604.07372/) (2026)
- [Minimax Estimation of Linear Functions of Eigenvectors in the Face of Small Eigen-Gaps](https://mlsanity.com/paper/2104.03298/) (2021)
- [Generalized Orthogonal Procrustes Problem under Arbitrary Adversaries](https://mlsanity.com/paper/2106.15493/) (2021)
- [Unrolled algorithms for group synchronization](https://mlsanity.com/paper/2207.09418/) (2022)
- [Sparsification of the regularized magnetic Laplacian with multi-type spanning forests](https://mlsanity.com/paper/2208.14797/) (2022)
- [Synthetic Principal Component Design: Fast Covariate Balancing with Synthetic Controls](https://mlsanity.com/paper/2211.15241/) (2022)
- [Sharp analysis of EM for learning mixtures of pairwise differences](https://mlsanity.com/paper/2302.10066/) (2023)
- [Leave-One-Out Analysis for Nonconvex Robust Matrix Completion with General Thresholding Functions](https://mlsanity.com/paper/2407.19446/) (2024)
- [Momentum-inspired Low-Rank Coordinate Descent for Diagonally Constrained SDPs](https://mlsanity.com/paper/2106.08775/) (2021)
- [Low-Rank Mirror-Prox for Nonsmooth and Low-Rank Matrix Optimization Problems](https://mlsanity.com/paper/2206.11523/) (2022)
- [Multi-Frequency Joint Community Detection and Phase Synchronization](https://mlsanity.com/paper/2206.12276/) (2022)
- [Entrywise error bounds for low-rank approximations of kernel matrices](https://mlsanity.com/paper/2405.14494/) (2024)
- [Dynamic angular synchronization under smoothness constraints](https://mlsanity.com/paper/2406.04071/) (2024)

## Abstract (arXiv)

The problem of phase synchronization is to estimate the phases (angles) of a complex unit-modulus vector z from their noisy pairwise relative measurements C = zz^* + σ W, where W is a complex-valued Gaussian random matrix. The maximum likelihood estimator (MLE) is a solution to a unit-modulus constrained quadratic programming problem, which is nonconvex. Existing works have proposed polynomial-time algorithms such as a semidefinite relaxation (SDP) approach or the generalized power method (GPM) to solve it. Numerical experiments suggest both of these methods succeed with high probability for σ up to tildeO(n1/2), yet, existing analyses only confirm this observation for σ up to O(n1/4). In this paper, we bridge the gap, by proving SDP is tight for σ = O(√n /log n), and GPM converges to the global optimum under the same regime. Moreover, we establish a linear convergence rate for GPM, and derive a tighter ℓ_∞ bound for the MLE. A novel technique we develop in this paper is to track (theoretically) n closely related sequences of iterates, in addition to the sequence of iterates GPM actually produces. As a by-product, we obtain an ℓ_∞ perturbation bound for leading eigenvectors. Our result also confirms intuitions that use techniques from statistical mechanics.