# Multi-Irreducible Spectral Synchronization for Robust Rotation Averaging

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 14 of its 44 references that are in the map.
- First posted on arXiv 28 Nov 2023.

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

- [Geometric Deep Learning: Grids, Groups, Graphs, Geodesics, and Gauges](https://mlsanity.com/paper/2104.13478/) (2021)
- [Past, Present, and Future of Simultaneous Localization And Mapping: Towards the Robust-Perception Age](https://mlsanity.com/paper/1606.05830/) (2016)
- [Graduated Non-Convexity for Robust Spatial Perception: From Non-Minimal Solvers to Global Outlier Rejection](https://mlsanity.com/paper/1909.08605/) (2019)
- [SE-Sync: A Certifiably Correct Algorithm for Synchronization over the Special Euclidean Group](https://mlsanity.com/paper/1612.07386/) (2016)
- [Implicit-PDF: Non-Parametric Representation of Probability Distributions on the Rotation Manifold](https://mlsanity.com/paper/2106.05965/) (2021)
- [Shonan Rotation Averaging: Global Optimality by Surfing SO(p)n](https://mlsanity.com/paper/2008.02737/) (2020)
- [Near-Optimal Performance Bounds for Orthogonal and Permutation Group Synchronization via Spectral Methods](https://mlsanity.com/paper/2008.05341/) (2020)
- [Unperturbed: spectral analysis beyond Davis-Kahan](https://mlsanity.com/paper/1706.06516/) (2017)
- [Advances in Inference and Representation for Simultaneous Localization and Mapping](https://mlsanity.com/paper/2103.05041/) (2021)
- [Non-unique games over compact groups and orientation estimation in cryo-EM](https://mlsanity.com/paper/1505.03840/) (2015)
- [Performance Guarantees for Spectral Initialization in Rotation Averaging and Pose-Graph SLAM](https://mlsanity.com/paper/2201.03773/) (2022)
- [Multi-Frequency Phase Synchronization](https://mlsanity.com/paper/1901.08235/) (2019)
- [The Role of Principal Angles in Subspace Classification](https://mlsanity.com/paper/1507.04230/) (2015)
- [Representation Theoretic Patterns in Multi-Frequency Class Averaging for Three-Dimensional Cryo-Electron Microscopy](https://mlsanity.com/paper/1906.01082/) (2019)

## Abstract (arXiv)

Rotation averaging (RA) is a fundamental problem in robotics and computer vision. In RA, the goal is to estimate a set of N unknown orientations R1, ..., RN ∈ SO(3), given noisy measurements Rij ~ R-1i Rj of a subset of their pairwise relative rotations. This problem is both nonconvex and NP-hard, and thus difficult to solve in the general case. We apply harmonic analysis on compact groups to derive a (convex) spectral relaxation constructed from truncated Fourier decompositions of the individual summands appearing in the RA objective; we then recover an estimate of the RA solution by computing a few extremal eigenpairs of this relaxation, and (approximately) solving a consensus problem. Our approach affords several notable advantages versus prior RA methods: it can be used in conjunction with any smooth loss function (including, but not limited to, robust M-estimators), does not require any initialization, and is implemented using only simple (and highly scalable) linear-algebraic computations and parallelizable optimizations over band-limited functions of individual rotational states. Moreover, under the (physically well-motivated) assumption of multiplicative Langevin measurement noise, we derive explicit performance guarantees for our spectral estimator (in the form of probabilistic tail bounds on the estimation error) that are parameterized in terms of graph-theoretic quantities of the underlying measurement network. By concretely linking estimator performance with properties of the underlying measurement graph, our results also indicate how to devise measurement networks that are guaranteed to achieve accurate estimation, enabling such downstream tasks as sensor placement, network compression, and active sensing.