Probabilistic Inference on the Symmetric Group

Introduction

Permutations are ubiquitous in real world problems such as voting, rankings, and data association. Representing uncertainty over permutations is challenging, however, since there are n! possibilities and typical approaches such as graphical models do not capture the inherent mutual exclusivity constraints. Instead,we use the "low frequency" terms of a Fourier decomposition to represent distributions compactly. We develop intuitive and efficient approximate inference algorithms defined directly in the Fourier domain and show that they are effective in a real camera-based multi-person tracking setting.