# SE-Sync: A Certifiably Correct Algorithm for Synchronization over the Special Euclidean Group

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

## Key facts

- Cited by 80 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 21 Dec 2016.

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

- [Kimera: from SLAM to Spatial Perception with 3D Dynamic Scene Graphs](https://mlsanity.com/paper/2101.06894/) (2021)
- [Theseus: A Library for Differentiable Nonlinear Optimization](https://mlsanity.com/paper/2207.09442/) (2022)
- [Kimera-Multi: Robust, Distributed, Dense Metric-Semantic SLAM for Multi-Robot Systems](https://mlsanity.com/paper/2106.14386/) (2021)
- [HRegNet: A Hierarchical Network for Large-scale Outdoor LiDAR Point Cloud Registration](https://mlsanity.com/paper/2107.11992/) (2021)
- [MultiBodySync: Multi-Body Segmentation and Motion Estimation via 3D Scan Synchronization](https://mlsanity.com/paper/2101.06605/) (2021)
- [Object Pose Estimation with Statistical Guarantees: Conformal Keypoint Detection and Geometric Uncertainty Propagation](https://mlsanity.com/paper/2303.12246/) (2023)
- [LU-NeRF: Scene and Pose Estimation by Synchronizing Local Unposed NeRFs](https://mlsanity.com/paper/2306.05410/) (2023)
- [Quantum Permutation Synchronization](https://mlsanity.com/paper/2101.07755/) (2021)
- [HARA: A Hierarchical Approach for Robust Rotation Averaging](https://mlsanity.com/paper/2111.08831/) (2021)
- [Certifiably Optimal Outlier-Robust Geometric Perception: Semidefinite Relaxations and Scalable Global Optimization](https://mlsanity.com/paper/2109.03349/) (2021)
- [Preconditioned Gradient Descent for Overparameterized Nonconvex Burer--Monteiro Factorization with Global Optimality Certification](https://mlsanity.com/paper/2206.03345/) (2022)
- [PCAM: Product of Cross-Attention Matrices for Rigid Registration of Point Clouds](https://mlsanity.com/paper/2110.01269/) (2021)
- [Hybrid Rotation Averaging: A Fast and Robust Rotation Averaging Approach](https://mlsanity.com/paper/2101.09116/) (2021)
- [Distributional Depth-Based Estimation of Object Articulation Models](https://mlsanity.com/paper/2108.05875/) (2021)
- [Advances in Inference and Representation for Simultaneous Localization and Mapping](https://mlsanity.com/paper/2103.05041/) (2021)
- [Quantum Motion Segmentation](https://mlsanity.com/paper/2203.13185/) (2022)
- [Optimal Pose and Shape Estimation for Category-level 3D Object Perception](https://mlsanity.com/paper/2104.08383/) (2021)
- [Rotation Coordinate Descent for Fast Globally Optimal Rotation Averaging](https://mlsanity.com/paper/2103.08292/) (2021)
- [MatchNorm: Learning-based Point Cloud Registration for 6D Object Pose Estimation in the Real World](https://mlsanity.com/paper/2203.15309/) (2022)
- [Improved Global Guarantees for the Nonconvex Burer--Monteiro Factorization via Rank Overparameterization](https://mlsanity.com/paper/2207.01789/) (2022)
- [Advances in Global Solvers for 3D Vision](https://mlsanity.com/paper/2602.14662/) (2026)
- [Rotation Averaging in a Split Second: A Primal-Dual Method and a Closed-Form for Cycle Graphs](https://mlsanity.com/paper/2109.08046/) (2021)
- [Estimation Contracts for Outlier-Robust Geometric Perception](https://mlsanity.com/paper/2208.10521/) (2022)
- [GlobalPointer: Large-Scale Plane Adjustment with Bi-Convex Relaxation](https://mlsanity.com/paper/2407.13537/) (2024)
- [An Inexact Projected Gradient Method with Rounding and Lifting by Nonlinear Programming for Solving Rank-One Semidefinite Relaxation of Polynomial Optimization](https://mlsanity.com/paper/2105.14033/) (2021)
- [A Robot Web for Distributed Many-Device Localisation](https://mlsanity.com/paper/2202.03314/) (2022)
- [Snapshot of Algebraic Vision](https://mlsanity.com/paper/2210.11443/) (2022)
- [A Survey on Computational Solutions for Reconstructing Complete Objects by Reassembling Their Fractured Parts](https://mlsanity.com/paper/2410.14770/) (2024)
- [Building Rome with Convex Optimization](https://mlsanity.com/paper/2502.04640/) (2025)
- [On the Tightness of Semidefinite Relaxations for Rotation Estimation](https://mlsanity.com/paper/2101.02099/) (2021)

## Abstract (arXiv)

Many important geometric estimation problems take the form of synchronization over the special Euclidean group: estimate the values of a set of poses given a set of relative measurements between them. This problem is typically formulated as a nonconvex maximum-likelihood estimation that is computationally hard to solve in general. Nevertheless, in this paper we present an algorithm that is able to efficiently recover certifiably globally optimal solutions of the special Euclidean synchronization problem in a non-adversarial noise regime. The crux of our approach is the development of a semidefinite relaxation of the maximum-likelihood estimation whose minimizer provides an exact MLE so long as the magnitude of the noise corrupting the available measurements falls below a certain critical threshold; furthermore, whenever exactness obtains, it is possible to verify this fact a posteriori, thereby certifying the optimality of the recovered estimate. We develop a specialized optimization scheme for solving large-scale instances of this relaxation by exploiting its low-rank, geometric, and graph-theoretic structure to reduce it to an equivalent optimization problem on a low-dimensional Riemannian manifold, and design a truncated-Newton trust-region method to solve this reduction efficiently. Finally, we combine this fast optimization approach with a simple rounding procedure to produce our algorithm, SE-Sync. Experimental evaluation on a variety of simulated and real-world pose-graph SLAM datasets shows that SE-Sync is able to recover certifiably globally optimal solutions when the available measurements are corrupted by noise up to an order of magnitude greater than that typically encountered in robotics and computer vision applications, and does so more than an order of magnitude faster than the Gauss-Newton-based approach that forms the basis of current state-of-the-art techniques.