The Fast Fourier Transform problem is to evaluate the matrix-vector product $$ X = W x $$ quickly, where $x$ is the input signal and $W$ is the DFT matrix, $$ W = \frac{1}{\sqrt{N}} \pmatrix{ 1 & 1 & 1 & \cdots & 1 \\ 1 & \omega & \omega^2 & \cdots & \omega^{N-1} \\ 1 & \omega^2 & \omega^4 & \cdots & \omega^{2(N-1)} \\ \vdots & \vdots & \vdots & \cdots & \vdots \\ 1 & \omega^{N-1} & \omega^{2(N-1)} & \cdots & \omega^{(N-1)(N-1)} } $$ with $\omega = e^{-2\pi i / N}$. The FFT works by using the symmetry of the matrix $W$ to factor it into a product of sparse matrices, i.e. $$ W = S_1 S_2 \cdots S_n $$ if $N = 2^n$. Computing $n$ sparse matrix-vector products is much faster than computing the original dense matrix-vector product.

Since symmetry plays such an important role in the FFT, I was wondering if there is a nice derivation of the FFT using group theory. In other words can group theory be used to find the sparse factors of the $W$ matrix? I would appreciate a nice reference on this topic if anyone knows of one.

  • 2
    $\begingroup$ Group representation theory is useful and there exist DFT / FFT over abelian groups. Over non-abelian groups it is a bit more involved. Consider the work of Rockmore et al.: arxiv.org/pdf/1609.02634.pdf $\endgroup$ – Wuestenfux Jun 8 '17 at 12:20
  • 2
    $\begingroup$ Group theory (representation theory of abelian grapes in particular) gives us all kinds of DFTs. See e.g. this $\endgroup$ – Jyrki Lahtonen Jun 8 '17 at 12:34

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.