# Probabilistic Permutation Synchronization using the Riemannian Structure of the Birkhoff Polytope

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

## Key facts

- Cited by 26 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 11 Apr 2019.

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

- [BCD Nets: Scalable Variational Approaches for Bayesian Causal Discovery](https://mlsanity.com/paper/2112.02761/) (2021)
- [MultiBodySync: Multi-Body Segmentation and Motion Estimation via 3D Scan Synchronization](https://mlsanity.com/paper/2101.06605/) (2021)
- [Quantum Permutation Synchronization](https://mlsanity.com/paper/2101.07755/) (2021)
- [Projective Manifold Gradient Layer for Deep Rotation Regression](https://mlsanity.com/paper/2110.11657/) (2021)
- [Multiway Non-rigid Point Cloud Registration via Learned Functional Map Synchronization](https://mlsanity.com/paper/2111.12878/) (2021)
- [NRDF: Neural Riemannian Distance Fields for Learning Articulated Pose Priors](https://mlsanity.com/paper/2403.03122/) (2024)
- [Multiway Point Cloud Mosaicking with Diffusion and Global Optimization](https://mlsanity.com/paper/2404.00429/) (2024)
- [Chordal Averaging on Flag Manifolds and Its Applications](https://mlsanity.com/paper/2303.13501/) (2023)
- [Q-FW: A Hybrid Classical-Quantum Frank-Wolfe for Quadratic Binary Optimization](https://mlsanity.com/paper/2203.12633/) (2022)
- [Fast, Accurate and Memory-Efficient Partial Permutation Synchronization](https://mlsanity.com/paper/2203.16505/) (2022)
- [Sparse Quadratic Optimisation over the Stiefel Manifold with Application to Permutation Synchronisation](https://mlsanity.com/paper/2110.00053/) (2021)
- [Mirror Sinkhorn: Fast Online Optimization on Transport Polytopes](https://mlsanity.com/paper/2211.10420/) (2022)
- [GeoNLF: Geometry guided Pose-Free Neural LiDAR Fields](https://mlsanity.com/paper/2407.05597/) (2024)
- [Geometric Neural Distance Fields for Learning Human Motion Priors](https://mlsanity.com/paper/2509.09667/) (2025)
- [Pooling Image Datasets With Multiple Covariate Shift and Imbalance](https://mlsanity.com/paper/2403.02598/) (2024)
- [Joint Deep Multi-Graph Matching and 3D Geometry Learning from Inhomogeneous 2D Image Collections](https://mlsanity.com/paper/2103.17229/) (2021)
- [Kernelized multi-graph matching](https://mlsanity.com/paper/2210.05206/) (2022)
- [Probabilistic Sampling of Balanced K-Means using Adiabatic Quantum Computing](https://mlsanity.com/paper/2310.12153/) (2023)
- [Graph Alignment via Birkhoff Relaxation](https://mlsanity.com/paper/2503.05323/) (2025)
- [Parallelised Differentiable Straightest Geodesics for 3D Meshes](https://mlsanity.com/paper/2603.15780/) (2026)
- [Riemannian Functional Map Synchronization for Probabilistic Partial Correspondence in Shape Networks](https://mlsanity.com/paper/2111.14762/) (2021)
- [Non-Negative Spherical Relaxations for Universe-Free Multi-Matching and Clustering](https://mlsanity.com/paper/2310.13311/) (2023)
- [COMPOSE: Hypergraph Cover Optimization for Multi-view 3D Human Pose Estimation](https://mlsanity.com/paper/2601.09698/) (2026)
- [PDF-HR: Pose Distance Fields for Humanoid Robots](https://mlsanity.com/paper/2602.04851/) (2026)
- [Learning Unbiased Permutations via Flow Matching](https://mlsanity.com/paper/2605.16755/) (2026)
- [DisPOSE: Projected Polystochastic Diffusion for Self-Supervised Multi-View 3D Human Pose Estimation](https://mlsanity.com/paper/2606.07419/) (2026)

## Abstract (arXiv)

We present an entirely new geometric and probabilistic approach to synchronization of correspondences across multiple sets of objects or images. In particular, we present two algorithms: (1) Birkhoff-Riemannian L-BFGS for optimizing the relaxed version of the combinatorially intractable cycle consistency loss in a principled manner, (2) Birkhoff-Riemannian Langevin Monte Carlo for generating samples on the Birkhoff Polytope and estimating the confidence of the found solutions. To this end, we first introduce the very recently developed Riemannian geometry of the Birkhoff Polytope. Next, we introduce a new probabilistic synchronization model in the form of a Markov Random Field (MRF). Finally, based on the first order retraction operators, we formulate our problem as simulating a stochastic differential equation and devise new integrators. We show on both synthetic and real datasets that we achieve high quality multi-graph matching results with faster convergence and reliable confidence/uncertainty estimates.