nips nips2012 nips2012-234 nips2012-234-reference knowledge-graph by maker-knowledge-mining
Source: pdf
Author: Risi Kondor, Walter Dempsey
Abstract: 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 for sparse signals. We discuss potential applications in ranking, sparse approximation, and multi-object tracking. 1
[1] J. Huang, C. Guestrin, and L. Guibas. Fourier Theoretic Probabilistic Inference over Permutations. Journal of Machine Learning Research, 10:997–1070, 2009.
[2] R. Kondor, A. Howard, and T. Jebara. Multi-object tracking with representations of the symmetric group. In Artificial Intelligence and Statistics (AISTATS), 2007.
[3] S. Jagabathula and D. Shah. Inferring Rankings under Constrained Sensing. In In Advances in Neural Information Processing Systems (NIPS), 2008.
[4] J. Huang, C. Guestrin, X. Jiang, and L. Guibas. Exploiting Probabilistic Independence for Permutations. In Artificial Intelligence and Statistics (AISTATS), 2009.
[5] X. Jiang, J. Huang, and L. Guibas. Fourier-information duality in the identity management problem. In In Proceedings of the European Conference on Machine Learning and Principles and Practice of Knowledge Discovery in Databases (ECML PKDD), Athens, Greece, September 2011.
[6] D. Rockmore, P. Kostelec, W. Hordijk, and P. F. Stadler. Fast Fourier Transforms for Fitness Landscapes. Applied and Computational Harmonic Analysis, 12(1):57–76, 2002.
[7] P. Diaconis. Group representations in probability and statistics. Institute of Mathematical Statistics, 1988.
[8] M. Gavish, B. Nadler, and R. R. Coifman. Multiscale Wavelets on Trees, Graphs and High Dimensional Data: Theory and Applications to Semi Supervised Learning. In International Conference on Machine Learning (ICML), 2010.
[9] R. R. Coifman and M. Maggioni. Diffusion wavelets. Applied and Computational Harmonic Analysis, 21, 2006.
[10] D. K. Hammond, P. Vandergheynst, and R. Gribonval. Wavelets on graphs via spectral graph theory. Applied and Computational Harmonic Analysis, 30:129–150, 2011.
[11] S. G. Mallat. A Theory for Multiresolution Signal Decomposition. IEEE Transactions on Pattern Analysis and Machine Intelligence, 11:674–693, 1989.
[12] M. Clausen. Fast generalized Fourier transforms. Theor. Comput. Sci., 67(1):55–63, 1989.
[13] D. Maslen and D. Rockmore. Generalized FFTs – a survey of some recent results. In Groups and Computation II, volume 28 of DIMACS Ser. Discrete Math. Theor. Comput. Sci., pages 183–287. AMS, Providence, RI, 1997.
[14] D. K. Maslen and D. N. Rockmore. Separation of Variables and the Computation of Fourier Transforms on Finite Groups, I. Journal of the American Mathematical Society, 10:169–214, 1997. 9