Fourier transform

The Fourier transform decomposes a signal (i.e. a time series) into multiple sine and cosine waves.

Background

Suppose we have signal\(\displaystyle f(x)\).
Then the Fourier transform \(\displaystyle \hat{f}(\xi)\)is defined as: \[\hat{f}(\xi) = \int_{-\infty}^{\infty} f(x) e^{-i2 \pi \xi x} dx\]

Recall that Euler's formula states: \(\displaystyle e^{ix} = cos(x) + i \sin(x)\). Hence, \(\displaystyle e^{-i2 \pi \xi x} = cos(-2 \pi \xi x) + i \sin(-2 \pi \xi x)\) In other words, the Fourier transform is the integral (i.e. alignment) of signal times some sine and cosine waves.

The inverse of the fourier transform is: \[f(x) = \int_{-\infty}^{\infty} \hat{f}(\xi) e^{i2 \pi \xi x} d\xi\]

Discrete Fourier Transform

A naive DFT would compute the matrix of \(\displaystyle e^{-i2 \pi \xi x}\) and multiply it with the signal. This would take \(\displaystyle \mathcal{O}(n^2)\) time.
However, most languages have an FFT library which can compute the DFT in \(\displaystyle \mathcal{O}(n \log n)\) time.

In most languages, FFT is defined as: \[A_k = \sum_{m=0}^{n-1} f(x) \exp\ \left\{ -2 \pi i \frac{mk}{n} \right\}\] and IFFT is defined as: \[a_m = \frac{1}{n} \sum_{k=0}^{n-1} \hat{f}(\xi) \exp \left\{ 2 \pi i \frac{mk}{n} \right\}\]

That the main difference between the FFT and IFFT is the negative symbol in the exponent. You can implement IFFT as IFFT(x) = (1/len(x))*conj(FFT(conj(x))).

Properties

Note \(\displaystyle \bar{x}\) refers to the complex conjugate Let \(\displaystyle F(s) = FFT(f(s))\).

Linearity
\(\displaystyle FFT(\lambda f + g) = \lambda FFT(f) + FFT(g)\)

Shift
\(\displaystyle FFT(f(x-a)) = e^{-i \omega_k a} F(\omega_k)\)

• Note \(\displaystyle \omega_k = 2 \pi k/N \)

Similarity
\(\displaystyle FFT(f(ax)) = |a|^{-1} F(s/a)\)

Convolution Theorem
\(\displaystyle f *g \Leftrightarrow F(s) \times G(s)\)
\(\displaystyle f \times g \Leftrightarrow F(s) * G(s)\)

Parseval's Theorem
\(\displaystyle \int |f(x)|^2 dx = \int |F(s)|^2 ds\)

See Wikipedia: Parseval's theorem

More generally, \(\displaystyle \int f(x) g^*(x) dx = \int F(s) G^*(s) ds\)

Autocorrelation
\(\displaystyle \int f(x') f^*(x' - x) dx' \Leftrightarrow |F(x)|^2\)

This is a case of the convolution theorem.

IFFT
\(\displaystyle IFFT(f) = (1/n) FFT^*(f^*)\)

• Where \(\displaystyle ^*\) is the conjugate.

2D FFT
\(\displaystyle FFT2(f) = FFT_{x}(FFT_{y}(f)) = FFT_{y}(FFT_{x}(f))\)

Phase correlation

Main article: Wikipedia: Phase correlation

Short-time Fourier transform

Main article: Wikipedia: Short-time Fourier transform

The STFT applies FFT using a sliding window over the signal.
This produces a matrix of FFT values over time which allow you to see how the signal is changing.