FFT アルゴリズムの理解（2013 年）

2013 年 8 月 28 日（水）

高速フーリエ変換（FFT: Fast Fourier Transform）は、信号処理およびデータ解析の分野において最も重要なアルゴリズムの一つです。私は何年もこの手法を用いてきましたが、形式的なコンピュータサイエンスのバックグラウンドを持たなかったため、今週になって初めて、なぜ FFT が離散フーリエ変換（DFT）をそれほど高速に計算するのかと自問した次第でした。古びたアルゴリズムの本を手直しし、調べた結果、J・W・クージーとジョン・タッキーが 1965 年の画期的な論文で導入した、見かけ上単純に見えるしかし極めて巧妙な計算のトリックについては、非常に面白く読ませていただきました。

本稿の目的は、クージー‐タッキー FFT アルゴリズムの核心に diving in（深読み）し、それを導き出した対称性の原理を解説するとともに、理論を実践に移すための簡潔な Python 実装例を示すことにあります。私の願いは、私自身のようなデータサイエンティストが、使用するアルゴリズムの背後で何が起きているのかというより包括的な理解を得ることを通じて、この探求が有益となることです。

離散フーリエ変換¶

FFT は、naively なアプローチでは$\mathcal{O}[N^2]$ の計算量が必要とされる離散フー理学変換（DFT）を、高速である$\mathcal{O}[N\log N]$ のアルゴリズムで実現します。より馴染みのある連続フーリエ変換と同様に、DFT も前進形式と逆転形式を持っています。それらは以下の式で定義されます：

前進離散フーリエ変換（DFT）: $$X_k = \sum_{n=0}^{N-1} x_n \cdot e^{-i2\pikn/~N}$$

逆離散フーリエ変換（IDFT）: $$x_n = \frac{1}{N}\sum_{k=0}^{N-1} X_k e^{i2\pikn/~N}$$

$x_n$ から $X_k$ への変換は、空間からの周波数空間への移行（位相空間から周波数空間へ）であり、信号の電力スペクトルを探索する上でも、特定の計算効率化のための問題変形においても非常に有用です。この実用例については、 forthcoming の天文学・統計学関連書籍の第 10 章を参照いただくことができます（図および Python ソースコードはここにアクセス可能です）。また、もともと困難だった微分方程式の積分を FFT がどのように簡素化するかの例として、「Python でシュレーディンガー方程式を解く」と題した私の投稿をご覧ください。

FFT は多くの分野で極めて重要であるため、Python にもこれを計算するための標準ツールやラッパーが多数用意されています。NumPy および SciPy の両方とも、極めて信頼性の高い FFTPACK ライブラリのラッパーを提供しており、それぞれ

numpy.fft

scipy.fftpack

本稿では当面は、これらの実装については一旦脇に置き、Python を使用して FFT を一からどのように計算するかを問いかけてみたいと思います。

離散フーリエ変換の計算¶

単純化のために、ここでは逆変換には触れないものとします（逆変換は非常に類似の方法で実装可能です）。上記の DFT の式を見ると、それは単なる直線的な線形操作に過ぎません：ベクトル$\vec{x}$ との行列ベクトル積$\vec{X} = M \cdot \vec{x}$ であり、その行列 $M$ は次のように与えられます。 $$M_{kn} = e^{-i2\pikn/~N}.$$

このことを踏まえ、DFT は単純な行列乗算を用いて以下のように計算できます：

In [1]: import numpy as np def DFT_slow(x): """一次元配列 x の離散フーリエ変換を計算する""" x = np.asarray(x, dtype=float) N = x.shape[0] n = np.arange(N) k = n.reshape((N, 1)) M = np.exp(-2j * np.pi * k * n / N) return np.dot(M, x)

結果を確認するために、NumPy の内蔵 FFT 関数との比較を行います：

In [2]: x = np.random.random(1024) np.allclose(DFT_slow(x), np.fft.fft(x))

アルゴリズムの遅さを確認するため、両アプローチの実行時間を比較します：

In [3]: %timeit DFT_slow(x) %timeit np.fft.fft(x)

10 loops, best of 3: 75.4 ms per loop 10000 loops, best of 3: 25.5 µs per loop

私たちは約 1000 倍も遅くなっています。これは、あえてシンプルにした実装であるため予想されることです。しかし、これが最悪のケースではありません。長さ$N$の入力ベクトルに対して、FFT アルゴリズムは$\mathcal{O}[N\log N]$でスケールする一方、私たちの「低速」アルゴリズムは$\mathcal{O}[N^2]$でスケールします。つまり、$N=10^6$ の要素の場合、FFT は約 50ms で完了するのに対し、私たちの低速なアルゴリズムではほぼ 20 時間必要になるでしょう！

では、FFT はどのようにしてこの高速化を実現しているのでしょうか？その答えは対称性の利用にあります。

離散フーリエ変換における対称性¶

アルゴリズム設計者にとって最も重要なツールの一つは、問題の対称性を活用することです。 analytical に一つの部分と別の部分が単純に関係していることを示すことができれば、サブ結果を一度だけ計算し、その計算コストを節約することができます。クージーとタッキーも、FFT を導出する際にまさにこのアプローチ采用了しました。

まず、$X_{N+k}$ の値がどうなるかを見てみましょう。上記の式より：

$$ \begin{align*} X_{N + k} &= \sum_{n=0}^{N-1} x_n \cdot e^{-i2\pi(N + k)n/N}\ &= \sum_{n=0}^{N-1} x_n \cdot e^{- i2\pin} \cdot e^{-i2\pikn~/N}\ &= \sum_{n=0}^{N-1} x_n \cdot e^{-i2\pikn~/~N} \end{align*} $$

ここで、整数$n$であれば $\exp[2\piin] = 1$ という恒等式を使用しました。最後の行は DFT の美しい対称性性質を示しています： $$X_{N+k} = X_k.$$

簡単な拡張により、 $$X_{k + i \cdot N} = X_k$$ となり、これは任意の整数$i$に対して成り立ちます。後述しますが、この対称性は DFT をはるかに高速に計算するための鍵となります。

DFT から FFT：対称性の活用¶

クージーとタッキーは、DFT の計算を 2 つのより小さい部分に分けることが可能であることを示しました。DFT の定義から出発すると：

$$ \begin{align} X_k &= \sum_{n=0}^{N-1} x_n \cdot e^{-i2\pikn/N} \ &= \sum_{m=0}^{N/2 - 1} x_{2m} \cdot e^{-i2\pik(2m)/N} + \sum_{m=0}^{N/2 - 1} x_{2m + 1} \cdot e^{-i2\pik~(2m + 1)/N} \ &= \sum_{m=0}^{N/2 - 1} x_{2m} \cdot e^{-i2\pikm/(N/2)} + e^{-i2\pik/N} \sum_{m=0}^{N/2 - 1} x_{2m + 1} \cdot e^{-i2\pikm~/~(N/2)} \end{align} $$

私たちは単一の離散フーリエ変換を、奇数項の要素に対して計算するものと同規模の小さな離散フーリエ変換と、偶数項の要素に対して計算するものと同規模のもう一つに分割しました。しかし現状では、まだ計算サイクルの節約にはなっていません。それぞれの項はそれぞれ $(N/2) \times N$ の計算を必要とし、合計では $N^2$ になります。

ここでのトリックは、これらの各項における対称性を活用することです。変数$k$の範囲は $0 \le k < N$ であり、一方$n$の範囲は $0 \le n < M \equiv N/2$ なので、前述の対称性性質から、各サブ問題に対しては半分だけの計算を実行すれば十分であることがわかります。私たちの$\mathcal{O}[N^2]$の計算は、$M$（$N$の半分）のサイズを持つことになり、$\mathcal{O}[M^2]$へと軽減されます。

しかしそこで止まる必要はありません：私たちのより小さなフーリエ変換が偶数長の$M$を持っていする限り、この分割統治アプローチを繰り返し適用でき、各ステップで計算コストを半分にしていきます。最終的に配列のサイズが小さくなり、この戦略がもはや有益でない時点で停止します。漸近的な極限において、この反復的なアプローチは$\mathcal{O}[N\log N]$でスケールします。

この反復的アルゴリズムは Python で非常に簡潔に実装でき、サブ問題のサイズが十分に小さくなった段階では前述の遅い DFT コードをフォールバックとして利用します：

In [4]: def FFT(x): """一次元 Cooley-Tukey FFT の反復的実装""" x = np.asarray(x, dtype=float) N = x.shape[0]

if N % 2 > 0:
    raise ValueError("x のサイズは 2 のべき乗である必要があります")
elif N <= 32:  # このカットオフ値は最適化されるべきです
    return DFT_slow(x)
else:
    X_even = FFT(x[::2])
    X_odd = FFT(x[1::2])
    factor = np.exp(-2j * np.pi * np.arange(N) / N)
    return np.concatenate([X_even + factor[:N / 2] * X_odd,
                           X_even + factor[N / 2:] * X_odd])

ここで、我々のアルゴリズムが正しい結果を生成するかを確認します：

In [5]: x = np.random.random(1024) np.allclose(FFT(x), np.fft.fft(x))

そして、我々の遅いバージョンとの実行時間を比較します：

In [6]: %timeit DFT_slow(x) %timeit FFT(x) %timeit np.fft.fft(x)

10 loops, best of 3: 77.6 ms per loop 100 loops, best of 3: 4.07 ms per loop 10000 loops, best of 3: 24.7 µs per loop

我々の計算は、naive なバージョンよりも桁違いに速くなりました！さらに言えば、我々の反復的アルゴリズムは漸近的には$\mathcal{O}[N\log N]$であり、私たちは高速フーリエ変換（Fast Fourier Transform）を実装したことになります。

ただし、NumPy の内蔵 FFT アルゴリズムとの速度にはまだ程遠いです。これは当然のことです。NumPy の fft を裏付ける FFTPACK アルゴリズムは、何年もの間細かな調整と最適化が施された Fortran 実装です。また、我々の NumPy ソリューションは Python スタックを用いた再帰呼び出しや多くの一時配列の割り当てを含んでおり、これらは追加の計算時間を招いています。

Python/NumPy でコードを高速化する際の賢い戦略には、可能な限り繰り返し計算をベクトライゼーション（向量化）することがあります。私たちはこれを達成し、その過程で反復的な関数呼び出しを排除して、Python 版の FFT をさらに効率的にします。

ベクトライズされた NumPy バージョン¶

上記の反復的 FFT 実装では、最下位の再帰レベルにおいて$N~/~32$個の同型の行列ベクトル積を実行しています。我々のアルゴリズムの効率は、これらすべての行列ベクトル積を一度に単一の行列行列積として計算することによって向上します。各次の再帰レベルでも、ベクトライズ可能な重複操作が行われます。NumPy はこのようなタイプの作業に長けており、その事実を活用して高速フーリエ変換のこのベクトライズされたバージョンを作成できます：

In [7]: def FFT_vectorized(x): """Cooley-Tukey FFT のベクトライズされた非反復的実装""" x = np.asarray(x, dtype=float) N = x.shape[0]

if np.log2(N) % 1 > 0:
    raise ValueError("x のサイズは 2 のべき乗である必要があります")

# 以下の N_min は上記の停止条件に相当し、2 のべき乗であるべきです
N_min = min(N, 32)

# 長さ N_min のすべてのサブ問題を一度に行う O[N^2] DFT を実行
n = np.arange(N_min)
k = n[:, None]
M = np.exp(-2j * np.pi * n * k / N_min)
X = np.dot(M, x.reshape((N_min, -1)))

# 再帰計算の各レベルを一括で構築していきます
while X.shape[0] < N:
    X_even = X[:, :X.shape[1] / 2]
    X_odd = X[:, X.shape[1] / 2:]
    factor = np.exp(-1j * np.pi * np.arange(X.shape[0])
                    / X.shape[0])[:, None]
    X = np.vstack([X_even + factor * X_odd,
                   X_even - factor * X_odd])

return X.ravel()

このアルゴリズムは少し不透明に見えますが、反復バージョンで使用された操作の単純な再編成に過ぎません。例外は一つあります：factor 計算における対称性を活用し、配列の半分のみを構築することです。再び、我々の関数が正しい結果を与えるかを確認します：

In [8]: x = np.random.random(1024) np.allclose(FFT_vectorized(x), np.fft.fft(x))

アルゴリズムがはるかに効率的になっているため、DFT_slow を除いて大きな配列を使用して時間を比較できます：

In [9]: x = np.random.random(1024 * 16) %timeit FFT(x) %timeit FFT_vectorized(x) %timeit np.fft.fft(x)

10 loops, best of 3: 72.8 ms per loop 100 loops, best of 3: 4.11 ms per loop 1000 loops, best of 3: 505 µs per loop

我々の実装はまたしても桁違いに改善されました！私たちは、Fortran の FFTPACK ベンチマークと比べてまだ約 10 倍程度の差がありますが、純粋な Python + NumPy を数 dozen 行だけで達成しています。計算能力という点ではまだ対抗できませんが、可読性の観点からは Python 版は FFTPACK のソース（閲覧はこちらから）よりもはるかに優れています。

では、FFTPACK が最後のわずかなスピードアップを実現するのはどのようにしてでしょうか？主にそれは詳細な事務作業の問題です。FFTPACK は、再利用可能などのサブ計算も確実に再利用することを確認するために多くの時間を費やしています。我々の NumPy バージョンはまだ余計なメモリの割り当てとコピーを含んでおり、Fortran などの低レベル言語ではメモリ使用量を取り扱い最小化するのが容易です。さらに、Cooley-Tukey アルゴリズムはサイズが 2 でない分割（ここでは実装している radix-2 Cooley-Tukey FFT）を使用するために拡張できます。また、畳み込みに基づいた本質的に異なるアプローチを含むより高度な FFT アルゴリズムも使用でき（例えば、Bluestein のアルゴリズムと Rader のアルゴリズム参照）、上記の拡張および技術の組み合わせにより、配列のサイズが 2 のべき乗でない場合でも非常に高速な FFT を実現できます。

純粋な Python 関数は実践的には有用ではないかもしれませんが、FFT ベースのデータ分析の背後で何が起きているかという直感を提供してくれたことに感謝したいです。データサイエンティストとして、我々はアルゴリズムに強みを持つ同僚によって構築された根本的なツールブラックボックス実装で十分に対処できますが、私にとっては、データを適用する低レベルアルゴリズムについてより理解があるほど、実践家としての質が高まると強く信じています。

このブログ投稿は IPython Notebook で完全に書かれました。完全版ノートブックをダウンロードするにはこちらをクリックするか、静的表示はこちらをクリックしてください。