離散フーリエ変換について

はじめに

この記事は離散フーリエ変換についての覚書です。

記号の約束

長さ$N$の複素数列全体を$\mathbb{C}^N$と書く。

$\{ a_n \}_{n = 0}^{N - 1} \in \mathbb{C}^N$とする。また、$n \in \mathbb{Z}$に対し、$n$を$N$で割ったあまりを$q(n)$とおく。$q(n)$により、記号$a[n]$を次のように定義する。
$$ a[n] = a_{q(n)} $$
これはつまり
$$ \dots,\,a[1] = a_1,\,a[0] = a_0,\,a[-1] = a_{N - 1},\,a[-2] = a_{N - 2},\dots $$
ということ。以降、長さ$N$で一般項が$a_n$の数列を$\{ a[n] \}_{n = 0}^{N - 1}$とも表記する。

離散フーリエ変換

複素数列$x = \{ x[n] \}_{n = 0}^{N - 1}$に対し、次の式で数列$X = \{ X[n] \}_{n = 0}^{N - 1}$を定義する。
$$ X[n] = \sum_{k = 0}^{N - 1} x[k] e^{-i\frac{2\pi}{N}kn} $$

数列$X$のことを$x$の離散フーリエ変換といい、次のように表す。
$$ X = \mathcal{F}(x) $$

離散フーリエ変換の性質

パーセバルの等式

$\mathcal{F}(x)$の定義式から、次の式は任意の$x, y \in \mathbb{C}^N$、$a, b \in \mathbb{C}$に対して明らかに成り立つ。
$$ \mathcal{F}(ax + by) = a\mathcal{F}(x) + b\mathcal{F}(y) $$

したがって$\mathcal{F}$は線形写像である。そこで、標準基底に関する表現行列$W$を考えると次のようになる。
$$ W = \left( e^{-i\frac{2\pi}{N}nm} \right) = \begin{pmatrix} e^{-i\frac{2\pi}{N} \cdot 0 \cdot 0} & e^{-i\frac{2\pi}{N} \cdot 1 \cdot 0} & \cdots & e^{-i\frac{2\pi}{N} \cdot (N - 1) \cdot 0} \\ e^{-i\frac{2\pi}{N} \cdot 0 \cdot 1} & e^{-i\frac{2\pi}{N} \cdot 1 \cdot 1} & \cdots & e^{-i\frac{2\pi}{N} \cdot (N - 1) \cdot 1} \\ \vdots & \vdots & \ddots & \vdots \\ e^{-i\frac{2\pi}{N} \cdot 0 \cdot (N - 1)} & e^{-i\frac{2\pi}{N} \cdot 1 \cdot (N - 1)} & \cdots & e^{-i\frac{2\pi}{N} \cdot (N - 1) \cdot (N - 1)} \end{pmatrix} $$

$w = e^{i\frac{2\pi}{N}}$とおくともう少し見た目がきれいになる。
$$ W = \begin{pmatrix} w^{-0 \cdot 0} & w^{-1 \cdot 0} & \cdots & w^{-(N -1) \cdot 0} \\ w^{-0 \cdot 1} & w^{-1 \cdot 1} & \cdots & w^{-(N - 1) \cdot 1} \\ \vdots & \vdots & \ddots & \vdots \\ w^{-0 \cdot (N - 1)} & w^{-1 \cdot (N - 1)} & \cdots & w^{-(N - 1) \cdot (N - 1)} \\ \end{pmatrix} $$

ここで$U = \frac{1}{\sqrt{N}} A$と置きなおす。このとき$U$はユニタリ行列になる。つまり、$U$には逆行列があって$U^{-1} = \overline{U^\top}$となる。

ユニタリ行列の性質から、$U$は内積を変えない。実際
$$ \langle Ux, Uy \rangle = Ux \overline{(Uy)^\top} = Ux \overline{y^\top U^\top} = U \langle x, y \rangle U^{-1} = \langle x, y \rangle $$
である。したがって次の等式が成り立つ。
$$ \langle \mathcal{F}(x), \mathcal{F}(y) \rangle = N \langle x, y \rangle $$

特に、$x = y$のときは次のようになる。
$$ \begin{alignat*}{1} \langle \mathcal{F}(x), \mathcal{F}(x) \rangle &= N\langle x, y \rangle \\ \lVert x \rVert^2 &= \frac{1}{N} \lVert \mathcal{F}(x) \rVert^2 \end{alignat*} $$
最後の式を「パーセバルの等式」という。

畳み込み定理

巡回畳み込みは$\mathbb{C}^N$の二項演算であり、次のように定義される。
$$ a * b = \left\{ \sum_{k = 0}^{N - 1}a[k]b[n - k] \right\}_{n = 0}^{N - 1} $$

畳み込み定理とは、離散フーリエ変換と巡回畳み込みが持つ次の関係のことである。
$$ \mathcal{F}(a * b) = \mathcal{F}(a) \cdot \mathcal{F}(b) $$

実際に成り立つことを確認しよう。$n = 0,\dots,N - 1$を１つとる。$\sum$の順序は勝手に交換して良いから
$$ \begin{alignat*}{1} \mathcal{F}(a * b)[n] &= \sum_{k = 0}^{N - 1} (a * b)[k] e^{-i \frac{2\pi}{N} kn} \\ &= \sum_{k = 0}^{N - 1} \left( \sum_{l = 0}^{N - 1} a[l]b[k - l] \right) e^{-i \frac{2\pi}{N} kn} \\ &= \sum_{l = 0}^{N - 1} \sum_{k = 0}^{N - 1} a[l]b[k - l] e^{-i \frac{2\pi}{N} kn} \\ &= \sum_{l = 0}^{N - 1} a[l] \sum_{k = 0}^{N - 1} b[k - l] e^{-i \frac{2\pi}{N} kn} \\ &= \sum_{l = 0}^{N - 1} a[l] \sum_{k = 0}^{N - 1} b[k - l] e^{-i \frac{2\pi}{N} (k - l)n} e^{-i \frac{2\pi}{N} ln} \\ &= \sum_{l = 0}^{N - 1} a[l] e^{-i \frac{2\pi}{N} ln} \sum_{k = 0}^{N - 1} b[k - l] e^{-i \frac{2\pi}{N} (k - l)n} \end{alignat*} $$
と変形できる。ここで、$\sum_{k = 0}^{N - 1} b[k - l] e^{-i \frac{2\pi}{N} (k - l)n}$をよく見ると、これは$\sum_{k = 0}^{N - 1} b[k] e^{-i \frac{2\pi}{N} kn}$に等しいことが分かる（ちょうど足す順番を入れ替えた形になっている）。$\sum_{k = 0}^{N - 1} b[k] e^{-i \frac{2\pi}{N} kn} = \mathcal{F}(b)[n]$なので
$$ \begin{alignat*}{1} \mathcal{F}(a * b)[n] &= \sum_{l = 0}^{N - 1} a[l] e^{-i \frac{2\pi}{N} ln} \sum_{k = 0}^{N - 1} b[k - l] e^{-i \frac{2\pi}{N} (k - l)n} \\ &= \sum_{l = 0}^{N - 1} a[l] e^{-i \frac{2\pi}{N} ln} \mathcal{F}(b)[n] \\ &= \mathcal{F}(a)[n] \cdot \mathcal{F}(b)[n] \end{alignat*} $$
となる。すべての$n = 0,\dots,N - 1$についてこれが成り立つから、確かに
$$ \mathcal{F}(a * b) = \mathcal{F}(a) \cdot \mathcal{F}(b) $$
が確認できた。

巡回畳み込みと固有分解

畳み込み定理は線形代数によっても示せる。$a * b$を、$b$に$a$を左から掛けた結果と考えよう。このとき、写像
$$ \varphi_a \colon \mathbb{C}^N \ni x \mapsto a * x \in \mathbb{C}^N $$
は（畳み込み積の定義により）線形写像になる。

そこで、$\varphi_a$の標準基底に関する表現行列を考える。$e_i$を第$i$項が$1$の単位ベクトルとすると
$$ \begin{alignat*}{1} \varphi_a (e_i) &= a * e_i \\ &= \left\{ \sum_{k = 0}^{N - 1}a[k]e_i[n - k] \right\}_{n = 0}^{N - 1} \\ &= \left\{ a[n - i] \right\}_{n = 0}^{N - 1} \quad (\because n - k \equiv i \mod N \iff k \equiv n - i \mod N) \\ &= (a[0 - i], a[1 - i], \dots, a[(N - 1) - i])^\top \end{alignat*} $$
だから
$$ \begin{alignat*}{1} \varphi_a (e_0) = a * e_0 &= (a_0,\ a_1,\ a_2,\ \dots,\ a_{N - 1})^\top \\ \varphi_a (e_1) = a * e_1 &= (a_{N - 1},\ a_0,\ a_1,\ \dots,\ a_{N - 2})^\top \\ \varphi_a (e_2) = a * e_2 &= (a_{N - 2},\ a_{N - 1},\ a_0,\ \dots,\ a_{N - 3})^\top \\ &\vdots \\ \varphi_a (e_{N-1}) = a * e_{N-1} &= (a_1,\ a_2,\ a_3,\ \dots,\ a_0)^\top \end{alignat*} $$
であり、$\varphi_a$の表現行列$\Phi (a)$は次のようになる。
$$ \Phi (a) = \begin{pmatrix} a_0 & a_{N - 1} & a_{N - 2} & \cdots & a_1 \\ a_1 & a_0 & a_{N - 1} & \cdots & a_2 \\ a_2 & a_1 & a_0 & \cdots & a_3 \\ \vdots & \vdots & \vdots & \ddots & \vdots \\ a_{N - 1} & a_{N - 2} & a_{N - 3} & \cdots & a_0 \\ \end{pmatrix} $$

一般に、このような形で書ける行列$\Phi (a)$を巡回行列という。

ここで、唐突ではあるが$\Phi (a)$を対角化しよう。固有方程式は次のとおりである。
$$ \det (\lambda E - \Phi (a)) = \det \begin{pmatrix} \lambda - a_0 & -a_{N - 1} & -a_{N - 2} & \cdots & -a_1 \\ -a_1 & \lambda - a_0 & -a_{N - 1} & \cdots & -a_2 \\ -a_2 & -a_1 & \lambda - a_0 & \cdots & -a_3 \\ \vdots & \vdots & \vdots & \ddots & \vdots \\ -a_{N - 1} & -a_{N - 2} & -a_{N - 3} & \cdots & \lambda - a_0 \\ \end{pmatrix} = 0 $$

まず、第１列に他の列をすべて足すと、第１列に表れる項はすべて$\lambda - (a_0 + \cdots + a_{N - 1})$になる。したがって、$\lambda = a_0 + \cdots + a_{N - 1}$のとき第１列は０ベクトルになるので、これは解の１つである。つまり、$\Phi (a)$の固有値の１つは$a_0 + \cdots + a_{N - 1}$である。

ここで第１列に$w^{0n}$、第２列に$w^{1n}$、第３列に$w^{2n}$……を掛ける。ただし$n = 0, \dots, N - 1$である。すると
$$ \det \begin{pmatrix} w^{0n} (\lambda - a_0) & w^{1n} (-a_{N - 1}) & w^{2n} (-a_{N - 2}) & \cdots & w^{(N-1)n} (-a_1) \\ w^{0n} (-a_1) & w^{1n} (\lambda - a_0) & w^{2n} (-a_{N - 1}) & \cdots & w^{(N-1)n} (-a_2) \\ w^{0n} (-a_2) & w^{1n} (-a_1) & w^{2n} (\lambda - a_0) & \cdots & w^{(N-1)n} (-a_3) \\ \vdots & \vdots & \vdots & \ddots & \vdots \\ w^{0n} (-a_{N - 1}) & w^{1n} (-a_{N - 2}) & w^{2n} (-a_{N - 3}) & \cdots & w^{(N-1)n} (\lambda - a_0) \\ \end{pmatrix} = 0 $$
である。

次に、第１行に$w^{-0n}$、第２行に$w^{-1n}$、第３行に$w^{-2n}$……を掛ける。
$$ \det \begin{pmatrix} \lambda - a_0 & -w^{1n}a_{N-1} & -w^{2n}a_{N-2} & \cdots & -w^{(N-1)n}a_1 \\ -w^{-1n}a_1 & \lambda - a_0 & -w^{1n}a_{N-1} & \cdots & -w^{(N-2)n}a_2 \\ -w^{-2n}a_2 & -w^{-1n}a_1 & \lambda - a_0 & \cdots & -w^{(N-3)n}a_3 \\ \vdots & \vdots & \vdots & \ddots & \vdots \\ -w^{-(N-1)n}a_{N-1} & -w^{-(N-2)n}a_{N-2} & -w^{-(N-3)n}a_{N-3} & \cdots & \lambda - a_0 \\ \end{pmatrix} = 0 $$

これは、$a' = (a_0, w^{-1n}a_1, w^{-2n}a_2,\dots,w^{-(N-1)n}a_{N-1})^\top$とおくと$\Phi (a')$の固有方程式である。$\Phi (a)$の固有値の１つに$a_0 + \cdots + a_{N - 1}$があったから、$\Phi (a')$の固有値の１つに
$$ a_0 + w^{-1n}a_1 + w^{-2n}a_2 + \cdots w^{-(N-1)n}a_{N-1} $$
がある。したがって、$\Phi (a)$の$N$個の固有値
$$ \lambda_n = a_0 + w^{-1n}a_1 + w^{-2n}a_2 + \cdots + w^{-(N-1)n}a_{N-1} = \mathcal{F}(a)[n] $$
が得られた。各$\lambda_n$に属する固有ベクトル$v_n$は
$$ \Phi (a) v_n = \lambda_n v_n $$
により、定数倍の違いを除いて
$$ v_n = \frac{1}{N} (1, w^{-(N-1)n}, w^{-(N-2)n}, \dots, w^{-1n})^\top = \frac{1}{N} (1, w^{1n}, w^{2n}, \dots, w^{(N-1)n})^\top $$
である。$\{ v_0, \dots, v_{N - 1}\}$は線形独立なので、行列$(v_0\ \cdots\ v_{N - 1})$で$\Phi (a)$は対角化できる。ところが、$(v_0\ \cdots\ v_{N - 1}) = W^{-1}$なので
$$ W^{-1} \Lambda W = A $$
である。ただし
$$ \Lambda = \begin{pmatrix} \lambda_0 & 0 & \cdots & 0 \\ 0 & \lambda_1 & \cdots & 0 \\ \vdots & \vdots & \ddots & \vdots \\ 0 & 0 & \cdots & \lambda_{N -1} \\ \end{pmatrix} $$
である。

さて
$$ a * b = \Phi (a) b = W^{-1} \Lambda W b $$
だから、左辺に$W$を掛けて
$$ W(a * b) = \Lambda W b = \left\{ \lambda_n \mathcal{F}(b)[n] \right\}_{n = 0}^{N - 1} = \left\{ \mathcal{F}(a)[n] \cdot \mathcal{F}(b)[n] \right\}_{n = 0}^{N - 1} = \mathcal{F}(a) \cdot \mathcal{F}(b) $$
である。よって次式が成り立つ。
$$ \mathcal{F}(a * b) = \mathcal{F}(a) \cdot \mathcal{F}(b) $$