Fast generalized DFT for finite groups

Almost 6 months ago, I came across an interesting update through the UT CS theory seminar group on the classic problem on the computation of the Discrete Fourier Transform(DFT) of finite groups. Chris Umans, from Caltech, made some pretty nice improvements to the complexity of the general DFT through some slick combinatorics , which I’ll shortly explain. The paper is here.

Introduction

Well, before I even start, perhaps, I should make some kind of a comment to motivate the problem at hand. A sequence of n complex numbers (x_{i}) can be represented by a function f:\mathbb{Z}_{n} \to \mathbb{C}.

A Discrete Fourier Transform of (x_{i}) sends it to the sequence (F_{i}) where F_{i}=\sum\limits_{j=0}^{n-1}x_{j}e^{\frac{-i2\pi k j}{n}}.

This motivates the definition of the Fourier transform \hat{f} of a function from a finite group f : G \to \mathbb{C} which takes as input a representation \rho:G \to GL(d_{\rho},\mathbb{C}), i.e

\hat{f}(\rho)=\sum\limits_{g \in G} f(g)\rho(g)

where one must note that here, more generally, \rho(g) can be matrix-valued.From Maschke’s theorem, the DFT of a finite group reduces to a map which takes as input an element \alpha \in latex \mathbb{C}[G](group ring consisting of all functions from G to \mathbb{C} under convolution)and sends it to \sum\limits_{g} \alpha(g) \bigoplus_{\rho \in Irr(G)}\rho(g). Throughout, one assumes that we have already have the \rho and chosen a basis for each \rho.

Quite simply, one trivially gets that this requires O(|G|^{2}) operations. Exponent-one algorithms exist for abelian groups(as one would expect using the decomposition into cyclic groups), supersolvable and certain classes of symmetric and alternating groups.

Throughout the post, let \omega be the exponent of matrix multiplication(currently it is around 2.38 I guess).

The main result is that Chris Umans achieves an operation complexity of O(|G|^{\frac{\omega}{2}}. Some basic facts from representation theory will be used throughout though I guess most readers would already be familiar with that. For example, it is easy to prove that through the Schur orthogonality relations is that \sum\limits_{i} |V_{i}|^{2}=|G| where the V_{i} is the set of all irreducible representations of G. This gives us the useful lemma.

Lemma 1:

For every real number \alpha \geq 2, \sum\limits_{\rho \in Irr(G)} dim(\rho)^{\alpha} \leq |G|^{\frac{\alpha}{2}}(Proof omitted)


Some facts about the induced representation and Clifford theory are used but it shouldn’t be too much of a hassle to discuss it on-the-fly.

The Support Trick

Let G be a group and S, a subset. Let’s assume that we can caluclate the generalized DFT with respect to G for all inputs \alpha \in \mathbb{C}[G] supported on S(i.e components \alpha_{g}=0 for g \not\in S) in m operations. Surely, with some extra computational cost(involving the index of S), one can extend this to all inputs because if we can compute DFT supported on S then we can compute DFT supported on Sg' by multiplying  \sum\limits_{g} \alpha(g) \bigoplus_{\rho \in Irr(G)}\rho(g) by \bigoplus_{\rho \in Irr(G)} \rho(g') which has an additional operation cost of \sum\limits_{\rho \in Irr(G)} O(dim(\rho)^{\omega+\epsilon}. We can apply Lemma 1,take appropriate number of ‘shifts/translates’ by elements of G to get the following result(see Section 2.3):

Continue reading “Fast generalized DFT for finite groups”