3
$\begingroup$

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?

Improve this question
$\endgroup$
4
  • 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
    Commented Aug 19, 2019 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$
    – Turbo
    Commented Aug 19, 2019 at 20:57
  • $\begingroup$ Can't you just take Fourier transform component-wise? $\endgroup$
    – Jochen Wengenroth
    Commented Aug 20, 2019 at 13:26
  • $\begingroup$ Perhaps no speed up is possible. $\endgroup$
    – Turbo
    Commented Aug 21, 2019 at 8:45

1 Answer 1

Reset to default
2
$\begingroup$

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

Improve this answer
$\endgroup$
4
  • $\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
    Commented Aug 19, 2019 at 20:24
  • $\begingroup$ would vector valued nonsense also admit fft? $\endgroup$
    – Turbo
    Commented Aug 19, 2019 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
    Commented Aug 19, 2019 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$
    – Turbo
    Commented Aug 20, 2019 at 9:24

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .