Towards a Theory of Group Convolution

Let $G$ be a finite group. Following S. D. Berman and I. I. Grushko, we give general definitions of the $G$-spectrum and $G$-convolution that, in the case of Abelian groups $G$, coincide with the conventional definitions. We also find estimates on the computational complexity of group-theoretic convolution for non-Abelian groups in terms of degrees of irreducible representations of these groups. For a number of cases, this construction enables a time gain for some values of length of the convolved signals.