Fourier transform: Difference between revisions

(8 intermediate revisions by the same user not shown)

Line 16:

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

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

Line 24:

Line 25:

<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 ~~different~~ between the FFT and IFFT is the negative symbol in the exponent.

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: <math>FFT(\lambda f + g) = \lambda FFT(f) + FFT(g)</math>

'''Linearity'''

* <math>IFFT(f) = (1/n) ~~\bar{~~FFT}(~~\bar{~~f})</math>

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

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

'''Shift'''

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

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

'''Similarity'''

'''Convolution Theorem'''

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

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

'''Parseval's Theorem'''

See [[Wikipedia: Parseval's theorem]]

More generally,

'''Autocorrelation'''

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

This is a case of the convolution theorem.

'''IFFT'''

* Where <math>^*</math> is the conjugate.

'''2D FFT'''

==Phase correlation==

==Short-time Fourier transform==

@@ Line 16: / Line 16: @@
 ===Discrete Fourier Transform===
+{{Main | Wikipedia: 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.
@@ Line 24: / Line 25: @@
 <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 different between the FFT and IFFT is the negative symbol in the exponent.
+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: <math>FFT(\lambda f + g) = \lambda FFT(f) + FFT(g)</math>
+'''Linearity'''<br>
-* <math>IFFT(f) = (1/n) \bar{FFT}(\bar{f})</math>
+<math>FFT(\lambda f + g) = \lambda FFT(f) + FFT(g)</math>
-* <math>FFT2(f) = FFT_{x}(FFT_{y}(f)) = FFT_{y}(FFT_{x}(f))</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==