Computing Fourier transforms and convolutions of -invariant signals on in time linear in

Abstract: Let denote the symmetric group on and the stabilizer subgroup of . We derive algorithms for computing Fourier transforms of left and right -invariant signals that require a total of additions and scalar multiplications. Furthermore we show that the convolution of such signals can also be computed in time linear in . [Copyright &y& Elsevier]