이산 푸리에 변환 행렬
설명
이산 푸리에 변환discrete Fourier transform, DFT은 푸리에변환을 유한차원 벡터, 즉 디지털 신호에 적용할 수 있도록 변형한 것이다. 이산 푸리에 변환의 정의는 다음과 같다.
다음과 같이 정의되는 선형변환 $\mathcal{F}_{N} : \mathbb{C}^{N} \to \mathbb{C}^{N}$을 이산 푸리에 변환(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) $$
이때 $\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}$이다.
다시말해서 이 변환은 행렬의 곱으로 나타낼 수 있다. $F = [F_{ij}]$를 이산 푸리에 변환 행렬이라 하자. 그러면 정의에 따라서 $F$는 아래와 같다.
$$ 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} $$
이때 $\omega = e^{-i2\pi/N}$이라 나타내면,
$$ 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} $$
따라서 $N$차원 벡터 $\mathbf{x}$의 이산 푸리에 변환 $\hat{\mathbf{x}}$는 다음과 같다.
$$ \widehat{\mathbf{x}} = F \mathbf{x} $$
역변환은 정의에 따라서 부호만 바꿔주면 된다. $\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} $$
2차원 이산 푸리에 변환
2차원 $N \times N$ 행렬 $\mathbf{X} = [\mathbf{x}_{1}\quad \mathbf{x}_{2}\quad \cdots\quad \mathbf{x}_{N}]$가 주어졌다고 하자. 2차원 이산 푸리에 변환은 각각의 행과 열에 대해서 1차원 DFT를 적용하는 것이다. 각각의 열에 대해서 DFT를 적용하는 것은 행렬 곱의 정의에 의해 다음과 같다. $$ F \mathbf{X} $$ 각각의 행에 대해서 DFR를 적용하려면, 행과 열을 바꿔주면 되고 이것은 전치행렬이다. $$ (F \mathbf{X}^{\mathsf{T}})^{\mathsf{T}} = \mathbf{X} F^{\mathsf{T}} $$ 따라서 2차원 이산 푸리에 변환은 다음과 같다. $$ \widehat{\mathbf{X}} = F \mathbf{X} F^{\mathsf{T}} $$ 역변환은 다음과 같다. $$ \mathbf{X} = \dfrac{1}{N^{2}} \overline{F} \widehat{\mathbf{X}} \overline{F}^{\mathsf{T}} $$