ベクトル化した2次元データに対する離散フーリエ変換行列

機械学習では画像のような2次元のデータをベクトル化して1次元のデータとして扱うことが多い．このようにベクトル化した2次元データに対する離散フーリエ変換 (DFT) 行列を定義できれば便利である．

長さ ${N}$ のベクトル ${\mathbf{x}}$ に対する1次元の DFT は， ${\mathbf{W}_{N}}$ を ${N{\times}N}$ の DFT 行列として次の様に表せる．

$\begin{equation} \mathrm{DFT}_{1}(\mathbf{x}) = \mathbf{W}_{N}\mathbf{x} \end{equation}$

同様に ${M}$ 行 ${N}$ 列の2次元データ ${\mathbf{X}}$ に対する2次元の DFT は次の様に表せる．

$\begin{equation} \mathrm{DFT}_{2}(\mathbf{X}) = \mathbf{W}_{M}\mathbf{X}\mathbf{W}_{N} \end{equation}$

さて，2次元のデータ（行列）をベクトル化する操作を ${\mathrm{vec}(\cdot)}$ と表すと，次の関係が成り立つ．

$\begin{equation} \mathrm{vec}(\mathbf{AXB}) = \left(\mathbf{B}^{T}\otimes\mathbf{A}\right)\mathrm{vec}(\mathbf{X}) \end{equation}$

ここで ${\otimes}$ はクロネッカー積である．2番目の式とあわせて考えると，次の関係を得る*1．

$\begin{align} \mathrm{vec}(\mathrm{DFT}_{2}(\mathbf{X})) &= \mathrm{vec}(\mathbf{W}_{M}\mathbf{X}\mathbf{W}_{N})\\ &= \left(\mathbf{W}_{N}^{T}\otimes\mathbf{W}_{M}\right)\mathrm{vec}(\mathbf{X})\\ &= \left(\mathbf{W}_{N}\otimes\mathbf{W}_{M}\right)\mathrm{vec}(\mathbf{X})\\ \end{align}$

というわけで，ベクトル化した2次元データに対する DFT 行列は ${\mathbf{W}_{N}\otimes\mathbf{W}_{M}}$ で定義できることが分かる．ちなみに ${\mathbf{X}}$ を ${128{\times}128}$ ，DFT 行列の要素を std::complex< double > とすると，この DFT 行列は 4 GB のメモリを必要とする．

*1:DFT 行列の性質 ${\mathbf{W}^T=\mathbf{W}}$ に注意．