Discrete Fourier Transform Matrix
📂Fourier Analysis Discrete Fourier Transform Matrix Description The discrete Fourier transform is an adaptation of the Fourier transform for finite-dimensional vectors or digital signals. The definition of the discrete Fourier transform is as follows.
The linear transformation defined as F N : C N → C N \mathcal{F}_{N} : \mathbb{C}^{N} \to \mathbb{C}^{N} F N : C N → C N discrete Fourier transform (DFT) .
F N ( a ) = a ^ , a ^ m = ∑ n = 0 N − 1 e − i 2 π m n / N a n ( 0 ≤ m < N )
\mathcal{F}_{N}(\mathbf{a}) = \hat{\mathbf{a}},\quad \hat{a}_{m}=\sum_{n=0}^{N-1}e^{-i2\pi mn /N} a_{n}\quad (0\le m < N)
F N ( a ) = a ^ , a ^ m = n = 0 ∑ N − 1 e − i 2 πmn / N a n ( 0 ≤ m < N )
Here, a = ( a 0 , a 1 , … , a N − 1 ) \mathbf{a} = (a_{0}, a_{1}, \dots, a_{N-1}) a = ( a 0 , a 1 , … , a N − 1 ) a ^ = ( a ^ 0 , a ^ 1 , … , a ^ N − 1 ) ∈ C N \hat{\mathbf{a}} = (\hat{a}_{0}, \hat{a}_{1}, \dots, \hat{a}_{N-1}) \in \mathbb{C}^{N} a ^ = ( a ^ 0 , a ^ 1 , … , a ^ N − 1 ) ∈ C N
In other words, this transformation can be represented as a product of a matrix . Let F = [ F i j ] F = [F_{ij}] F = [ F ij ] F F F
F = [ 1 1 1 ⋯ 1 1 e − i 2 π / N e − i 4 π / N ⋯ e − i 2 ( N − 1 ) π / N 1 e − i 4 π / N e − i 8 π / N ⋯ e − i 4 ( N − 1 ) π / N ⋮ ⋮ ⋮ ⋱ ⋮ 1 e − i 2 ( N − 1 ) π / N e − i 4 ( N − 1 ) π / N ⋯ e − i 2 ( N − 1 ) ( N − 1 ) π / N ]
F = \begin{bmatrix}
1 & 1 & 1 & \cdots & 1 \\
1 & e^{-i2\pi/N} & e^{-i4\pi/N} & \cdots & e^{-i2(N-1)\pi/N} \\
1 & e^{-i4\pi/N} & e^{-i8\pi/N} & \cdots & e^{-i4(N-1)\pi/N} \\
\vdots & \vdots & \vdots & \ddots & \vdots \\
1 & e^{-i2(N-1)\pi/N} & e^{-i4(N-1)\pi/N} & \cdots & e^{-i2(N-1)(N-1)\pi/N}
\end{bmatrix}
F = 1 1 1 ⋮ 1 1 e − i 2 π / N e − i 4 π / N ⋮ e − i 2 ( N − 1 ) π / N 1 e − i 4 π / N e − i 8 π / N ⋮ e − i 4 ( N − 1 ) π / N ⋯ ⋯ ⋯ ⋱ ⋯ 1 e − i 2 ( N − 1 ) π / N e − i 4 ( N − 1 ) π / N ⋮ e − i 2 ( N − 1 ) ( N − 1 ) π / N
If ω = e − i 2 π / N \omega = e^{-i2\pi/N} ω = e − i 2 π / N
F = [ 1 1 1 ⋯ 1 1 ω ω 2 ⋯ ω N − 1 1 ω 2 ω 4 ⋯ ω 2 ( N − 1 ) ⋮ ⋮ ⋮ ⋱ ⋮ 1 ω N − 1 ω 2 ( N − 1 ) ⋯ ω ( N − 1 ) 2 ]
F = \begin{bmatrix}
1 & 1 & 1 & \cdots & 1 \\
1 & \omega & \omega^2 & \cdots & \omega^{N-1} \\
1 & \omega^2 & \omega^4 & \cdots & \omega^{2(N-1)} \\
\vdots & \vdots & \vdots & \ddots & \vdots \\
1 & \omega^{N-1} & \omega^{2(N-1)} & \cdots & \omega^{(N-1)^{2}}
\end{bmatrix}
F = 1 1 1 ⋮ 1 1 ω ω 2 ⋮ ω N − 1 1 ω 2 ω 4 ⋮ ω 2 ( N − 1 ) ⋯ ⋯ ⋯ ⋱ ⋯ 1 ω N − 1 ω 2 ( N − 1 ) ⋮ ω ( N − 1 ) 2
Therefore, the discrete Fourier transform of the N N N x \mathbf{x} x
x ^ = F x
\widehat{\mathbf{x}} = F \mathbf{x}
x = F x
The inverse transform can be achieved by simply changing the sign according to the definition. If denoted as ω ‾ = e i 2 π / N \overline{\omega} = e^{i2\pi/N} ω = e i 2 π / N
F − 1 = 1 N [ 1 1 1 ⋯ 1 1 ω ‾ ω ‾ 2 ⋯ ω ‾ N − 1 1 ω ‾ 2 ω ‾ 4 ⋯ ω ‾ 2 ( N − 1 ) ⋮ ⋮ ⋮ ⋱ ⋮ 1 ω ‾ N − 1 ω ‾ 2 ( N − 1 ) ⋯ ω ‾ ( N − 1 ) 2 ] = 1 N F ‾
F^{-1} = \dfrac{1}{N} \begin{bmatrix}
1 & 1 & 1 & \cdots & 1 \\
1 & \overline{\omega} & \overline{\omega}^2 & \cdots & \overline{\omega}^{N-1} \\
1 & \overline{\omega}^2 & \overline{\omega}^4 & \cdots & \overline{\omega}^{2(N-1)} \\
\vdots & \vdots & \vdots & \ddots & \vdots \\
1 & \overline{\omega}^{N-1} & \overline{\omega}^{2(N-1)} & \cdots & \overline{\omega}^{(N-1)^{2}}
\end{bmatrix}
= \dfrac{1}{N} \overline{F}
F − 1 = N 1 1 1 1 ⋮ 1 1 ω ω 2 ⋮ ω N − 1 1 ω 2 ω 4 ⋮ ω 2 ( N − 1 ) ⋯ ⋯ ⋯ ⋱ ⋯ 1 ω N − 1 ω 2 ( N − 1 ) ⋮ ω ( N − 1 ) 2 = N 1 F
Suppose a 2D N × N N \times N N × N X = [ x 1 x 2 ⋯ x N ] \mathbf{X} = [\mathbf{x}_{1}\quad \mathbf{x}_{2}\quad \cdots\quad \mathbf{x}_{N}] X = [ x 1 x 2 ⋯ x N ] matrix multiplication , can be expressed as follows.
F X
F \mathbf{X}
F X transpose matrix .
( F X T ) T = X F T
(F \mathbf{X}^{\mathsf{T}})^{\mathsf{T}} = \mathbf{X} F^{\mathsf{T}}
( F X T ) T = X F T X ^ = F X F T
\widehat{\mathbf{X}} = F \mathbf{X} F^{\mathsf{T}}
X = F X F T X = 1 N 2 F ‾ X ^ F ‾ T
\mathbf{X} = \dfrac{1}{N^{2}} \overline{F} \widehat{\mathbf{X}} \overline{F}^{\mathsf{T}}
X = N 2 1 F X F T
Implementation 