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

はじめに

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

記号の約束

長さ$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)=\left(\begin{array}{cccc}{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}\\ ⋮& ⋮& \ddots & ⋮\\ 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{array}\right)$$

$w=e^{i\frac{2\pi }{N}}$とおくともう少し見た目がきれいになる。
$$W=\left(\begin{array}{cccc}{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}\\ ⋮& ⋮& \ddots & ⋮\\ w^{-0\cdot (N-1)}& w^{-1\cdot (N-1)}& \cdots & w^{-(N-1)\cdot (N-1)}\end{array}\right)$$

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

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

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

畳み込み定理

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

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

実際に成り立つことを確認しよう。$n=0,\dots ,N-1$を１つとる。$\sum$の順序は勝手に交換して良いから
$$\begin{array}{rl}\mathcal{F}(a\ast b)[n]& =\sum _{k=0}^{N-1}(a\ast b)[k]e^{-i\frac{2\pi }{N}kn}\\ & =\sum _{k=0}^{N-1}(\sum _{l=0}^{N-1}a[l]b[k-l])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{array}$$
と変形できる。ここで、$\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{array}{rl}\mathcal{F}(a\ast 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{array}$$
となる。すべての$n=0,\dots ,N-1$についてこれが成り立つから、確かに
$$\mathcal{F}(a\ast b)=\mathcal{F}(a)\cdot \mathcal{F}(b)$$
が確認できた。

巡回畳み込みと固有分解

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

そこで、${\phi }_a$の標準基底に関する表現行列を考える。$e_i$を第$i$項が$1$の単位ベクトルとすると
$$\begin{array}{rl}{\phi }_a(e_i)& =a\ast e_i\\ & ={\{\sum _{k=0}^{N-1}a[k]e_i[n-k]\}}_{n=0}^{N-1}\\ & ={\{a[n-i]\}}_{n=0}^{N-1}(\because n-k\equiv i\mathrm{mod}N⟺k\equiv n-i\mathrm{mod}N)\\ & =(a[0-i],a[1-i],\dots ,a[(N-1)-i]{)}^{\mathrm{\top }}\end{array}$$
だから
$$\begin{array}{rl}{\phi }_a(e_0)=a\ast e_0& =(a_0,a_1,a_2,\dots ,a_{N-1}{)}^{\mathrm{\top }}\\ {\phi }_a(e_1)=a\ast e_1& =(a_{N-1},a_0,a_1,\dots ,a_{N-2}{)}^{\mathrm{\top }}\\ {\phi }_a(e_2)=a\ast e_2& =(a_{N-2},a_{N-1},a_0,\dots ,a_{N-3}{)}^{\mathrm{\top }}\\ & ⋮\\ {\phi }_a(e_{N-1})=a\ast e_{N-1}& =(a_1,a_2,a_3,\dots ,a_0{)}^{\mathrm{\top }}\end{array}$$
であり、${\phi }_a$の表現行列$\mathrm{\Phi }(a)$は次のようになる。
$$\mathrm{\Phi }(a)=\left(\begin{array}{ccccc}{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\\ ⋮& ⋮& ⋮& \ddots & ⋮\\ a_{N-1}& a_{N-2}& a_{N-3}& \cdots & a_0\end{array}\right)$$

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

ここで、唐突ではあるが$\mathrm{\Phi }(a)$を対角化しよう。固有方程式は次のとおりである。
$$\det (\lambda E-\mathrm{\Phi }(a))=\det \left(\begin{array}{ccccc}\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\\ ⋮& ⋮& ⋮& \ddots & ⋮\\ -a_{N-1}& -a_{N-2}& -a_{N-3}& \cdots & \lambda -a_0\end{array}\right)=0$$

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

ここで第１列に$w^{0n}$、第２列に$w^{1n}$、第３列に$w^{2n}$……を掛ける。ただし$n=0,\dots ,N-1$である。すると
$$\det \left(\begin{array}{ccccc}{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)\\ ⋮& ⋮& ⋮& \ddots & ⋮\\ w^{0n}(-a_{N-1})& w^{1n}(-a_{N-2})& w^{2n}(-a_{N-3})& \cdots & w^{(N-1)n}(\lambda -a_0)\end{array}\right)=0$$
である。

次に、第１行に$w^{-0n}$、第２行に$w^{-1n}$、第３行に$w^{-2n}$……を掛ける。
$$\det \left(\begin{array}{ccccc}\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\\ ⋮& ⋮& ⋮& \ddots & ⋮\\ -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{array}\right)=0$$

これは、$a^{\prime }=(a_0,w^{-1n}{a}_1,w^{-2n}{a}_2,\dots ,w^{-(N-1)n}{a}_{N-1}{)}^{\mathrm{\top }}$とおくと$\mathrm{\Phi }(a^{\prime })$の固有方程式である。$\mathrm{\Phi }(a)$の固有値の１つに$a_0+\cdots +a_{N-1}$があったから、$\mathrm{\Phi }(a^{\prime })$の固有値の１つに
$$a_0+w^{-1n}{a}_1+w^{-2n}{a}_2+\cdots w^{-(N-1)n}{a}_{N-1}$$
がある。したがって、$\mathrm{\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$は
$$\mathrm{\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}{)}^{\mathrm{\top }}=\frac{1}{N}(1,w^{1n},w^{2n},\dots ,w^{(N-1)n}{)}^{\mathrm{\top }}$$
である。$\{v_0,\dots ,v_{N-1}\}$は線形独立なので、行列$(v_0\cdots v_{N-1})$で$\mathrm{\Phi }(a)$は対角化できる。ところが、$(v_0\cdots v_{N-1})=W^{-1}$なので
$$W^{-1}\mathrm{\Lambda }W=A$$
である。ただし
$$\mathrm{\Lambda }=\left(\begin{array}{cccc}{\lambda }_0& 0& \cdots & 0\\ 0& {\lambda }_1& \cdots & 0\\ ⋮& ⋮& \ddots & ⋮\\ 0& 0& \cdots & {\lambda }_{N-1}\end{array}\right)$$
である。

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