The Robotics Institute

Carnegie Mellon Robotics Institute

Copyright notice: This material is presented to ensure timely dissemination of scholarly and technical work. Copyright and all rights therein are retained by authors or by other copyright holders. All persons copying this information are expected to adhere to the terms and constraints invoked by each author's copyright. These works may not be reposted without the explicit permission of the copyright holder.

Abstract

Permutations are ubiquitous in many real world problems, such as voting, rankings and data association. Representing uncertainty over permutations is challenging, since there are $n!$ possibilities. Recent Fourier-based approaches can be used to provide a compact representation over low-frequency components of the distribution. Though polynomial, the complexity of these representations grows very rapidly, especially if we want to maintain reasonable estimates for peaked distributions. In this paper, we first characterize the notion of probabilistic independence for distributions over permutations. We then present a method for factoring distributions into independent components in the Fourier domain, and use our algorithms to decompose large problems into much smaller ones. We demonstrate that our method provides very significant improvements in terms of running time, on real tracking data.

Notes

Text Reference

Jonathan Huang, Carlos Ernesto Guestrin, Xiaoye Jiang, and Leonidas Guibas, "Exploiting Probabilistic Independence for Permutations," Artificial Intelligence and Statistics (AISTATS 2009), April, 2009.

BibTeX Reference

@inproceedings{Huang_2009_6328,
   author = "Jonathan Huang and Carlos Ernesto Guestrin and Xiaoye Jiang and Leonidas Guibas",
   title = "Exploiting Probabilistic Independence for Permutations",
   booktitle = "Artificial Intelligence and Statistics (AISTATS 2009)",
   month = "April",
   year = "2009",
}

The Robotics Institute

Menu