Probabilistic Permutation Synchronization using the Riemannian Structure of the Birkhoff Polytope

Abstract

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.

arXiv commentTo appear as oral presentation at CVPR 2019. 20 pages including the supplementary material

References in corpus (16)

• Manopt, a Matlab toolbox for optimization on manifolds
• A Complete Recipe for Stochastic Gradient MCMC
• A General Multi-Graph Matching Approach via Graduated Consistency-regularized Boosting
• On the Convergence of Stochastic Gradient MCMC Algorithms with High-Order Integrators
• Langevin diffusions and the Metropolis-adjusted Langevin algorithm
• Near-Optimal Joint Object Matching via Convex Relaxation
• Geodesic Monte Carlo on Embedded Manifolds
• A Solution for Multi-Alignment by Transformation Synchronisation
• Averaging Stochastic Gradient Descent on Riemannian Manifolds
• Manifold Optimization Over the Set of Doubly Stochastic Matrices: A Second-Order Geometry
• Synchronisation of Partial Multi-Matchings via Non-negative Factorisations
• Bayesian Pose Graph Optimization via Bingham Distributions and Tempered Geodesic MCMC
• Distributed methods for synchronization of orthogonal matrices over graphs
• A Structured Prediction Approach for Label Ranking
• Initialization and Coordinate Optimization for Multi-way Matching
• Note on the geodesic Monte Carlo

Cited by in corpus (6)

• Geoopt: Riemannian Optimization in PyTorch
• Multiway Non-rigid Point Cloud Registration via Learned Functional Map Synchronization
• MultiBodySync: Multi-Body Segmentation and Motion Estimation via 3D Scan Synchronization
• Sparse Quadratic Optimisation over the Stiefel Manifold with Application to Permutation Synchronisation
• Non-Negative Spherical Relaxations for Universe-Free Multi-Matching and Clustering
• 6D Camera Relocalization in Ambiguous Scenes via Continuous Multimodal Inference