こんにちは。データサイエンスチームのtmtkです。
前回の記事（1.離散フーリエ変換入門）では、離散フーリエ変換を紹介しました。今回の記事では、離散フーリエ変換を高速に計算できる高速フーリエ変換（FFT）というアルゴリズムを紹介します。

高速フーリエ変換とは

高速フーリエ変換は、離散フーリエ変換を分割統治法によって高速に計算します。計算量は入力のベクトル[latex]x \in \mathbb{C}^N[/latex]の次元[latex]N \in \mathbb{N}[/latex]に対して[latex]O(N\log N)[/latex]になります。
離散フーリエ変換の定義を思い出すと、[latex]x\in \mathbb{C}^N[/latex]の離散フーリエ変換

[latex]\mathcal{F}(x) = \left( \begin{array}{cc} \mathcal{F}(x)(1) \\ \vdots \\\mathcal{F}(x)(N)\end{array} \right)\in \mathbb{C}^N[/latex]
は
[latex]\displaystyle\mathcal{F}(x)(n) = \frac{1}{\sqrt N}\sum_{t=1}^N x(t) \exp(-\frac{i2\pi nt}{N})[/latex]
で定義されるのでした。これを素朴に計算すると、[latex]\mathcal{F}(x)(n)[/latex]を計算するために[latex]N+1[/latex]の掛け算と[latex]N-1[/latex]回の足し算が必要なため、[latex]\mathcal{F}(x)(n)[/latex]を計算するのに[latex]O(N)[/latex]時間かかります。これを[latex]n[/latex]を動かして繰り返すと、[latex]\mathcal{F}(x)[/latex]を計算するのに全体として[latex]O(N^2)[/latex]の計算量がかかります。高速フーリエ変換では、これが[latex]O(N\log N)[/latex]に改善されます。
いま、次元数[latex]N[/latex]が偶数であると仮定してこれを少し変形すると、
[latex]\displaystyle \begin{aligned} \mathcal{F}(x)(n) =& \frac{1}{\sqrt N}\sum_{t=1}^N x(t) \exp(-\frac{i2\pi nt}{N}) \\ = &\frac{1}{\sqrt N}\sum_{t=1}^{N/2} x(2t-1) \exp(-\frac{i2\pi n(2t-1)}{N}) + \frac{1}{\sqrt N}\sum_{t=1}^{N/2} x(2t) \exp(-\frac{i2\pi n2t}{N})\\ = &\frac{\exp(\frac{i2\pi n}{N})}{\sqrt 2}\frac{1}{\sqrt{N/2}}\sum_{t=1}^{N/2} x(2t-1) \exp(-\frac{i2\pi nt}{N/2}) + \frac{1}{\sqrt{2}}\frac{1}{\sqrt {N/2}}\sum_{t=1}^{N/2} x(2t) \exp(-\frac{i2\pi nt}{N/2}) \end{aligned}[/latex]
と計算できます。[latex]N/2[/latex]次元のベクトル[latex]y, z\in \mathbb{C}^{N/2}[/latex]を[latex]y(t) = x(2t-1), z(t) = x(2t) \,(t = 1, 2, \ldots, N)[/latex]で定めれば、
[latex]\displaystyle \begin{aligned} &\mathcal{F}(x)(n) = &\frac{\exp(\frac{i2\pi n}{N})}{\sqrt 2}\mathcal{F}(y)(n) + \frac{1}{\sqrt{2}}\mathcal{F}(z)(n) \end{aligned}[/latex]
と書くことができます。ただし[latex]\cdot = y, z \in \mathbb{C}^{N/2}[/latex]に対して[latex]\mathcal{F}(\cdot)[/latex]は[latex]N/2[/latex]次元ベクトル空間[latex]\mathbb{C}^{N/2}[/latex]の元ですが、[latex]\mathcal{F}(\cdot)(n+N/2) = \mathcal{F}(\cdot)(n)[/latex]で[latex]\mathcal{F}(\cdot)\in\mathbb{C}^N[/latex]に自然に拡張して同一視します。なお、いまは[latex]N[/latex]が偶数の場合について述べましたが、それ以外の場合でも適宜修正すれば同様の計算ができます。
以上の議論により、次のことがわかります。[latex]x\in\mathbb{C}^N[/latex]の離散フーリエ変換[latex]\mathcal{F}(x)\in\mathbb{C}^N[/latex]を計算するには、[latex]N/2[/latex]次元のベクトル[latex]y, z[/latex]を[latex]y(t) = x(2t-1), z(t) = x(2t)[/latex]で定め、[latex]y, z[/latex]の離散フーリエ変換を計算し、その線形結合[latex]\begin{aligned} &\mathcal{F}(x)(n) = &\frac{\exp(\frac{i2\pi n}{N})}{\sqrt 2}\mathcal{F}(y)(n) + \frac{1}{\sqrt{2}}\mathcal{F}(z)(n) \end{aligned}[/latex]を計算すればよい。
この方法で繰り返し対象のベクトルの次元を小さくしていき、再帰的に計算して離散フーリエ変換[latex]\mathcal{F}(x)[/latex]を計算するアルゴリズムを、高速フーリエ変換と呼びます。この分割統治法により、離散フーリエ変換が時間計算量[latex]O(N\log N)[/latex]で計算できます。
まったく同じ方法で、逆離散フーリエ変換も高速に計算することができます。この方法を逆高速フーリエ変換とよびます。

まとめ

この記事では、高速フーリエ変換（FFT）のアルゴリズムを紹介しました。高速フーリエ変換は離散フーリエ変換を高速に計算するアルゴリズムで、分割統治法を用いて、[latex]N[/latex]次元のベクトルを時間計算量[latex]O(N\log N)[/latex]で離散フーリエ変換できます。
次の記事では、高速フーリエ変換の応用として、畳み込み処理を高速化する方法を紹介します。

参考文献

• 山下幸彦他『工学のためのフーリエ解析』