3
$\begingroup$

Let $a,b,c,d\in\mathbb{R}^n$. Is it possible to compute $$\langle a*b,c*d\rangle$$ faster than 6 FFTs?

I can do it with 6 FFTs by doing normal convolutions, 3 FFTs each.

In my application I know $b, d$ upfront and can do preprocessing, so the cost is actually 4 FFTs. Can I do better than this?

The reason I believe that this might be possible is because FFTs are unitary, so maybe there's a way to omit the inverse FFTs in the convolutions.

[EDIT] where convolution is defined by: $$(a*b)_i=\sum_{j=1}^i a_jb_{n+j-i}$$

$\endgroup$
  • $\begingroup$ You can get the acylic convolution by means of zero padding before doing an FFT based circular convolution. $\endgroup$ – Brian Borchers Aug 30 '16 at 23:25
  • $\begingroup$ @Brian: Right, that's how I solve the problem with 6(/4) FFTs. I don't see how to stay in the frequency domain if I zero padded the vectors. $\endgroup$ – Dror Speiser Aug 31 '16 at 5:44
  • $\begingroup$ I think the indexing in the sum above is wrong. The sum must run to some maximum size, not to the index $i$ that also appears on the right. $\endgroup$ – Wolfgang Bangerth Sep 5 '16 at 21:11
  • $\begingroup$ @Wolfgang Bangerth: the indexing is the right one. Think of the convolution with $b$ as a filter on a stream: at time $i$ we only know the first $i$ coordinates of $a$, so $b$ multiplies only with them. For example taking $b$ to be the vector $(0,...,0,B)$, convolution (in the above sense) multiplies vectors by B. $\endgroup$ – Dror Speiser Sep 6 '16 at 5:47
  • $\begingroup$ But it doesn't match the definition on the wikipedia page you linked to from my answer in a comment. There, the sum always has the same number of terms, independent of the index $i$ of the result vector. $\endgroup$ – Wolfgang Bangerth Sep 6 '16 at 21:41
2
$\begingroup$

Parseval's theorem tells you that the dot product between two vectors equals the dot product of the Fourier transforms, possibly up to a constant. Consequently, you do not need to transform back the result of $a\ast b$ and $c \ast d$ and should be able to do the overall operation with just 4 FFTs.

$\endgroup$
  • $\begingroup$ Is it 4 or 5? In continuous arithmetic the analogous result with the convolution theorem still requires that the product of the inverse transforms be itself transformed back. $\endgroup$ – origimbo Aug 30 '16 at 15:50
  • $\begingroup$ I've edited my question to include that my convolutions are linear (acyclic). Is it still possible to use Parseval's theorem? $\endgroup$ – Dror Speiser Aug 30 '16 at 15:58
  • $\begingroup$ I don't know about the acyclic convolution. It's the first time I hear about it. As for having to transform it back -- the result of the product $\left<a \ast b, c \ast d\right>$ is a scalar number. There is nothing to transform. $\endgroup$ – Wolfgang Bangerth Aug 31 '16 at 0:14
  • $\begingroup$ The most famous example of acylic convolution usage is in polynomial multiplication. en.wikipedia.org/wiki/… $\endgroup$ – Dror Speiser Aug 31 '16 at 5:50

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.