이산 푸리에 변환 행렬
説明
離散フーリエ変換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} $$ それぞれの行に対してDFTを適用するには、行と列を入れ替えればよく、これは転置行列である。 $$ (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}} $$