J. Huang, C. Guestrin, L. Guibas. Fourier Theoretic Probabilistic Inference over Permutations. Journal of Machine Learning (JMLR), Volume 10 pp. 997-1070, May 2009


Permutations are ubiquitous in many real-world problems, such as voting, ranking, and data association. Representing uncertainty over permutations is challenging, since there are $n!$ possibilities, and typical compact and factorized probability distribution representations, such as graphical models, cannot capture the mutual exclusivity constraints associated with permutations. In this paper, we use the ``low-frequency'' terms of a Fourier decomposition to represent distributions over permutations compactly. We present emph{Kronecker conditioning}, a novel approach for maintaining and updating these distributions directly in the Fourier domain, allowing for polynomial time bandlimited approximations. Low order Fourier-based approximations, however, may lead to functions that do not correspond to valid distributions. To address this problem, we present a quadratic program defined directly in the Fourier domain for projecting the approximation onto a relaxation of the polytope of legal marginal distributions. We demonstrate the effectiveness of our approach on a real camera-based multi-person tracking scenario.


author = {Jonathan Huang and Carlos Guestrin and Leonidas Guibas},
title = {Fourier Theoretic Probabilistic Inference over Permutations},
journal = {Journal of Machine Learning Research (JMLR)},
year = {2009},
volume = {10},
pages = {997-1070},
month = {May},