# Orthogonal Group Synchronization with Incomplete Measurements: Error Bounds and Linear Convergence of the Generalized Power Method

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

## Key facts

- Cited by 4 papers in the map (data through 14 Oct 2026).
- Builds on 19 of its 38 references that are in the map.
- First posted on arXiv 13 Dec 2021.

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

- [Community Detection and Stochastic Block Models](https://mlsanity.com/paper/1703.10146/) (2017)
- [SE-Sync: A Certifiably Correct Algorithm for Synchronization over the Special Euclidean Group](https://mlsanity.com/paper/1612.07386/) (2016)
- [The non-convex Burer-Monteiro approach works on smooth semidefinite programs](https://mlsanity.com/paper/1606.04970/) (2016)
- [Shonan Rotation Averaging: Global Optimality by Surfing SO(p)n](https://mlsanity.com/paper/2008.02737/) (2020)
- [Near-optimal bounds for phase synchronization](https://mlsanity.com/paper/1703.06605/) (2017)
- [Nonconvex phase synchronization](https://mlsanity.com/paper/1601.06114/) (2016)
- [A Unified Approach to Error Bounds for Structured Convex Optimization Problems](https://mlsanity.com/paper/1512.03518/) (2015)
- [Global registration of multiple point clouds using semidefinite programming](https://mlsanity.com/paper/1306.5226/) (2013)
- [On the Estimation Performance and Convergence Rate of the Generalized Power Method for Phase Synchronization](https://mlsanity.com/paper/1603.00211/) (2016)
- [A Riemannian low-rank method for optimization over semidefinite matrices with block-diagonal constraints](https://mlsanity.com/paper/1506.00575/) (2015)
- [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)
- [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)
- [Complete Dictionary Learning via ℓp-norm Maximization](https://mlsanity.com/paper/2002.10043/) (2020)
- [Exact Minimax Estimation for Phase Synchronization](https://mlsanity.com/paper/2010.04345/) (2020)
- [New Analysis of Linear Convergence of Gradient-type Methods via Unifying Error Bound Conditions](https://mlsanity.com/paper/1606.00269/) (2016)
- [Linear Convergence of a Proximal Alternating Minimization Method with Extrapolation for ℓ1-Norm Principal Component Analysis](https://mlsanity.com/paper/2107.07107/) (2021)
- [Tightness of the semidefinite relaxation for orthogonal trace-sum maximization](https://mlsanity.com/paper/1911.08700/) (2019)

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

- [NS-RGS: Newton-Schulz based Riemannian gradient method for orthogonal group synchronization](https://mlsanity.com/paper/2604.07372/) (2026)
- [Decentralized Weakly Convex Optimization Over the Stiefel Manifold](https://mlsanity.com/paper/2303.17779/) (2023)
- [On the Estimation Performance of Generalized Power Method for Heteroscedastic Probabilistic PCA](https://mlsanity.com/paper/2312.03438/) (2023)
- [ℓ1-norm rank-one symmetric matrix factorization has no spurious second-order stationary points](https://mlsanity.com/paper/2410.05025/) (2024)

## Abstract (arXiv)

Group synchronization refers to estimating a collection of group elements from the noisy pairwise measurements. Such a nonconvex problem has received much attention from numerous scientific fields including computer vision, robotics, and cryo-electron microscopy. In this paper, we focus on the orthogonal group synchronization problem with general additive noise models under incomplete measurements, which is much more general than the commonly considered setting of complete measurements. Characterizations of the orthogonal group synchronization problem are given from perspectives of optimality conditions as well as fixed points of the projected gradient ascent method which is also known as the generalized power method (GPM). It is well worth noting that these results still hold even without generative models. In the meantime, we derive the local error bound property for the orthogonal group synchronization problem which is useful for the convergence rate analysis of different algorithms and can be of independent interest. Finally, we prove the linear convergence result of the GPM to a global maximizer under a general additive noise model based on the established local error bound property. Our theoretical convergence result holds under several deterministic conditions which can cover certain cases with adversarial noise, and as an example we specialize it to the setting of the Erd"os-R'enyi measurement graph and Gaussian noise.