高速フーリエ変換（FFT）- 理論編
参考
FFT とは
DFT との違い
前章の DFT で理解した公式、
$$ \begin{align*} \text{DFT:}\quad &F = \sum_{k=0}^{N-1}X[k]~ e^{-2i\pi k\frac{n}{N}}\\[5pt] \text{IDFT:}\quad &X = \frac{1}{N}\sum_{n=0}^{N-1} F[n]~ e^{2i\pi k\frac{n}{N}} \end{align*} $$
では、変数 $n,k$ に対してそれぞれ操作を行うため、計算量は $O(N^2)$ となってしまう。
これを、非常に巧妙なやり方で $O(N\log N)$ にまで落とすのが FFT である。
準備
回転因子
回転因子 $W_N$ を次のように定義する。
$$ \begin{align*} W_N = e^{-i\frac{2\pi}{N}} \end{align*} $$
これは、複素数平面上の点 $1$ を原点 $O$ を中心に $2\pi/N$ だけ回転させたものと考えられる。
また、DFT のときに用いた行列 $W$ （文字が混ざってややこしい）の成分 $W_{k,n}$ を $W_N^{kn}$ と表すことができる。
※$e$の方に乗っける部分の正負を逆転させたため、DFT の時とは $W$ の中身の符号が逆になっちゃってます。
回転因子の周期性
複素数平面上での回転を考えると、
$$ \begin{align*} W_N^k = W_N^{k~\text{mod}N} \end{align*} $$
回転因子の対称性
$N$ が偶数のとき、複素数平面上での位置関係から、
$$ \begin{align*} -W_N^k = W_N^{k~\text{mod}N/2} \end{align*} $$
DFT の回転因子を用いた表記
$N=8$ の DFT を考える。入力ベクトル $x$ を出力ベクトル $X$ に変換する操作は以下のように表すことができる。
$$ \begin{align*} \left( \begin{array}{c} X_0 \\ X_1 \\ X_3 \\ X_4 \\ X_5 \\ X_6 \\ X_7 \end{array} \right) = \left( \begin{array}{cccccccc} W_8^{0} & W_8^{0} & W_8^{0} & W_8^{0} & W_8^{0} & W_8^{0} & W_8^{0} & W_8^{0}\\ W_8^{0} & W_8^{1} & W_8^{2} & W_8^{3} & W_8^{4} & W_8^{5} & W_8^{6} & W_8^{7}\\ W_8^{0} & W_8^{2} & W_8^{4} & W_8^{6} & W_8^{8} & W_8^{10} & W_8^{12} & W_8^{14}\\ W_8^{0} & W_8^{3} & W_8^{6} & W_8^{9} & W_8^{12} & W_8^{15} & W_8^{18} & W_8^{21}\\ W_8^{0} & W_8^{4} & W_8^{8} & W_8^{12} & W_8^{16} & W_8^{20} & W_8^{24} & W_8^{28}\\ W_8^{0} & W_8^{5} & W_8^{10} & W_8^{15} & W_8^{20} & W_8^{25} & W_8^{30} & W_8^{35}\\ W_8^{0} & W_8^{6} & W_8^{12} & W_8^{18} & W_8^{24} & W_8^{30} & W_8^{36} & W_8^{42}\\ W_8^{0} & W_8^{7} & W_8^{14} & W_8^{21} & W_8^{28} & W_8^{35} & W_8^{42} & W_8^{49}\\ \end{array} \right) \left( \begin{array}{c} x_0 \\ x_1 \\ x_2 \\ x_3 \\ x_4 \\ x_5 \\ x_6 \\ x_7 \end{array} \right) \end{align*} $$
ここで、回転因子の周期性を用いると、
上の式はこのように変形される。
$$ \begin{align*} \left( \begin{array}{c} X_0 \\ X_1 \\ X_3 \\ X_4 \\ X_5 \\ X_6 \\ X_7 \end{array} \right) = \left( \begin{array}{cccccccc} W_8^{0} & W_8^{0} & W_8^{0} & W_8^{0} & W_8^{0} & W_8^{0} & W_8^{0} & W_8^{0}\\ W_8^{0} & W_8^{1} & W_8^{2} & W_8^{3} & W_8^{4} & W_8^{5} & W_8^{6} & W_8^{7}\\ W_8^{0} & W_8^{2} & W_8^{4} & W_8^{6} & W_8^{0} & W_8^{2} & W_8^{4} & W_8^{6}\\ W_8^{0} & W_8^{3} & W_8^{6} & W_8^{1} & W_8^{4} & W_8^{7} & W_8^{2} & W_8^{5}\\ W_8^{0} & W_8^{4} & W_8^{0} & W_8^{4} & W_8^{0} & W_8^{4} & W_8^{0} & W_8^{4}\\ W_8^{0} & W_8^{5} & W_8^{2} & W_8^{7} & W_8^{4} & W_8^{1} & W_8^{6} & W_8^{3}\\ W_8^{0} & W_8^{6} & W_8^{4} & W_8^{2} & W_8^{0} & W_8^{6} & W_8^{4} & W_8^{2}\\ W_8^{0} & W_8^{7} & W_8^{6} & W_8^{5} & W_8^{4} & W_8^{3} & W_8^{2} & W_8^{1}\\ \end{array} \right) \left( \begin{array}{c} x_0 \\ x_1 \\ x_2 \\ x_3 \\ x_4 \\ x_5 \\ x_6 \\ x_7 \end{array} \right) \end{align*} $$
高速フーリエ変換の導出
前準備で作った行列が持つ性質をうまく利用して、計算量を落としていく。具体的には、奇数行と偶数行に分けて計算していく。
奇数行
$$ \begin{align*} \left( \begin{array}{c} X_0 \\ X_2 \\ X_4 \\ X_6 \end{array} \right) &= \left( \begin{array}{cccccccc} W_8^{0} & W_8^{0} & W_8^{0} & W_8^{0} & W_8^{0} & W_8^{0} & W_8^{0} & W_8^{0}\\ W_8^{0} & W_8^{2} & W_8^{4} & W_8^{6} & W_8^{0} & W_8^{2} & W_8^{4} & W_8^{6}\\ W_8^{0} & W_8^{4} & W_8^{0} & W_8^{4} & W_8^{0} & W_8^{4} & W_8^{0} & W_8^{4}\\ W_8^{0} & W_8^{6} & W_8^{4} & W_8^{2} & W_8^{0} & W_8^{6} & W_8^{4} & W_8^{2}\\ \end{array} \right) \left( \begin{array}{c} x_0 \\ x_1 \\ x_2 \\ x_3 \\ x_4 \\ x_5 \\ x_6 \\ x_7 \end{array} \right)\\[5pt] &= \left( \begin{array}{cccc|cccc} W_8^{0} & W_8^{0} & W_8^{0} & W_8^{0} & W_8^{0} & W_8^{0} & W_8^{0} & W_8^{0}\\ W_8^{0} & W_8^{2} & W_8^{4} & W_8^{6} & W_8^{0} & W_8^{2} & W_8^{4} & W_8^{6}\\ W_8^{0} & W_8^{4} & W_8^{0} & W_8^{4} & W_8^{0} & W_8^{4} & W_8^{0} & W_8^{4}\\ W_8^{0} & W_8^{6} & W_8^{4} & W_8^{2} & W_8^{0} & W_8^{6} & W_8^{4} & W_8^{2}\\ \end{array} \right) \left( \begin{array}{c} x_0 \\ x_1 \\ x_2 \\ x_3 \\ x_4 \\ x_5 \\ x_6 \\ x_7 \end{array} \right) \end{align*} $$
縦線で区切ったときの左右が全く同じ値になっていることがわかる。したがって、
$$ \begin{align*} \left( \begin{array}{c} X_0 \\ X_2 \\ X_4 \\ X_6 \end{array} \right) &= \left( \begin{array}{cccc} W_8^{0} & W_8^{0} & W_8^{0} & W_8^{0}\\ W_8^{0} & W_8^{2} & W_8^{4} & W_8^{6}\\ W_8^{0} & W_8^{4} & W_8^{0} & W_8^{4}\\ W_8^{0} & W_8^{6} & W_8^{4} & W_8^{2}\\ \end{array} \right) \left( \begin{array}{c} x_0 + x_4 \\ x_1 + x_5 \\ x_2 + x_6 \\ x_3 + x_7 \end{array} \right) \end{align*} $$
と変形できる。
偶数行
$$ \begin{align*} \left( \begin{array}{c} X_1 \\ X_3 \\ X_5 \\ X_7 \end{array} \right) &= \left( \begin{array}{cccccccc} W_8^{0} & W_8^{1} & W_8^{2} & W_8^{3} & W_8^{4} & W_8^{5} & W_8^{6} & W_8^{7}\\ W_8^{0} & W_8^{3} & W_8^{6} & W_8^{1} & W_8^{4} & W_8^{7} & W_8^{2} & W_8^{5}\\ W_8^{0} & W_8^{5} & W_8^{2} & W_8^{7} & W_8^{4} & W_8^{1} & W_8^{6} & W_8^{3}\\ W_8^{0} & W_8^{7} & W_8^{6} & W_8^{5} & W_8^{4} & W_8^{3} & W_8^{2} & W_8^{1}\\ \end{array} \right) \left( \begin{array}{c} x_0 \\ x_1 \\ x_2 \\ x_3 \\ x_4 \\ x_5 \\ x_6 \\ x_7 \end{array} \right) \end{align*} $$
これを回転因子の対称性を用いて変形すると、
$$ \begin{align*} \left( \begin{array}{c} X_1 \\ X_3 \\ X_5 \\ X_7 \end{array} \right) &= \left( \begin{array}{cccccccc} W_8^{0} & W_8^{1} & W_8^{2} & W_8^{3} & -W_8^{0} & -W_8^{1} & -W_8^{2} & -W_8^{3}\\ W_8^{0} & W_8^{3} & -W_8^{2} & W_8^{1} & -W_8^{0} & -W_8^{3} & W_8^{2} & -W_8^{1}\\ W_8^{0} & -W_8^{1} & W_8^{2} & -W_8^{3} & -W_8^{0} & W_8^{1} & -W_8^{2} & W_8^{3}\\ W_8^{0} & -W_8^{3} & -W_8^{2} & -W_8^{1} & -W_8^{0} & W_8^{3} & W_8^{2} & W_8^{1}\\ \end{array} \right) \left( \begin{array}{c} x_0 \\ x_1 \\ x_2 \\ x_3 \\ x_4 \\ x_5 \\ x_6 \\ x_7 \end{array} \right)\\[5pt] &= \left( \begin{array}{cccc|cccc} W_8^{0} & W_8^{1} & W_8^{2} & W_8^{3} & -W_8^{0} & -W_8^{1} & -W_8^{2} & -W_8^{3}\\ W_8^{0} & W_8^{3} & -W_8^{2} & W_8^{1} & -W_8^{0} & -W_8^{3} & W_8^{2} & -W_8^{1}\\ W_8^{0} & -W_8^{1} & W_8^{2} & -W_8^{3} & -W_8^{0} & W_8^{1} & -W_8^{2} & W_8^{3}\\ W_8^{0} & -W_8^{3} & -W_8^{2} & -W_8^{1} & -W_8^{0} & W_8^{3} & W_8^{2} & W_8^{1}\\ \end{array} \right) \left( \begin{array}{c} x_0 \\ x_1 \\ x_2 \\ x_3 \\ x_4 \\ x_5 \\ x_6 \\ x_7 \end{array} \right) \end{align*} $$
ここで、縦線で区切った左右が $-1$ をかけると等しくなる性質を持っていることがわかる。したがって、
$$ \begin{align*} \left( \begin{array}{c} X_1 \\ X_3 \\ X_5 \\ X_7 \end{array} \right) &= \left( \begin{array}{cccccccc} W_8^{0} & W_8^{1} & W_8^{2} & W_8^{3}\\ W_8^{0} & W_8^{3} & -W_8^{2} & W_8^{1}\\ W_8^{0} & -W_8^{1} & W_8^{2} & -W_8^{3}\\ W_8^{0} & -W_8^{3} & -W_8^{2} & -W_8^{1}\\ \end{array} \right) \left( \begin{array}{c} x_0 - x_4 \\ x_1 - x_5 \\ x_2 - x_6 \\ x_3 - x_7 \end{array} \right) \end{align*} $$
となる。また、回転因子の対称性を用いなくても問題ないため、もとにもどすと、
$$ \begin{align*} \left( \begin{array}{c} X_1 \\ X_3 \\ X_5 \\ X_7 \end{array} \right) &= \left( \begin{array}{cccccccc} W_8^{0} & W_8^{1} & W_8^{2} & W_8^{3}\\ W_8^{0} & W_8^{3} & W_8^{6} & W_8^{1}\\ W_8^{0} & W_8^{5} & W_8^{2} & W_8^{7}\\ W_8^{0} & W_8^{7} & W_8^{6} & W_8^{5}\\ \end{array} \right) \left( \begin{array}{c} x_0 - x_4 \\ x_1 - x_5 \\ x_2 - x_6 \\ x_3 - x_7 \end{array} \right) \end{align*} $$
ここで、指数法則を用いて列ベクトルから回転因子を取り出すと、
$$ \begin{align*} \left( \begin{array}{c} X_1 \\ X_3 \\ X_5 \\ X_7 \end{array} \right) &= \left( \begin{array}{cccccccc} W_8^{0} & W_8^{0} & W_8^{0} & W_8^{0}\\ W_8^{0} & W_8^{2} & W_8^{4} & W_8^{6}\\ W_8^{0} & W_8^{4} & W_8^{0} & W_8^{4}\\ W_8^{0} & W_8^{6} & W_8^{4} & W_8^{2}\\ \end{array} \right) \left( \begin{array}{c} W_8^0 (x_0 - x_4)\\ W_8^1 (x_1 - x_5)\\ W_8^2 (x_2 - x_6)\\ W_8^3 (x_3 - x_7) \end{array} \right) \end{align*} $$
2x2 行列になったとき
上の計算を再帰的に行う、このとき終了条件が必要になる。
ここで、このときの回転因子の行列は
$$ \begin{align*} \left( \begin{array}{cc} W_8^0 & W_8^0\\ W_8^0 & W_8^4\\ \end{array} \right) = \left( \begin{array}{cc} 1 & 1\\ 1 & -1\\ \end{array} \right) \end{align*} $$
よって、ベクトルとの積は
$$ \begin{align*} \left( \begin{array}{cc} 1 & 1\\ 1 & -1\\ \end{array} \right) \left( \begin{array}{c} x \\ y \end{array} \right) = \left( \begin{array}{c} x + y\\ x - y \end{array} \right) \end{align*} $$
バタフライ演算
ここで、回転因子の行列は奇数と偶数で全く同じ形になっていることがわかる。
この性質を利用して、重複する計算を省略していく。
（図はいろいろなとこにあるので省略）
とうとう実装編へ！