NIPS Proceedingsβ

Multiresolution analysis on the symmetric group

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

[PDF] [BibTeX] [Supplemental]



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.