3
$\begingroup$

As you probably know, the discrete convolution $ H = F \ast G $ of some $ F \left[ x \right] $ and some $ G \left[ x \right] $ can be calculated using the Fast Fourier Transform (FFT).

To do this, one would ...

  1. Set $ M $ to the length of the sequence $ F $ and $ L $ to the length of the sequence $ G $.

  2. Choose an $ N = 2^n $ with $ n \in \mathbb{N} $ such that $ N \ge \left(M + L \right) - 1 $.

  3. Extend both sequences $ F $ and $ G $ to a length of $ N $ by appending zeroes (on the "right"). (This is necessary to prevent time-domain aliasing from occuring due to the fact that we perform circular convolution instead of linear convolution.)

  4. Calculate $ \hat{F} = FFT \left( F \right), \hat{G} = FFT \left( G \right) $.

  5. Calculate $ \hat{H} = \hat{F} \odot \hat{G} $, where $ \odot $ is the Hadamard operator.

  6. Calculate $ H = FFT^{-1} \left( \hat{H} \right) $.

Now, the thing is that there are different variants of the DFT (and therefore FFT) and they differ from each other regarding their scaling factors.

The "standard" version is as follows.

DFT: $$ X_{k} = \sum_{n = 0}^{N - 1} x_{n} \cdot e^{\frac{-i \cdot 2 \cdot \pi \cdot k \cdot n}{N}} $$

IDFT: $$ x_{n} = \frac{1}{N} \cdot \sum_{k = 0}^{N - 1} X_{k} \cdot e^{\frac{i \cdot 2 \cdot \pi \cdot k \cdot n}{N}} $$

However, there is also an "orthonormal" version of the transforms.

DFT: $$ X_{k} = \frac{1}{\sqrt{N}} \cdot \sum_{n = 0}^{N - 1} x_{n} \cdot e^{\frac{-i \cdot 2 \cdot \pi \cdot k \cdot n}{N}} $$

IDFT: $$ x_{n} = \frac{1}{\sqrt{N}} \cdot \sum_{k = 0}^{N - 1} X_{k} \cdot e^{\frac{i \cdot 2 \cdot \pi \cdot k \cdot n}{N}} $$

And, as far as I know, in principle, one could in fact use any scaling factors to transform back and forth between time and frequency domain, as long as the product of both is $ \frac{1}{N} $.

As long as you only do one transform, then perform linear manipulations in the frequency domain, then do an inverse transform, it does not really matter, which way you scale the transforms, however, when we calculate the convolution of two vectors by taking the DFT/FFT of both, multiplying them, and then taking the inverse transform, the scaling seems to matter.

  1. When using the "standard" transforms, both $ F $ and $ G $ get scaled by $ 1 $ (not scaled at all) on the "forward" transform, then multiplied, then get scaled by $ \frac{1}{N} $ on the inverse transform. Thus, in total, you have one scaling by multiplication with $ \frac{1}{N} $.

  2. When using the "orthonormal" transforms, both $ F $ and $ G $ get scaled by $ \frac{1}{\sqrt{N}} $. Then the transformed functions are multiplied, so that the product of the two effectively got scaled by $ \frac{1}{N} $. Then, on the inverse transform, they get scaled by $ \frac{1}{\sqrt{N}} $ again, so that in total, you got a scaling of $ \frac{1}{N \cdot \sqrt{N}} = N^{\frac{-3}{2}} \neq \frac{1}{N} $ so that the result will be different from that obtained using the "standard" transform.

Also note that, either way, we always scale by $ N $ (or some - possibly fractional - power of $ N $), which is neither (a power of) the length of the sequence $ F $ (which is $ M $), nor (a power of) the length of the sequence $ G $ (which is $ L $) but something rather unrelated to it. In the end, we chose $ N $ so that it fits our algorithm. Most FFT algorithms require the vectors to have a size which is a power of two, so we chose one. I'm not sure if (and how) one would have to compensate for that.

Summary: How should I scale the FFTs (or apply additional scaling before/afterwards to compensate) so that $ FFT^{-1} \left( FFT \left( F \right) \odot FFT \left( G \right) \right) \stackrel{!}{=} F \ast G $?

$\endgroup$
2
$\begingroup$

this formula $FFT^{-1} \left( FFT \left( F \right) \odot FFT \left( G \right) \right) \stackrel{!}{=} F \ast G$ is not always true, it's true when you scale at the inverse operation as you mentioned in your first case, in second case you have to multiply the right side by $\sqrt{N}$ to make it right.

Generally when you apply the Fourier transform over the convolution you see any scaling would be used for the first signal and no scaling remain for the second signal so if you multiply and divide by the scaling and use the scaling in the denominator for standard Fourier transform, the scaling remain in the nominator.

$\endgroup$

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.