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?

  • 1
    $\begingroup$ 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? $\endgroup$ – Dmitry Krachun Aug 19 '19 at 19:52
  • $\begingroup$ @DmitryKrachun Capitalization refers to vector of vector variables. Convolution is a vector and the Fourier transforms are not invertible here. $\endgroup$ – 1.. Aug 19 '19 at 20:57
  • $\begingroup$ Can't you just take Fourier transform component-wise? $\endgroup$ – Jochen Wengenroth Aug 20 '19 at 13:26
  • $\begingroup$ Perhaps no speed up is possible. $\endgroup$ – 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.)

  • $\begingroup$ 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. $\endgroup$ – Paul Siegel Aug 19 '19 at 20:24
  • $\begingroup$ would vector valued nonsense also admit fft? $\endgroup$ – 1.. Aug 19 '19 at 20:53
  • 1
    $\begingroup$ @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. $\endgroup$ – Paul Siegel Aug 19 '19 at 22:09
  • $\begingroup$ 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. $\endgroup$ – 1.. Aug 20 '19 at 9:24

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.