# Optimal Orthogonal Group Synchronization and Rotation Group Synchronization

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

## Key facts

- Cited by 4 papers in the map (data through 14 Oct 2026).
- Builds on 18 of its 36 references that are in the map.
- First posted on arXiv 28 Sep 2021.

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

- [Consistency of spectral clustering in stochastic block models](https://mlsanity.com/paper/1312.2050/) (2013)
- [Near-optimal bounds for phase synchronization](https://mlsanity.com/paper/1703.06605/) (2017)
- [Nonconvex phase synchronization](https://mlsanity.com/paper/1601.06114/) (2016)
- [Tightness of the maximum likelihood semidefinite relaxation for angular synchronization](https://mlsanity.com/paper/1411.3272/) (2014)
- [Iterative Algorithm for Discrete Structure Recovery](https://mlsanity.com/paper/1911.01018/) (2019)
- [Message-passing algorithms for synchronization problems over compact groups](https://mlsanity.com/paper/1610.04583/) (2016)
- [Near-Optimal Performance Bounds for Orthogonal and Permutation Group Synchronization via Spectral Methods](https://mlsanity.com/paper/2008.05341/) (2020)
- [On the Estimation Performance and Convergence Rate of the Generalized Power Method for Phase Synchronization](https://mlsanity.com/paper/1603.00211/) (2016)
- [The Projected Power Method: An Efficient Algorithm for Joint Alignment from Pairwise Differences](https://mlsanity.com/paper/1609.05820/) (2016)
- [A Unified Approach to Synchronization Problems over Subgroups of the Orthogonal Group](https://mlsanity.com/paper/2009.07514/) (2020)
- [Optimal Estimation and Completion of Matrices with Biclustering Structures](https://mlsanity.com/paper/1512.00150/) (2015)
- [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)
- [Improved Performance Guarantees for Orthogonal Group Synchronization via Generalized Power Method](https://mlsanity.com/paper/2012.00470/) (2020)
- [Exact Minimax Estimation for Phase Synchronization](https://mlsanity.com/paper/2010.04345/) (2020)
- [Joint Community Detection and Rotational Synchronization via Semidefinite Programming](https://mlsanity.com/paper/2105.06031/) (2021)
- [On recovery guarantees for angular synchronization](https://mlsanity.com/paper/2005.02032/) (2020)
- [SDP Achieves Exact Minimax Optimality in Phase Synchronization](https://mlsanity.com/paper/2101.02347/) (2021)

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

- [Seeded graph matching for the correlated Gaussian Wigner model via the projected power method](https://mlsanity.com/paper/2204.04099/) (2022)
- [A Spectral Method for Joint Community Detection and Orthogonal Group Synchronization](https://mlsanity.com/paper/2112.13199/) (2021)
- [NS-RGS: Newton-Schulz based Riemannian gradient method for orthogonal group synchronization](https://mlsanity.com/paper/2604.07372/) (2026)
- [Dynamic angular synchronization under smoothness constraints](https://mlsanity.com/paper/2406.04071/) (2024)

## Abstract (arXiv)

We study the statistical estimation problem of orthogonal group synchronization and rotation group synchronization. The model is Yij = Zi^* Zj*T + σ Wij∈ℝd× d where Wij is a Gaussian random matrix and Zi^* is either an orthogonal matrix or a rotation matrix, and each Yij is observed independently with probability p. We analyze an iterative polar decomposition algorithm for the estimation of Z^* and show it has an error of (1+o(1))fracσ2 d(d-1)2np when initialized by spectral methods. A matching minimax lower bound is further established which leads to the optimality of the proposed algorithm as it achieves the exact minimax risk.