Fourier analysis on permutations

The Fourier transform is one of the cornerstones of Mathematics. As it is well known, on the real line the Fourier transform takes the form \[\hat f(\omega)=\int f(x)\,e^{-2\pi i x\omega}\,dx.\] It is less well known that the Fourier transform has a natural generalization to any finite group: if  \(f\) is a function on a fininte group \(G\), its Fourier transform is \[\hat f(\rho)=\sum_{x\in G} f(x)\,\rho(x)\] where \(\rho\) are certain matrix valued functions called the irreducible representations of \(G\). While at first sight this definition seems strange because it says that Fourier transform is now a collection of matrices (of different sizes), in fact, this type of generalized Fourier transform inherits many of the most important properties of the ordinary Fourier transform, such as Plancherel's theorem, the convolution theorem, and so on.

I am particularly interested in the case where \(G\) is the so-called symmetric group, i.e., the group of permutations of \(n\) objects. Our paper [P1] was the first to introduce Fourier analysis on the symmetric group to Machine Learning, in the context of multi-object tracking. In [P2] and [P3] we used the same tools to constructs graph invariants, and hence a graph kernel, which can be used for learning graph-structured data, such as molecules. In [P8]-[P10] we used Fourier theoretic methods to solve the image association problem in computer vision and in [P6] I showed that the Fourier method can even be used to help solve the famed quadratic assignment problem. Finally, in [P7] we defined a representation theory based notion of wavelets on the symmetric group.

Due to the super-exponential size of the symmetric group, none of these applications would be realistic without the special fast Fourier transform (FFT) methods that have been developed for the symmetric group. My SnOB library [S1] was the first efficient implementation of the Clausen's symmetric group FFT. See also our new Julia-based implementation, [S2].


[P1]  R. Kondor, A. Howard and T. Jebara:  Multi-object tracking with representations of the symmetric group (AISTATS 2007)  [paper] [Newton video] [AISPDS video]

[P2]  R. Kondor:  Non-commutative harmonic analysis in multi-object tracking in "Bayesian Time-series Models" ed. D. Barber, A. T. Cemgil and S. Chiappa (Cambridge University Press, 2011)  [paper]

[P3]  R. Kondor and K. M. Borgwardt:  The skew spectrum of graphs (ICML 2008)  [paper] [ICML video] [C++ code]

[P4]  R. Kondor, N. Shervashidze and K. M. Borgwardt:  The graphlet spectrum (ICML 2009)  [paper]

[P5]  R. Kondor and M. Barbosa:  Ranking with kernels in Fourier space (COLT 2010)  [paper] [supplement]

[P6]  R. Kondor:  A Fourier space algorithm for solving quadratic assignment problems (SODA 2010)  [pdf]

[P7]  R. Kondor, W. Dempsey:  Multiresolution analysis on the symmetric group (NIPS 2012)  [paper] [supplement]

[P8]  D. Pachauri, M. Collins, R. Kondor, V. Singh:  Incorporating domain knowledge in matching problems via harmonic analysis (ICML 2012)  [paper]

[P9]  D. Pachauri, R. Kondor and V. Singh:  Solving the multi-way matching problem by permutation synchronization (NIPS 2013)  [paper]

[P10]  D. Pachauri, R. Kondor, G. Sargur and V. Singh:  Permutation diffusion maps with application to the image association problem in computer vision (NIPS 2014)  [paper]


R. Kondor: Group theoretical methods in machine learning (Columbia University, 2007; advisor: Tony Jebara) [thesis]


[S1]  R. Kondor: SnOB: a C++ library for computing fast Fourier transforms on the symmetric group (2006-)  [SnOB]

[S2]  G. Plumb, D. Pachauri, R. Kondor and V. Singh: Sn--FFT: A Julia toolkit for for harmonic analysis on the symmetric group (2015)  [GitHub] [JMLR paper]


Risi Kondor, Jason Morton and Lek-Heng Lim: IMA Summer School on Modern Applications of Representation Theory (July 21 - August 6, 2014)  [schedule] [videos]


R. Kondor and V.Singh: Solving matching problems in machine learning with non-commutative harmonic analysis (NSF CCF132-0344, Total award: 424,205)  [grant]

Risi Kondor, Jason Morton and Lek-Heng Lim: Supplementary grant for the IMA Summer school on modern applications of representation theory (NSF DMS-1417916, total award: $39,920)