|
|
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].
Papers
[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]
Thesis
R. Kondor:
Group theoretical methods in machine learning
(Columbia University, 2007; advisor: Tony Jebara)
[thesis]
Software
[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]
Events
Risi Kondor, Jason Morton and Lek-Heng Lim:
IMA Summer School on Modern Applications of Representation Theory
(July 21 - August 6, 2014)
[schedule]
[videos]
Grants
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)
|