Fourier transform

From David's Wiki
\( \newcommand{\P}[]{\unicode{xB6}} \newcommand{\AA}[]{\unicode{x212B}} \newcommand{\empty}[]{\emptyset} \newcommand{\O}[]{\emptyset} \newcommand{\Alpha}[]{Α} \newcommand{\Beta}[]{Β} \newcommand{\Epsilon}[]{Ε} \newcommand{\Iota}[]{Ι} \newcommand{\Kappa}[]{Κ} \newcommand{\Rho}[]{Ρ} \newcommand{\Tau}[]{Τ} \newcommand{\Zeta}[]{Ζ} \newcommand{\Mu}[]{\unicode{x039C}} \newcommand{\Chi}[]{Χ} \newcommand{\Eta}[]{\unicode{x0397}} \newcommand{\Nu}[]{\unicode{x039D}} \newcommand{\Omicron}[]{\unicode{x039F}} \DeclareMathOperator{\sgn}{sgn} \def\oiint{\mathop{\vcenter{\mathchoice{\huge\unicode{x222F}\,}{\unicode{x222F}}{\unicode{x222F}}{\unicode{x222F}}}\,}\nolimits} \def\oiiint{\mathop{\vcenter{\mathchoice{\huge\unicode{x2230}\,}{\unicode{x2230}}{\unicode{x2230}}{\unicode{x2230}}}\,}\nolimits} \)

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)))[1].

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) \bar{FFT}(\bar{f})\)

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

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.

References

  1. Siembida, A. (2010, March 11). How to compute the IFFT using only the forward FFT. Adam Siembida Personal Webpage. Retrieved January 24, 2023, from https://adamsiembida.com/how-to-compute-the-ifft-using-only-the-forward-fft/