Is there (fast) fourier transform for vector convolution? Given a list of variables $u_1,\dots,u_m\in\mathbb R$ and $v_1,\dots,v_n\in\mathbb R$ the standard convolution is defined
$$U*V(t)={\sum_{i}} u_iv_{t-i}.$$
Given a list of vectors $u_1,\dots,u_m\in\mathbb R^d$ and $v_1,\dots,v_n\in\mathbb R^d$ define vector-convolution $$U*V(t)={\sum_{i}}u_iv_{t-i}^T.$$


*

*Is there a Fourier transform for this convolutions that converts this to a 'product' $\widetilde U(f)\cdot\widetilde V(f)$ from which we can perform inverse fourier transform to get the convolution?


*Can we replace $u_iv_{t-i}^T$ by a polynomial or a rational function with $u_i,v_i\in\mathbb R^d$ arguments ($2d$ variables)?

Do these admit $FFT$`s?
 A: I think this all falls out of general nonsense with group algebras.  Given a locally compact group $G$ there is a homomorphism of Banach algebras $\mathcal{F} \colon L^1(G) \to C_0(\hat{G})$ where:


*

*$L^1(G)$ is the space of integrable functions with respect to Haar measure

*The Banach algebra structure on $L^1(G)$ is given by convolution

*$\hat{G} = \text{Hom}(G, S^1)$ is the Pontryagin dual of $G$
This map $\mathcal{F}$ is the Fourier transform that you're looking for, where $G$ is just the additive group $\mathbb{Z}$.  (I'm viewing $U$ and $V$ as compactly supported functions on $\mathbb{Z}$, which certainly are in $L^1(\mathbb{Z})$.)  The fact that $\mathcal{F}$ is a homomorphism of Banach algebras means it carries convolution to multiplication, and the Pontryagin duality theorem says that there is an inverse Fourier transform which implements the isomorphism between $G$ and its double dual.
You can extract the details from a representation theory textbook, but unwinding the definitions the formula you get for $\mathcal{F}$ is:
$$\mathcal{F}U(t) = \sum_j u_j e^{-2 \pi i j t}$$
(Well, you might get slightly different formulas depending on your conventions for writing down the Haar measure.)
