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

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?

• I'm slightly confused. Could you please specify what kind of an object $U * V$ is? Seems like $U*V(t)$ is a sum of numbers, so is $U*V$ a list of numbers? Also, if $n\not= m$, what is the sum over? – Dmitry Krachun Aug 19 '19 at 19:52
• @DmitryKrachun Capitalization refers to vector of vector variables. Convolution is a vector and the Fourier` transforms are not invertible here. – 1.. Aug 19 '19 at 20:57
• Can't you just take Fourier transform component-wise? – Jochen Wengenroth Aug 20 '19 at 13:26
• Perhaps no speed up is possible. – 1.. Aug 21 '19 at 8:45

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

• Oops, my answer only explicitly addresses the case where the $u_j$'s and $v_j$'s are in $\mathbb{R}$ rather than $\mathbb{R}^d$. There is a "vector valued" version of the Gelfand transform / Pontryagin duality; I can try to dig up a reference if needed. – Paul Siegel Aug 19 '19 at 20:24
• would vector valued nonsense also admit fft? – 1.. Aug 19 '19 at 20:53
• @Turbo The DFT (and therefore the FFT) lives on the group $G = \mathbb{Z} / n \mathbb{Z}$, so I'm not sure how to reconcile that with the definition of convolution that you gave in the question - normally the notion of convolution which is compatible with the DFT is the so-called "circle convolution", which requires that $U$ and $V$ have the same number of components so that they can be periodically extended. I'm not immediately sure whether the FFT extends to that notion of vector-valued DFT, but it would be sort of weird if it didn't. – Paul Siegel Aug 19 '19 at 22:09
• Hadamard Product of Fourier transform of two vectors is Fourier transform of convolution of the two vectors. We can interpret $u_i,v_j\in\mathbb R^d$ as fourier transform of convolution of inverse fourier transform of $u_i,v_j$ and the inner product is sum of the elements of the fourier transform and it might be possible to relegate the summation operation needed for inner product as a special operation in the end. Perhaps there is a different way to look at things. – 1.. Aug 20 '19 at 9:24