Background
From a mathematical point of view, the formulas similar to the following were produced:
- $F_1(f) = \mathcal{F}(T(t))$
- $F_2(f) = \mathcal{F}(T(t)\times sin\Theta t)$
- $F_3(f) = \mathcal{F}(T(t)\times(A+B\times sin\Theta t))$
- $F_4(f) = \mathcal{F}(T(t)\times(A\times sin\Theta t+B\times cos\Phi t))$
- $F_5(f) = \mathcal{F}(T(t)+T_2(t))$
As a programmer, this looks like sheer horror since I don't want to do 5 FFTs. Performance-wise, it just burns computation time since it is done in a large loop and to me it looks like I can easily relate one $F$ to the others.
I understand that for a well-practiced mathematician these are actually quite trivial FFTs, but my personal knowledge is quite rusty on the subject.
Question: Can I relate these $F$ to each other?
I looked into the theory and from what I understand, $F_2(f) = \mathcal{F}(T(t)\times sin\Theta t) = \mathcal{F}(T(t))\ast\mathcal{F}(sin\Theta t) = F_1(f)\ast\mathcal{F}(sin\Theta t)$ with $\ast$ being the convolution operator.
Since I don't need an FFT to compute $\mathcal{F}(sin\Theta t) = 0.5i\times(\delta(f+\Theta/2\pi)-\delta(f-\Theta/2\pi))$, I can simply do the convolution of my previous $F_1$ and this dirac directly, avoiding an FFT. I found that this convolution with a dirac is apparently very trivial to compute in a single step of $O(n)$, but I can't figure out the exact result due to there being two diracs with a shift and my brain not being able to handle it.
Ideally, I would like to find similar formulas for $F_3$, $F_4$ and $F_5$ as well in order to speed up my implementation significantly. There are about a dozen of variations on these FFTs provided by the original researchers which look to me like they could be done in 2 FFTs and a few $O(n)$ operations instead.
Equivalent, but so much faster...
I found the solution for $F_2$. So starting from the convolution for $F_2$ we have: $F_2(f) = F_1(f)\ast(0.5i\times(\delta(f+\Theta/2\pi)-\delta(f-\Theta/2\pi)))$
The formula for a convolution is (in the discrete case) $F_2(f) = 0.5i\times\sum_j{F_1(f-j)\times\delta(j+\Theta/2\pi)-\delta(j-\Theta/2\pi))}$
Finding that $\delta(j+\Theta/2\pi) > 0$ if and only if $j = -\Theta/2\pi$, we know the sum collapses to a simple $F_2(f) = 0.5i\times(F_1(f-\Theta/2\pi)-F_1(f+\Theta/2\pi))$.
A lot more comes to mind when you are working on an array (instead of a continuous function) but purely mathematically this works out. The FFT is replaced by a simple addition and multiplication.
I think the rest can be similarly simplified by using the distributive property of convolution.