Is there (fast) fourier transform for vector convolution?

Question

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.$$

1. 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?

2. 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?

Answer 1

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.)