Multiresolution analysis on the symmetric group

Part of Advances in Neural Information Processing Systems 25 (NIPS 2012)

Bibtex »Metadata »Paper »Supplemental »


Risi Kondor, Walter Dempsey


<p>There is no generally accepted way to define wavelets on permutations. We address this issue by introducing the notion of coset based multiresolution analysis (CMRA) on the symmetric group; find the corresponding wavelet functions; and describe a fast wavelet transform of O(n^p) complexity with small p for sparse signals (in contrast to the O(n^q n!) complexity typical of FFTs). We discuss potential applications in ranking, sparse approximation, and multi-object tracking.</p>