何番煎じか分からんですが、どうしても数式が多い1と読む気がなくなるので、
厳密さは棚上げして、なんで計算量が減るのかのイメージを把握する目的で、記事を残してみます。
前提知識
- 三角関数を知っている
- 複素数を知っている
- オイラーの公式を知っている
- 積分を知っている2
- 行列の積の計算規則を知っている
結構なレベルの数学知識が要求される内容なんだと改めて思いますね。。
フーリエ変換
上記の前提知識があれば、下記が分かりやすいと思います。
【画像45枚あり】フーリエ変換を宇宙一わかりやすく解説してみる
高速フーリエ変換
数学・工学系の記事にしてはめずらしく、Wikipediaの解説（下記）がイメージ付きやすいように思います。
上記(Wikipedia記事)の補足説明
上記のWikipediaの式（行列の計算式のとこ）で使われている記号と同じ記号を割り当てます。3
W=e^{2\pi i\frac{1}{N}}
とおくと、高速フーリエ変換では下記の$X_0, X_1, X_2,...,X_{N-1}$が求める対象になります。
X_t = \sum_{k=0}^{N-1}W^{k\ t}x_k
例として、$N=8$のときは下記のようになります。（通常、高速フーリエ変換を適用する際は$N$は$2$のべき乗を前提とします。）
\begin{align}
X_0&=W^0x_0+W^0x_1+W^0x_2+W^0x_3+W^0x_4+W^{0}x_5+W^{0}x_6+W^{0}x_7\\
X_1&=W^0x_0+W^1x_1+W^2x_2+W^3x_3+W^4x_4+W^{5}x_5+W^{6}x_6+W^{7}x_7\\
X_2&=W^0x_0+W^2x_1+W^4x_2+W^6x_3+W^8x_4+W^{10}x_5+W^{12}x_6+W^{14}x_7\\
&:\\
X_7&=W^0x_0+W^7x_1+W^{14}x_2+W^{21}x_3+W^{28}x_4+W^{35}x_5+W^{42}x_6+W^{49}x_7
\end{align}
下記のようにベクトルにみたてて、
\begin{pmatrix}
X_0\\
X_1\\
X_2\\
:\\
X_7\\
\end{pmatrix}
と書くと、下記のような行列とベクトルの積として表現できます。左辺の行列の要素をクリックすると、関連する要素が強調表示されます。
（※下記で左辺の$x$の添え字の並びが連番ではなくなっているのは意図的なものです。）
See the Pen Matrix Image of Fast Fourier Transform by kob58im (@kob58im) on CodePen.
（描画サイズが大きいので、縮小表示(0.5x)もしくは[CodePen上での閲覧](https://codepen.io/kob58im/pen/gOrRQwN)推奨です。[^4]）上記の分解は、$W^N=e^{2\pi i}=1$であることにより、$W^8=1\ (=W^0)$が成り立つことを利用しています。
右辺の右側から結合させる（積を求める）のがミソのようで、
右辺の右側の行列（真ん中というべきかも（？））が、$\frac{N}{2}$次の行列２つ分相当になり、再帰的に分解ができる構造になります。
さらに、$W^{N/2}=e^{\pi i}=-W$であることを使って計算を効率化させたりするようです。