Quick Intro to FFT

Image credit: Daniel Sierra

Quick Intro to FFT

Amir Gholami bio photo By Amir Gholami

Preface

Fourier transform is a method for decomposing a function into a series of sines and cosines. In the first place, why would you be interested in decomposition a function into something else? The short answer is that sometimes it is easier to analyze the function when it is decomposed. For example, consider a signal with a heavy noise in high frequencies. Using the fourier basis functions, one can simply denoise the signal and retrieve the desired information. Fourier transform is just one of many such mathematical transforms.

Some Math

The Fourier transform of a discrete signal, which is periodic in , is found by computing the following sum for each frequency:

$$ \widehat{f}(k)=\frac{2\pi}{N}\sum_{j=0}^{N-1}f(x_j)e^{-ikx_j} $$
$$ k=\frac{-N}{2}+1, \cdots,\frac{N}{2} $$

and correspondingly, the inverse discrete fourier transform:

$$ f(x)=\frac{1}{2\pi}\sum_{k=-N/2+1}^{N/2}\widehat{f}(k)e^{ikx} $$

To compute Fourier transform of a function in dimensions, one should compute the above sum times for each direction. For instance, to compute Fourier transform of a 3D array, you need to compute the sum three times in x,y, and z dimensions.

Now where does FFT come into picture? FFT or Fast Fourier Transform is an algorithm to speedup computing this sum. As you can see, for each frequency , you need to perform multiplication and summation. Since there is such frequencies, the computaional complexity of finding the Fourier transform would be . This is a prohibitively large cost.

Now back in 1965 Cooley and Turkey were tasked by IBM to find a way to reduce this cost. They developed the famous Cooley-Turkey algorithm which was later named the Fast Fourier Transform algorithm. FFT is one of the top ten numerical algorithms of the last century. This elegant algorithm reduces the computational complexity down to , which is a huge saving. This achievement paved the way for growth of spectral methods in different fields.

Fast Fourier Transform algorithm is one of the top ten algorithms of the last century.

Scaling Confusion

At least for me, there was a big confusion about where the scaling is performed in FFT. As you can see in the forward FFT formula, there is a factor of in front of the sum. However, if you compute FFT of using most of the libraries, there will be no scaling. Same thing is true for the inverse FFT. This means that the following difference would not be zero in most FFT libraries:

$$ \mathcal{F}^{-1}(\mathcal{F}(f)) -f \neq 0 $$

Here is the forward FFT operator and is its inverse. You need to perform the scaling manually yourself:

$$ \frac{1}{N}\mathcal{F}^{-1}(\mathcal{F}(f)) -f = 0 $$

To adhere to the standard, AccFFT does not perform the scaling either.

Exception! The only exception to this rule is the matlab FFT routine. Similar to other libraries, Matlab does not perform the scaling of the forward FFT. However it does the scaling when you compute IFFT! So the above difference will be zero without additional scaling on the user side.