2
$\begingroup$

I have question regarding convolution of functions (say g and h) defined on Sn. In Fourier space this is equivalent to IFT(G.H), where G = FT(g) and H = FT(h).

Fast Fourier transforms (Clausen's FFT) proceeds by recursively breaking down Fourier transformation over Sn into smaller transforms over S_(n-1), S_(n-2)... and computing each S_(k)-transform from the k independent S_(k-1) transforms.

Now the question I have is - How does the convolution of two functions (g & h, each defined on Sn) translate to S_(n-1)? In other words, is their any defining expression involving G' and H' to provide the n-1 independent S_(n-1) transforms to get final the convolution.

G': descendant Fourier transform of G on S_(n-1) H': descendant Fourier transform of H on S_(n-1) FT: Fourier transform IFT: Inverse Fourier transform

I would appreciate if anyone can direct me to some papers/books which talk about these concepts.

DP

Improve this question
$\endgroup$

2 Answers 2

Reset to default
1
$\begingroup$

It is not an answer to your question, but I hope it will help:

In general arithmetic complexity of convolution in non-anelian groups "equivalent" to the complexity of matrix multiplication. Here is the reason why:

The way of doing Fourier Transform in abelian group $A$ can be described in the is the following way: Let $f,g \in F[A]$ We know that $F[A]$ is isomorphic to the space $F^A$ with pointwise multiplication. Let $T$(which is acctually Fourier Transform) be this isomorphism. If we want calculate $f*g$ then calculate $T^{-1}(T(f)\cdot T(g))$. In case of non abelian group like $S_n$ It holds that $F[G]$ is isomorphic to the direct sum of matrix algebras that is $F[G]\simeq\oplus M_{n_i}$. Thus using the same formula you can calculate convolution in $S_n$, but now you will need to multiply matrixes.

Improve this answer
$\endgroup$
1
  • $\begingroup$ I guess you described convolution on Sn using matrix multiplication. My question is slightly different. Thanks for the response though. Deepti Pachauri $\endgroup$
    – Deepti Pachauri
    Commented Mar 7, 2011 at 19:05

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .