Abstract
Performing Bayesian inference over the space of permutations is a significant challenge in combinatorial optimization due to the factorial growth of the state space. This paper introduces a geometric approach that embeds the discrete space of $n!$ permutations into a continuous hypersphere. By utilizing directional statistics, specifically the von Mises-Fisher distribution, the authors develop a scalable recursive Bayesian filter for tracking and ranking. The method is evaluated on synthetic data, air traffic control records, and visual surveillance datasets, demonstrating superior scalability and efficiency compared to existing Fourier-based techniques.
Introduction
Permutations are fundamental to tasks like multi-object tracking and ranking. However, the space of permutations for $n$ objects grows at a rate of $n!$, making explicit representation of probability distributions impossible for even moderately sized $n$. Previous attempts using Fourier analysis or metric-based methods often suffer from high computational complexity or lack the smooth structure necessary for standard analytic tools. This work bridges the gap between unstructured combinatorial sets and structured continuous spaces by embedding permutations into a hypersphere.
Methods
The authors propose a geometric solution that maps the discrete space of permutations into a continuous domain where directional statistics can be applied.
The Hypersphere Embedding
Permutation matrices of size $n \times n$ are treated as vectors in $\mathbb{R}^{n^2}$. The authors leverage the fact that these matrices are the extreme points of the Birkhoff polytope (the set of all doubly stochastic matrices). They prove that these $n!$ points lie on the surface of a hypersphere within a lower-dimensional subspace of dimension $(n-1)^2$. This embedding is advantageous because it preserves the "closeness" of permutations; for instance, permutations differing by a single swap remain nearby in the continuous space.
Directional Statistics and the vMF Distribution
Once mapped to the sphere, the authors employ the von Mises-Fisher (vMF) distribution, often considered the spherical analogue of the Gaussian distribution. It is defined by a mean direction $\mu$ and a concentration parameter $\kappa$.
Efficient Projections and Filtering
The transition between discrete permutations and continuous spherical points is computationally efficient. Mapping to the sphere involves a linear shift and basis change ($O(n^4)$). The inverse mapping—finding the permutation closest to a point on the sphere—is formulated as a minimum weighted bipartite matching problem, solvable in polynomial time. This framework allows for the derivation of a recursive Bayesian filter, similar to a Kalman filter, which updates the distribution over permutations as noisy observations are received.
Experimental Evaluation
The model was tested across three distinct scenarios:
- Synthetic Data: Tracking up to 50 objects with varying noise levels.
- Air Traffic Control: Managing identities of aircraft near JFK airport, a standard benchmark for identity management.
- Visual Surveillance: Tracking 41 players in a soccer match (PETS dataset), demonstrating the model's ability to handle large-scale, real-world tracking.
Key Results and Insights
The proposed approach demonstrates significant improvements in scalability and efficiency. While Fourier-based methods struggle beyond $n=15$, this framework handles over 50 objects with ease. For 80 objects, the mean convergence time was approximately 17.2 seconds on 2011-era hardware. On the JFK dataset, the vMF filter achieved error rates (0.12–0.17) comparable to state-of-the-art methods but with much lower computational cost.
A critical insight is the handling of partial observations. In the hypersphere representation, marginalizing out missing objects corresponds to another vMF distribution, allowing for an elegant treatment of incomplete data.
Conclusion and Future Work
This work provides a robust framework for Bayesian inference on permutations by leveraging the geometry of the hypersphere. While the marginalization step requires an approximation using angular Gaussians, the results are highly accurate in practice. Future research may explore more complex spherical distributions or the use of spherical harmonics to represent multi-modal distributions.
Summary updated