Fourier transform: Difference between revisions

===Discrete Fourier Transform===

A naive DFT would compute the matrix of <math>e^{-i2 \pi \xi x}</math> and multiply it with the signal. This would take <math>\mathcal{O}(n^2)</math> time.<br>

However, most languages have an FFT library which can compute the DFT in <math>\mathcal{O}(n \log n)</math> time.

Let <math>F(s) = FFT(f(s))</math>.

<math>FFT(\lambda f + g) = \lambda FFT(f) + FFT(g)</math>

<math>FFT(f(x-a)) = e^{-i \omega_k a} F(\omega_k)</math>

* Note <math>\omega_k = 2 \pi k/N </math>

<math>FFT(f(ax)) = |a|^{-1} F(s/a)</math>

<math>f *g  \Leftrightarrow F(s) \times G(s)</math><br>

<math>f \times g \Leftrightarrow F(s) * G(s)</math>

<math>\int |f(x)|^2 dx = \int |F(s)|^2 ds</math>

See [[Wikipedia: Parseval's theorem]]<br>

<math>\int f(x) g^*(x) dx = \int F(s) G^*(s) ds</math>

<math>\int f(x') f^*(x' - x) dx' \Leftrightarrow |F(x)|^2</math>

This is a case of the convolution theorem.

<math>FFT2(f) = FFT_{x}(FFT_{y}(f)) = FFT_{y}(FFT_{x}(f))</math>

==Short-time Fourier transform==