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

$\endgroup$

2 Answers 2

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.

$\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$ Mar 7, 2011 at 19:05

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.