이산 푸리에 변환 행렬
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 $\mathcal{F}_{N} : \mathbb{C}^{N} \to \mathbb{C}^{N}$ is called the discrete Fourier transform (DFT).
$$ \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) $$
Here, $\mathbf{a} = (a_{0}, a_{1}, \dots, a_{N-1})$, $\hat{\mathbf{a}} = (\hat{a}_{0}, \hat{a}_{1}, \dots, \hat{a}_{N-1}) \in \mathbb{C}^{N}$ hold.
In other words, this transformation can be represented as a product of a matrix. Let $F = [F_{ij}]$ be the discrete Fourier transform matrix. Then, according to the definition, $F$ is represented as follows.
$$ 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} $$
If $\omega = e^{-i2\pi/N}$ is denoted as follows,
$$ 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} $$
Therefore, the discrete Fourier transform of the $N$-dimensional vector $\mathbf{x}$ is as follows:
$$ \widehat{\mathbf{x}} = F \mathbf{x} $$
The inverse transform can be achieved by simply changing the sign according to the definition. If denoted as $\overline{\omega} = e^{i2\pi/N}$,
$$ 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} $$
2D Discrete Fourier Transform
Suppose a 2D $N \times N$ matrix $\mathbf{X} = [\mathbf{x}_{1}\quad \mathbf{x}_{2}\quad \cdots\quad \mathbf{x}_{N}]$ is given. The 2D discrete Fourier transform involves applying a 1D DFT to each row and column. Applying DFT to each column, by the definition of matrix multiplication, can be expressed as follows. $$ F \mathbf{X} $$ To apply the DFT to each row, transpose the rows and columns, which corresponds to a transpose matrix. $$ (F \mathbf{X}^{\mathsf{T}})^{\mathsf{T}} = \mathbf{X} F^{\mathsf{T}} $$ Therefore, the 2D discrete Fourier transform is as follows: $$ \widehat{\mathbf{X}} = F \mathbf{X} F^{\mathsf{T}} $$ The inverse transform is as follows: $$ \mathbf{X} = \dfrac{1}{N^{2}} \overline{F} \widehat{\mathbf{X}} \overline{F}^{\mathsf{T}} $$