Abstract
Distributions over permutations arise in applications ranging from multi-object tracking to ranking of instances. The difficulty of dealing with these distributions is caused by the size of their domain, which is factorial in the number of considered entities ($n!$). It makes the direct definition of a multinomial distribution over permutation space impractical for all but a very small $n$. In this work we propose an embedding of all $n!$ permutations for a given $n$ in a surface of a hypersphere defined in $\mathbbm{R}^{(n-1)^2}$. As a result of the embedding, we acquire ability to define continuous distributions over a hypersphere with all the benefits of directional statistics. We provide polynomial time projections between the continuous hypersphere representation and the $n!$-element permutation space. The framework provides a way to use continuous directional probability densities and the methods developed thereof for establishing densities over permutations. As a demonstration of the benefits of the framework we derive an inference procedure for a state-space model over permutations. We demonstrate the approach with applications.
Introduction
The management of distributions over permutations is a fundamental challenge in fields like multi-object tracking and preference ranking. The primary obstacle is the "factorial explosion"—the size of the permutation space $n!$ grows at a rate that makes direct multinomial modeling computationally infeasible for even modest values of $n$. For instance, tracking just 15 objects involves over a trillion possible orderings. Traditional combinatorial spaces lack the continuous structure and derivatives necessary for efficient optimization. While Fourier-based methods on the symmetric group offer a mathematical alternative, they typically encounter a computational ceiling around $n=15$.
Methodology: Embedding Permutations in Continuous Space
To overcome these limitations, this work proposes a framework that embeds discrete permutations into a continuous, high-dimensional hypersphere.
- The Embedding: Each permutation is represented as an $n \times n$ matrix. The authors prove that these matrices for a given $n$ lie on the surface of a hypersphere ($\mathbb{S}^d$) within a subspace of dimension $(n-1)^2$.
- Directional Statistics: By mapping permutations to the sphere, the framework leverages the von Mises-Fisher (vMF) distribution—often described as the "Gaussian of the sphere." This distribution is characterized by a mean direction (representing the "true" permutation) and a concentration parameter $\kappa$ (representing certainty).
- Projections: The framework utilizes polynomial-time projections. Moving from discrete permutations to the continuous sphere is an $O(n^4)$ operation. Conversely, finding the discrete permutation closest to a point on the sphere is achieved via the Hungarian algorithm in $O(n^3)$.
- State-Space Modeling: The authors derive a recursive filtering model, akin to a Kalman Filter, allowing for analytical updates and marginalization, which is essential for handling partial observations where some object identities are unknown.
Evaluation and Results
The approach was validated across synthetic and real-world datasets:
- Synthetic Benchmarks: Tests with 25 and 50 objects demonstrated the scalability of the embedding and its robustness to noise.
- Air Traffic Control (ATC): Tracking 6 to 10 aircraft near JFK Airport yielded error rates (0.12–0.17) comparable to state-of-the-art methods but with significantly higher efficiency.
- Football Surveillance: The model successfully tracked 41 players on a pitch, a scale far exceeding the typical limits of previous Fourier-based methods.
Key Insights
The "aha moment" of this research is the realization that permutations possess a geometric structure compatible with hyperspherical manifolds. This "lifting" of the factorial curse allows the application of continuous calculus and directional statistics to discrete problems. Furthermore, the ability to marginalize unknown data by falling back to lower-dimensional subspaces makes the framework highly practical for real-world scenarios with missing observations.
Conclusion and Future Work
While the current model assumes a vMF transition, future work could explore more complex transition models or the broader exponential family of distributions on spheres. Additionally, using spherical harmonics could allow for representing multi-modal distributions. This framework represents a significant step toward bridging the gap between discrete combinatorial optimization and continuous statistical inference.
Summary updated