View source for Fourier transform

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)</math>
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:
<math display="block">f(x) = \int_{-\infty}^{\infty} \hat{f}(\xi) e^{i2 \pi \xi x} d\xi</math>

===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.

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

That the main difference between the FFT and IFFT is the negative symbol in the exponent.
You can implement IFFT as <code>IFFT(x) = (1/len(x))*conj(FFT(conj(x)))</code><ref name="siembida2010ifft"></ref>.

==Properties==
Note <math>\bar{x}</math> refers to the complex conjugate
Let <math>F(s) = FFT(f(s))</math>.

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

'''Shift'''<br>
<math>FFT(f(x-a)) = e^{-i \omega_k a} F(\omega_k)</math>
* Note <math>\omega_k = 2 \pi k/N </math>

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

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

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

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

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

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

This is a case of the convolution theorem.

'''IFFT'''<br>
<math>IFFT(f) = (1/n) FFT^*(f^*)</math>
* Where <math>^*</math> is the conjugate.

'''2D FFT'''<br>
<math>FFT2(f) = FFT_{x}(FFT_{y}(f)) = FFT_{y}(FFT_{x}(f))</math>

==Phase correlation==
{{main | Wikipedia: Phase correlation}}

==Short-time Fourier transform==
{{main | Wikipedia: Short-time Fourier transform}}
The STFT applies FFT using a sliding window over the signal.<br>
This produces a matrix of FFT values over time which allow you to see how the signal is changing.

==References==
{{reflist|refs=
<ref name="siembida2010ifft">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/ </ref>
}}