T. Birdal, U. Simsekli Probabilistic Permutation Synchronization using the Riemannian Structure of the Birkhoff Polytope IEEE Computer Vision and Pattern Recognition (CVPR), Long Beach, United States, June 2019 [oral] (bib)
	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 model in the form of a Markov Random Field (MRF), whose normalizing constant is provably not dependent on the parameters. Finally, based on the first order retraction operators, we formulate our problem as a stochastic differential equation (SDE) 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.
	This material is presented to ensure timely dissemination of scholarly and technical work. Copyright and all rights therein are retained by authors or by other copyright holders. All persons copying this information are expected to adhere to the terms and constraints invoked by each authors copyright. In most cases, these works may not be reposted without the explicit permission of the copyright holder.