高速フーリエ変換で畳み込みを高速化する 1. 離散フーリエ変換入門

Data Science

2018.7.24

Topics

こんにちは。データサイエンスチームのtmtkです。
この記事では、離散フーリエ変換の紹介をします。

離散フーリエ変換とは

離散フーリエ変換は、要素数がNの有限集合を定義域にもつ関数を、

\phi_n(t) = \displaystyle\exp(\frac{i2\pi nt}{N}) \quad (n = 1, 2, \ldots, N)

の形の関数の和で書き表す手続きのことをいいます。別の言い方をすれば、線形空間上で基底変換をしていると考えることもできます。
離散フーリエ変換は、高速フーリエ変換というアルゴリズムで高速化できます。
離散フーリエ変換の応用として、多倍長整数演算や、畳み込み処理の高速化などがあるようです。
この記事では、離散フーリエ変換の定義とその意味について紹介します。続く記事では、高速フーリエ変換やその応用として畳み込み処理の高速化を紹介します。

離散フーリエ変換の定義

はじめに、自然数N \in \mathbb{N}を固定します。
関数x \colon \mathbb{Z} \to \mathbb{C}が周期Nをもつとします。すなわち、任意の整数tに対して、x(t+N) = x(t)が成り立っているとします。このとき、xx(1), \ldots, x(N)から決まるので、xは有限集合\{ 1, 2, \ldots, N\}上の関数

\begin{array}{cccc}x\colon &\{1, \ldots, N\} &\to &\mathbb{C} \\ &t &\mapsto &x(t)\end{array}

N次元ベクトル空間\mathbb{C}^Nの元
\left(\begin{array}{c}x(1) \\ \vdots \\ x(N) \end{array}\right)

と同一視することができます。以後、N次元ベクトル
\displaystyle x = \left( \begin{array}{c} x(1)\\ \vdots \\x(N) \end{array} \right)

のみについて考えますが、周期関数や有限集合上の関数とも考えられることに注意してください。
さて、N次元ベクトルxに対して、xの離散フーリエ変換
\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})

で定義します。これが離散フーリエ変換の定義です。

離散フーリエ変換の意味

この離散フーリエ変換の定義はどのように出てきたものなのでしょうか。これから説明します。
周期関数

\displaystyle\begin{array}{cccc}\phi_n: &\mathbb{Z} &\to &\mathbb{C}\\ &t &\mapsto &\exp(\frac{i2\pi nt}{N})\end{array}

を考えることができます。これと同一視できるN次元ベクトル
\displaystyle \begin{array}{c}\phi_n = \left( \begin{array}{cc}  \exp(\frac{i2\pi n1}{N}) \\ \vdots \\  \exp(\frac{i2\pi nN}{N})\end{array}\right)\end{array}

n = 1, \ldots, Nにわたって集めると、これは\mathbb{C}^N上の正規直交基底になることがわかります。実際、内積を計算すると
\displaystyle \begin{aligned}(\phi_n, \phi_m) &= \sum_{t = 1}^N \overline{\phi_n(t)} \phi_m(t) \\ &= \frac{1}{N}\sum_{t=1}^N \exp(\frac{i2\pi (-n+m)t}{N}) \\ &= \delta_{nm} \end{aligned}

となるので、正規直交基底になっていることが確認できました。
そこで、標準基底\{e_1, \ldots, e_N\}で表示されたベクトルx \in \mathbb{C}^nを基底\{ \phi_1, \ldots, \phi_N\}に変換して表示すると、x
\displaystyle x = \sum_{n = 1}^N (\phi_n, x) \phi_n

と書けることから、x\phi_nに関する係数は
\displaystyle\begin{aligned}(\phi_n, x) &= \sum_{t = 1}^N \overline{\phi_n(t)} x(t) \\ &= \frac{1}{\sqrt{N}}\sum_{t = 1}^N x(t)\exp (-\frac{i2\pi nt}{N})\end{aligned}

となります。これはxのフーリエ変換の第n\mathcal{F}(x)(n)です。これが離散フーリエ変換の由来です。
つまり、離散フーリエ変換は線形空間\mathbb{C}^Nの標準基底\{e_1, \ldots, e_N\}から正規直交基底\{\phi_1, \ldots, \phi_N\}への基底変換です。

逆離散フーリエ変換

離散フーリエ変換の逆の操作で、逆離散フーリエ変換というものがあります。これは離散フーリエ変換の逆の基底変換です。具体的に書き表すと以下のようになります。
 N次元ベクトル空間\mathbb{C}^Nの元

x = \left(\begin{array}{c}x(1) \\ \vdots \\ x(N) \end{array}\right)

に対して、その逆離散フーリエ変換\mathcal{F}^{-1}(x)\in\mathbb{C}^N
\displaystyle\mathcal{F}^{-1}(x)(t) = \frac{1}{\sqrt N}\sum_{n=1}^N x(n) \exp(+\frac{i2\pi tn}{N})

で定義します。離散フーリエ変換の場合と指数関数\expの引数\frac{i2\pi nt}{N}の符号が変わっています。
実際に互いに逆変換になっていることは、以下のように直接の計算で確かめられます。まず、最初に\mathcal{F}^{-1}\circ\mathcal{F}については
\displaystyle\begin{aligned}\left(\mathcal{F}^{-1}\circ\mathcal{F}(x)\right)(t) &= \frac{1}{\sqrt{N}}\sum_{n=1}^N \mathcal{F}(x)(n)\exp(\frac{i2\pi t n }{N}) \\ &= \frac{1}{\sqrt N}\sum_{n=1}^N \left(\frac{1}{\sqrt N}\sum_{s=1}^N x(s)\exp(-\frac{i2\pi ns}{N})\right)\exp(\frac{i2\pi t n }{N}) \\ &= \sum_{s=1}^N x(s)\left(\frac{1}{N}\sum_{n=1}^N\exp(\frac{i2\pi n(t-s)}{N})\right) \\ &= \sum_{s=1}^N x(s) \delta_{st} \\ &= x(t)\end{aligned}

より、\mathcal{F}^{-1}\circ \mathcal{F} (x) = xが任意の x \in \mathbb{C}^Nについて成り立ちます。同様にして、\mathcal{F}\circ\mathcal{F}^{-1}(x) = xも示すことができます。したがって、離散フーリエ変換\mathcal{F}と逆離散フーリエ変換\mathcal{F}^{-1}は互いに逆変換になっています。

まとめ

この記事では、離散フーリエ変換の定義を紹介しました。離散フーリエ変換はベクトル空間の基底変換と考えることができます。離散フーリエ変換の逆変換を逆離散フーリエ変換と呼びます。

参考文献

テックブログ新着情報のほか、AWSやGoogle Cloudに関するお役立ち情報を配信中!

tmtk

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

Recommends

こちらもおすすめ

Special Topics

注目記事はこちら