高速フーリエ変換で畳み込みを高速化する 2. 高速フーリエ変換(FFT)入門

Data Science

2018.7.26

Topics

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

高速フーリエ変換とは

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

\mathcal{F}(x) = \left( \begin{array}{cc} \mathcal{F}(x)(1) \\ \vdots \\\mathcal{F}(x)(N)\end{array} \right)\in \mathbb{C}^N


\displaystyle\mathcal{F}(x)(n) = \frac{1}{\sqrt N}\sum_{t=1}^N x(t) \exp(-\frac{i2\pi nt}{N})

で定義されるのでした。これを素朴に計算すると、\mathcal{F}(x)(n)を計算するためにN+1の掛け算とN-1回の足し算が必要なため、\mathcal{F}(x)(n)を計算するのにO(N)時間かかります。これをnを動かして繰り返すと、\mathcal{F}(x)を計算するのに全体としてO(N^2)の計算量がかかります。高速フーリエ変換では、これがO(N\log N)に改善されます。
いま、次元数Nが偶数であると仮定してこれを少し変形すると、
\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}

と計算できます。N/2次元のベクトルy, z\in \mathbb{C}^{N/2}y(t) = x(2t-1), z(t) = x(2t) \,(t = 1, 2, \ldots, N)で定めれば、
\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}

と書くことができます。ただし\cdot = y, z \in \mathbb{C}^{N/2}に対して\mathcal{F}(\cdot)N/2次元ベクトル空間\mathbb{C}^{N/2}の元ですが、\mathcal{F}(\cdot)(n+N/2) = \mathcal{F}(\cdot)(n)\mathcal{F}(\cdot)\in\mathbb{C}^Nに自然に拡張して同一視します。なお、いまはNが偶数の場合について述べましたが、それ以外の場合でも適宜修正すれば同様の計算ができます。
以上の議論により、次のことがわかります。x\in\mathbb{C}^Nの離散フーリエ変換\mathcal{F}(x)\in\mathbb{C}^Nを計算するには、N/2次元のベクトルy, zy(t) = x(2t-1), z(t) = x(2t)で定め、y, zの離散フーリエ変換を計算し、その線形結合\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}を計算すればよい。
この方法で繰り返し対象のベクトルの次元を小さくしていき、再帰的に計算して離散フーリエ変換\mathcal{F}(x)を計算するアルゴリズムを、高速フーリエ変換と呼びます。この分割統治法により、離散フーリエ変換が時間計算量O(N\log N)で計算できます。
まったく同じ方法で、逆離散フーリエ変換も高速に計算することができます。この方法を逆高速フーリエ変換とよびます。

まとめ

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

参考文献

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

データ分析と機械学習とソフトウェア開発をしています。 アルゴリズムとデータ構造が好きです。

Recommends

こちらもおすすめ

Special Topics

注目記事はこちら