# NS-RGS: Newton-Schulz based Riemannian gradient method for orthogonal group synchronization

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

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- Builds on 27 of its 46 references that are in the map.
- First posted on arXiv 7 Apr 2026.

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

- [A Survey of Structure from Motion](https://mlsanity.com/paper/1701.08493/) (2017)
- [Understanding Gradient Orthogonalization for Deep Learning via Non-Euclidean Trust-Region Optimization](https://mlsanity.com/paper/2503.12645/) (2025)
- [Muon Optimizes Under Spectral Norm Constraints](https://mlsanity.com/paper/2506.15054/) (2025)
- [A Note on the Convergence of Muon](https://mlsanity.com/paper/2502.02900/) (2025)
- [SE-Sync: A Certifiably Correct Algorithm for Synchronization over the Special Euclidean Group](https://mlsanity.com/paper/1612.07386/) (2016)
- [Modular Duality in Deep Learning](https://mlsanity.com/paper/2410.21265/) (2024)
- [Gradient Descent with Random Initialization: Fast Global Convergence for Nonconvex Phase Retrieval](https://mlsanity.com/paper/1803.07726/) (2018)
- [Implicit Regularization in Nonconvex Statistical Estimation: Gradient Descent Converges Linearly for Phase Retrieval, Matrix Completion, and Blind Deconvolution](https://mlsanity.com/paper/1711.10467/) (2017)
- [Noisy Matrix Completion: Understanding Statistical Guarantees for Convex Relaxation via Nonconvex Optimization](https://mlsanity.com/paper/1902.07698/) (2019)
- [Near-optimal bounds for phase synchronization](https://mlsanity.com/paper/1703.06605/) (2017)
- [When do spectral gradient updates help in deep learning?](https://mlsanity.com/paper/2512.04299/) (2025)
- [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)
- [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)
- [A Unified Approach to Synchronization Problems over Subgroups of the Orthogonal Group](https://mlsanity.com/paper/2009.07514/) (2020)
- [Random Laplacian matrices and convex relaxations](https://mlsanity.com/paper/1504.03987/) (2015)
- [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)
- [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)
- [Rotation Group Synchronization via Quotient Manifold](https://mlsanity.com/paper/2306.12730/) (2023)
- [ReSync: Riemannian Subgradient-based Robust Rotation Synchronization](https://mlsanity.com/paper/2305.15136/) (2023)
- [Local Geometry Determines Global Landscape in Low-rank Factorization for Synchronization](https://mlsanity.com/paper/2311.18670/) (2023)
- [Non-Convex Joint Community Detection and Group Synchronization via Generalized Power Method](https://mlsanity.com/paper/2112.14204/) (2021)
- [Non-convex Pose Graph Optimization in SLAM via Proximal Linearized Riemannian ADMM](https://mlsanity.com/paper/2404.18560/) (2024)
- [Noisy phase retrieval from subgaussian measurements](https://mlsanity.com/paper/2412.07401/) (2024)

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

- [PolarAdamW: Disentangling Spectral Control and Schur Gauge-Equivariance in Matrix Optimisation](https://mlsanity.com/paper/2605.07067/) (2026)
- [A second-order method landing on the Stiefel manifold via Newtonunicodex2013Schulz iteration](https://mlsanity.com/paper/2605.02838/) (2026)

## Abstract (arXiv)

Group synchronization is a fundamental task involving the recovery of group elements from pairwise measurements. For orthogonal group synchronization, the most common approach reformulates the problem as a constrained nonconvex optimization and solves it using projection-based methods, such as the generalized power method. However, these methods rely on exact SVD or QR decompositions in each iteration, which are computationally expensive and become a bottleneck for large-scale problems. In this paper, we propose a Newton-Schulz-based Riemannian Gradient Scheme (NS-RGS) for orthogonal group synchronization that significantly reduces computational cost by replacing the SVD or QR step with the Newton-Schulz iteration. This approach leverages efficient matrix multiplications and aligns perfectly with modern GPU/TPU architectures. By employing a refined leave-one-out analysis, we overcome the challenge arising from statistical dependencies, and establish that NS-RGS with spectral initialization achieves linear convergence to the target solution up to near-optimal statistical noise levels. Experiments on synthetic data and real-world global alignment tasks demonstrate that NS-RGS attains accuracy comparable to state-of-the-art methods such as the generalized power method, while achieving nearly a 2× speedup.