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

tmtk

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)$ が成り立っているとします。このとき、 $x$ は $x(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}$ は互いに逆変換になっています。