Fourier transform

Revision as of 18:56, 20 January 2023 by David (talk | contribs) (Created page with "The Fourier transform decomposes a signal (i.e. a time series) into multiple sine and cosine waves. ==Background== Suppose we have signal<math>f(x)</math>.<br> Then the Fourier transform <math>\hat{f}(\xi)</math>is defined as: <math display="block">\hat{f}(\xi) = \int_{-\infty}^{\infty} f(x) e^{-i2 \pi \xi x} dx</math> Recall that Euler's formula states: <math>e^{ix} = cos(x) + i \sin(x)</math>. Hence, <math>e^{-i2 \pi \xi x} = cos(2 \pi \xi x) + i \sin(2 \pi \xi x)<...")
(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)
\( \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_{0}^{n-1} f(x) \exp\ \left\{ -2 \pi i \frac{mk}{n} \right\}\] and IFFT is defined as: \[a_m = (1/n) \sum_{0}^{n-1} \hat{f}(\xi) \exp \left\{ 2 \pi i \frac{mk}{n} \right\}\]

Properties

Note \(\displaystyle \bar{x}\) refers to the complex conjugate

  • Linearity: \(\displaystyle FFT(\lambda f + g) = \lambda FFT(f) + FFT(g)\)
  • \(\displaystyle IFFT(f) = (1/n) \bar{FFT}(\bar{f})\)
  • \(\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.