Efficient Inference for Distributions on Permutations
Jonathan Huang, Carlos Guestrin, Leonidas Guibas Poster ID: W19

Lots of problems require us to reason with permutations, like rankings, voting, data association for tracking, ...
 

Distributions over permutations require O(n!) storage...
Distribution (n=4, n!=24 parameters)

Approximation: Keep "low-frequency" Fourier terms!


keep

ignore

Fourier Transform

Fourier Domain (5 significant parameters)

But... what is the Fourier basis over the permutations? How can we do marginalization and conditioning in the Fourier domain? Answers to these burning questions and results on real tracking data at our poster!