# Nonconvex phase synchronization

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

## Key facts

- Cited by 30 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 22 Jan 2016.

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

- [Generative Principal Component Analysis](https://mlsanity.com/paper/2203.09693/) (2022)
- [An iterative clustering algorithm for the Contextual Stochastic Block Model with optimality guarantees](https://mlsanity.com/paper/2112.10467/) (2021)
- [Convergence and Recovery Guarantees of the K-Subspaces Method for Subspace Clustering](https://mlsanity.com/paper/2206.05553/) (2022)
- [On the Local Linear Rate of Consensus on the Stiefel Manifold](https://mlsanity.com/paper/2101.09346/) (2021)
- [Noisy Low-rank Matrix Optimization: Geometry of Local Minima and Convergence Rate](https://mlsanity.com/paper/2203.03899/) (2022)
- [Sharp Restricted Isometry Property Bounds for Low-rank Matrix Recovery Problems with Corrupted Measurements](https://mlsanity.com/paper/2105.08232/) (2021)
- [Semidefinite Programming versus Burer-Monteiro Factorization for Matrix Sensing](https://mlsanity.com/paper/2208.07469/) (2022)
- [Over-parametrization via Lifting for Low-rank Matrix Sensing: Conversion of Spurious Solutions to Strict Saddle Points](https://mlsanity.com/paper/2302.07828/) (2023)
- [Joint Community Detection and Rotational Synchronization via Semidefinite Programming](https://mlsanity.com/paper/2105.06031/) (2021)
- [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)
- [Seeded graph matching for the correlated Gaussian Wigner model via the projected power method](https://mlsanity.com/paper/2204.04099/) (2022)
- [SDP Achieves Exact Minimax Optimality in Phase Synchronization](https://mlsanity.com/paper/2101.02347/) (2021)
- [ReSync: Riemannian Subgradient-based Robust Rotation Synchronization](https://mlsanity.com/paper/2305.15136/) (2023)
- [Non-Convex Joint Community Detection and Group Synchronization via Generalized Power Method](https://mlsanity.com/paper/2112.14204/) (2021)
- [Robust Angular Synchronization via Directed Graph Neural Networks](https://mlsanity.com/paper/2310.05842/) (2023)
- [NS-RGS: Newton-Schulz based Riemannian gradient method for orthogonal group synchronization](https://mlsanity.com/paper/2604.07372/) (2026)
- [An accelerated expectation-maximization algorithm for multi-reference alignment](https://mlsanity.com/paper/2105.07372/) (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)
- [Synthetic Principal Component Design: Fast Covariate Balancing with Synthetic Controls](https://mlsanity.com/paper/2211.15241/) (2022)
- [Algorithmic Regularization in Tensor Optimization: Towards a Lifted Approach in Matrix Sensing](https://mlsanity.com/paper/2310.15549/) (2023)
- [Absence of spurious solutions far from ground truth: A low-rank analysis with high-order losses](https://mlsanity.com/paper/2403.06056/) (2024)
- [VICAN: Very Efficient Calibration Algorithm for Large Camera Networks](https://mlsanity.com/paper/2405.10952/) (2024)
- [Rotation Averaging: A Primal-Dual Method and Closed-Forms in Cycle Graphs](https://mlsanity.com/paper/2406.18564/) (2024)
- [Dual Quaternion SE(3) Synchronization with Recovery Guarantees](https://mlsanity.com/paper/2602.00324/) (2026)
- [Momentum-inspired Low-Rank Coordinate Descent for Diagonally Constrained SDPs](https://mlsanity.com/paper/2106.08775/) (2021)
- [Multi-Frequency Joint Community Detection and Phase Synchronization](https://mlsanity.com/paper/2206.12276/) (2022)
- [Dynamic angular synchronization under smoothness constraints](https://mlsanity.com/paper/2406.04071/) (2024)
- [Recovery Theory for Projected Power Iterations in Permutation Synchronization](https://mlsanity.com/paper/2609.09502/) (2026)

## Abstract (arXiv)

We estimate n phases (angles) from noisy pairwise relative phase measurements. The task is modeled as a nonconvex least-squares optimization problem. It was recently shown that this problem can be solved in polynomial time via convex relaxation, under some conditions on the noise. In this paper, under similar but more restrictive conditions, we show that a modified version of the power method converges to the global optimum. This is simpler and (empirically) faster than convex approaches. Empirically, they both succeed in the same regime. Further analysis shows that, in the same noise regime as previously studied, second-order necessary optimality conditions for this quadratically constrained quadratic program are also sufficient, despite nonconvexity.