離散フーリエ変換の代数的性質と一般化
0. はじめに
この記事では, 離散フーリエ変換(DFT)の基本的性質と, 代数的側面, 一般化について解説する.
第2章では, DFTやそれに関連のある概念を定義し, DFTの基本的性質や, DFTと諸概念との関係をみる.
第3章では, DFTが$\mathbb C[\mathbb Z_n]$上に考えられる, 異なる環構造を繋ぐ同型になることをみる.
第4章では, 第2, 第3章でみたDFTの性質から, 一般の群環上でのDFTの構成を試みる.
1. Notations
- $\mathbb N=\{1,2,3,\ldots\}$: 自然数全体の集合,
$\mathbb N_0:=\mathbb N\cup\{0\}$,
$\mathbb Z$: 整数全体の集合,
$\mathbb Q$: 有理数全体の集合,
$\mathbb R$: 実数全体の集合,
$\mathbb C$: 複素数全体の集合. - $\mathbb Z_n:=\mathbb Z/n\mathbb Z=\left\{\overline{0},\dots,\overline{n-1}\right\}$.
- $k$を可換環としたとき, $k$上の単位的可換結合代数のことを単に$k$代数という.
2. 定義と性質
長さ$n$の数列を定義するにあたり, 群環を導入する.
$A$を可換環, $G$を有限群としたときに, 写像$G\to A$の集合を$A[G]$とかき, この集合の元$a:g\mapsto a_g$を形式的に
\begin{gather}
\sum_{g\in G}a_g g
\end{gather}
とかく. $A[G]$の元に対して
\begin{gather}
\sum_{g\in G}a_g g + \sum_{g\in G}b_g g:=\sum_{g\in G}(a_g+b_g) g, \\
\left(\sum_{g\in G}a_g g\right)* \left(\sum_{g\in G}b_g g\right):=\sum_{g,h\in G}a_gb_h gh
\end{gather}
という2つの演算を定義すると, $A[G]$は環となる. $A[G]$を$G$の$A$上の群環という.
群環$A[G]$の元を形式的な和$\displaystyle\sum_{g\in G} a_g g$ として扱う際は係数を$a_g$と表記し、写像$a: G \to A$としての側面を強調する際は$a(g)$と表記することに注意.
- 群環$\mathbb C[\mathbb Z_n]$の元(つまり写像$v:\mathbb Z_n\to\mathbb C$)を長さ$n$の(複素)数列という. $\mathbb C[\mathbb Z_n]$は複素ベクトル空間であり, $\mathbb C[\mathbb Z_n]$には標準内積$(\cdot,\cdot)$が備わっているとする. ここで, 標準内積$(\cdot,\cdot)$は
\begin{gather} (v,w):=\sum_{k\in\mathbb Z_n}v(k) \overline{w(k)} \end{gather}
と定義される. - 群環上に備わっている積$*:\mathbb C[\mathbb Z_n]\times\mathbb C[\mathbb Z_n]\to\mathbb C[\mathbb Z_n]$を巡回畳み込みという.
- 写像$\cdot:\mathbb C[\mathbb Z_n]\times\mathbb C[\mathbb Z_n]\to\mathbb C[\mathbb Z_n]$を
\begin{gather} (v\cdot w)(m):=v(m)w(m) \end{gather}
と定義すると, これは$\mathbb C[\mathbb Z_n]$上の双線型な積となる(これは群環に元から備わっている積とは違うことに注意). この積$\cdot$をアダマール積という.
$k\in\mathbb Z_n$に対して, 写像$\delta_k:\mathbb Z_n\to\mathbb C$を
\begin{gather} \delta_k(m):=\delta_{k,m} \end{gather}
と定義すると, これは長さ$n$の数列である. ただし, $\delta:\mathbb Z_n\times\mathbb Z_n\to\mathbb C$を
\begin{eqnarray} \delta_{i,j}:= \begin{cases} 0, &(i\ne j)\\ 1 &(i=j) \end{cases} \end{eqnarray}
と定義した.
この$\delta_k\in\mathbb C[\mathbb Z_n]$は, 群環の定義で紹介したように, 形式的に
\begin{gather} \sum_{l\in\mathbb Z_n}\delta_{k,l}l=k \end{gather}
とかけるものである.
\begin{gather} (v*w)(m)=\sum_{k\in\mathbb Z_n}v(k)w(m-k). \end{gather}
\begin{eqnarray} v*w&=&\left(\sum_{k\in\mathbb Z_n}v_k k\right)*\left(\sum_{k\in\mathbb Z_n}w_k k \right)\\ &=&\sum_{k,l\in\mathbb Z_n}v_kw_l (k+l)\\ &=&\sum_{k,l\in\mathbb Z_n}v_kw_{l-k}l\\ &=&\sum_{l\in\mathbb Z_n}\left(\sum_{k\in\mathbb Z_n}v_kw_{l-k}\right)l. \end{eqnarray}
この命題により, 群環$\mathbb C[\mathbb Z_n]$上の積$*$が, よく見る畳み込みと同じであることがわかる.
- 写像$\mathcal{F}_n:\mathbb C[\mathbb Z_n]\to\mathbb C[\mathbb Z_n]$を
\begin{gather} \mathcal{F}_n[v](m):=\sum_{k\in\mathbb Z_n}v(k)\exp\left(-\frac{2i\pi km}{n}\right) \end{gather}
と定義すると, これは線型写像になる. 数列$\mathcal{F}_n[v]$を$v$の離散フーリエ変換(DFT)という. - $k\in\mathbb Z_n$に対して, 写像$\tau_{k}:\mathbb C[\mathbb Z_n]\to\mathbb C[\mathbb Z_n]$を
\begin{gather} \tau_{k}[v]:=k*v\quad\left(=\sum_{m\in\mathbb Z_n}v_{m-k}m\right) \end{gather}
と定義すると, これは線型写像になる. この写像をシフト作用素という. - 写像$\mathcal{R}_n:\mathbb C[\mathbb Z_n]\to\mathbb C[\mathbb Z_n]$を
\begin{gather} \mathcal{R}_n[v](m):=v(-m) \end{gather}
と定義すると, これは線型写像になる. この写像を時間反転, またはパリティ演算子という.
厳密には, DFTを定義する際に用いた関数
\begin{gather} \mathbb Z_n\times\mathbb Z_n\ni (\overline k,\overline l)\mapsto \exp\left(-\frac{2i\pi kl}{n}\right)\in\mathbb C\tag{1} \end{gather}
がwell-definedであることを確かめなければならない($\exp$の中身の$k,l$が代表元を取っていることがわかりやすいように, $\mathbb Z_n$の元を$\overline k, \overline l$などと表記している). 実際, $a,b\in\mathbb Z$として, 代表元の取り換えとして$k'=k+an$, $l'=l+bn$を考えると,
\begin{eqnarray}
\exp\left(-\frac{2i\pi k'l'}{n}\right)&=&\exp\left(-\frac{2i\pi (k+an)(l+bn)}{n}\right)\\
&=&\exp\left(-\frac{2i\pi (kl+aln+bkn+abn^2)}{n}\right)\\
&=&\exp\left(-\frac{2i\pi kl}{n}-2i\pi(al+bk+abn)\right)\\
&=&\exp\left(-\frac{2i\pi kl}{n}\right)
\end{eqnarray}
となり, 式$(1)$のwell-defined性は示される. この記事では, 同値類$\overline k\in\mathbb Z_n$と代表元$k\in\mathbb Z$を, 文脈に応じて同一視する.
$k\in\mathbb Z_n$に対して, 写像$e_k:\mathbb Z_n\to\mathbb C$を
\begin{gather} e_k(m):=\exp\left(-\frac{2i\pi km}{n}\right) \end{gather}
と定義すると, これは長さ$n$の数列である.
$\delta_k$のDFTを計算してみる.
\begin{eqnarray}
\mathcal{F}[\delta_k](m)&=&\sum_{l\in\mathbb Z_n}\delta_{k,l}\exp\left(-\frac{2i\pi lm}{n}\right)\\
&=&\exp\left(-\frac{2i\pi km}{n}\right)\\
&=&e_k(m).
\end{eqnarray}
よって$\mathcal{F}[\delta_k]=e_k$である.
\begin{gather} \sum_{k\in\mathbb Z_n}\exp\left(-\frac{2i\pi kl}{n}\right)=n\delta_{l,\overline0}. \end{gather}
- $l=\overline0$のとき
\begin{gather} \sum_{k\in\mathbb Z_n}\exp\left(-\frac{2i\pi k0}{n}\right)=n. \end{gather} - $l\ne\overline0$のとき
\begin{gather} \sum_{k\in\mathbb Z_n}\exp\left(-\frac{2i\pi kl}{n}\right)=\frac{1-\exp\left(-2i\pi l\right)}{1-\exp\left(-\frac{2i\pi l}{n}\right)}=0. \end{gather}
\begin{gather} \mathcal{F}_n^4=n^2\mathrm{id}_{\mathbb C[\mathbb Z_n]}. \end{gather}
\begin{eqnarray} \mathcal{F}_n^2[v](m)&=&\sum_{k,l\in\mathbb Z_n}v(k)\exp\left(-\frac{2i\pi kl}{n}\right)\exp\left(-\frac{2i\pi lm}{n}\right)\\ &=&n\sum_{k\in\mathbb Z_n}v(k)\delta_{k,-m}\\ &=&nv(-m)\\ &=&n\mathcal{R}_n[v](m).\\ \\ \therefore \mathcal{F}_n^4&=&n^2\mathcal{R}_n^2\\ &=&n^2\mathrm{id}_{\mathbb C[\mathbb Z_n]}. \end{eqnarray}
このことから$\mathcal{F}_n$は逆写像をもち,
\begin{gather}
\mathcal{F}_n^{-1}=\frac{1}{n^2}\mathcal{F}_n^3
\end{gather}
であることがわかる. さらに$\mathcal{F}_n$は固有値として$\pm\sqrt{n},\pm i\sqrt{n}$以外を持ちえないことがわかる.
\begin{gather} \mathcal{F}_n^{-1}[v](m)=\frac{1}{n}\sum_{k\in\mathbb Z_n}v(k)\exp\left(\frac{2i\pi km}{n}\right). \end{gather}
\begin{eqnarray} \mathcal{F}_n^{-1}[v](m)&=&\frac{1}{n^2}\mathcal{F}_n^{3}[v](m)\\ &=&\frac{1}{n}(\mathcal{R}_n\circ\mathcal{F}_n)[v](m)\\ &=&\frac{1}{n}\mathcal{F}_n[v](-m)\\ &=&\frac{1}{n}\sum_{k\in\mathbb Z_n}v(k)\exp\left(\frac{2i\pi km}{n}\right). \end{eqnarray}
数列$\mathcal{F}_n^{-1}[v]$を$v$の逆離散フーリエ変換(IDFT)という.
$\displaystyle \frac{1}{\sqrt{n}}\mathcal{F}_n$は$\mathbb C[\mathbb Z_n]$上のユニタリ変換である.
\begin{eqnarray} \left(\frac{1}{\sqrt{n}}\mathcal{F}_n[v],\frac{1}{\sqrt{n}}\mathcal{F}_n[w]\right)&=&\frac{1}{n}\sum_{k\in\mathbb Z_n}\mathcal{F}_n[v](k)\overline{\mathcal{F}_n[w](k)}\\ &=&\frac{1}{n}\sum_{k\in\mathbb Z_n}\left(\sum_{l\in\mathbb Z_n}v(l)\exp\left(-\frac{2i\pi lk}{n}\right)\right)\overline{\left(\sum_{m\in\mathbb Z_n}w(m)\exp\left(-\frac{2i\pi mk}{n}\right)\right)}\\ &=&\sum_{l,m\in\mathbb Z_n}v(l)\overline{w(m)}\left(\frac{1}{n}\sum_{k\in\mathbb Z_n}\exp\left(-\frac{2i\pi (l-m)k}{n}\right)\right)\\ &=&\sum_{l,m\in\mathbb Z_n}v(l)\overline{w(m)}\delta_{l,m}\\ &=&(v,w). \end{eqnarray}
プランシュレルの定理によって
\begin{gather}
(\mathcal{F}_n[v],\mathcal{F}_n[v])=n(v,v)
\end{gather}
であるが, この式をパーセバルの等式という.
\begin{gather} \mathcal{F}_n[v*w]=\mathcal{F}_n[v]\cdot\mathcal{F}_n[w]. \end{gather}
\begin{eqnarray} \mathcal{F}_n[v*w](m)&=&\sum_{k\in\mathbb Z_n}(v*w)(k)\exp\left(-\frac{2i\pi km}{n}\right)\\ &=&\sum_{k\in\mathbb Z_n}\left(\sum_{l\in\mathbb Z_n}v(l)w(k-l)\right)\exp\left(-\frac{2i\pi km}{n}\right)\\ &=&\sum_{l\in\mathbb Z_n}v(l)\exp\left(-\frac{2i\pi lm}{n}\right)\left(\sum_{k\in\mathbb Z_n}w(k-l)\exp\left(-\frac{2i\pi (k-l)m}{n}\right)\right)\\ &=&\left(\sum_{l\in\mathbb Z_n}v(l)\exp\left(-\frac{2i\pi lm}{n}\right)\right)\left(\sum_{k\in\mathbb Z_n}w(k)\exp\left(-\frac{2i\pi km}{n}\right)\right)\\ &=&\mathcal{F}_n[v](m)\mathcal{F}_n[w](m). \end{eqnarray}
\begin{gather} \mathcal{F}_n\circ\tau_{k}[v]=e_k\cdot\mathcal{F}_n[v]. \end{gather}
畳み込み定理より
\begin{eqnarray}
\mathcal{F}_n\circ\tau_{k}[v]&=&\mathcal{F}_n[k*v]\\
&=&\mathcal{F}_n[k]\cdot\mathcal{F}_n[v]\\
&=&e_k\cdot\mathcal{F}_n[v].
\end{eqnarray}
シフト定理の主張の式は
\begin{gather}
\mathcal{F}_n\circ\tau_{k}\circ\mathcal{F}_n^{-1}[v]=e_k\cdot v
\end{gather}
とかきなおすことができるが, これはフーリエ変換が, 基底$\{\delta_{\overline 0},\dots,\delta_{\overline{n-1}}\}$に対してシフト演算子を対角化する作用素であることを主張している.
さらに, シフト演算子$\tau_{k}$の固有値は$e_k({\overline{0}}),\dots,e_k({\overline{n-1}})$ということも直ちにわかる.
3. $\mathbb C[\mathbb Z_n]$の代数構造
$(\mathbb C[\mathbb Z_n],+,\cdot)$は$\mathbb C$代数である.
乗法単位元は$1:\mathbb Z_n\ni m\mapsto 1\in\mathbb C$である. また, 結合則, 交換則, 分配則が成り立つことは容易に確認できる.
\begin{gather} (\mathbb C[\mathbb Z_n],+,\cdot)\cong\mathbb C^n \end{gather}
ただし, $\mathbb C^n$は環の直和の意味で, これは$\mathbb C$の自然な作用(スカラー倍)が定まっているので$\mathbb C$代数である.
\begin{gather}
\mathbb C[\mathbb Z_n]\ni\sum_{k\in\mathbb Z_n}v_k k\mapsto(v_0,\dots,v_{n-1})\in\mathbb C^n
\end{gather}
が$\mathbb C$代数同型となる.
\begin{gather} \mathbb C[\mathbb Z_n]\cong\mathbb C^n. \end{gather}
畳み込み定理より, $\mathcal{F}_n:\mathbb C[\mathbb Z_n]\to(\mathbb C[\mathbb Z_n],+,\cdot)\cong\mathbb C^n$が$\mathbb C$代数同型となる.
畳み込み定理の証明を見ると明らかであるが, DFTは積演算として巡回畳み込みを持つ代数 と, アダマール積を持つ代数の間の同型写像であることがわかる.
4. 一般の群環上のDFT
DFTを一般化するにあたり, 定理10を観察する. 実はこの定理は, $\mathbb C[\mathbb Z_n]$を$n$個の既約表現$(\hat e_{\overline 0},\mathbb C),\dots,(\hat e_{\overline{n-1}},\mathbb C)$に分解できることを主張していると解釈することができる(例4を参照). この, 代数構造を, その既約表現を通じて分解する写像というアイデアをもとに, DFTを一般の群環へと拡張する.
- $A$を可換環, $G$を有限群とする. ある$A$加群上の$G$の表現$\phi:G\to\mathrm{End}(V)$に対して$A[G]$に定まる自然な表現$\hat\phi:A[G]\to\mathrm{End}(V)$を
\begin{gather} \hat\phi\left(\sum_{g\in G}a_gg\right):=\sum_{g\in G}a_g\phi(g) \end{gather}
と定義する. - $A$を可換環, $G$を有限群, $\{(\rho_\lambda,V_\lambda)\}_{\lambda\in\Lambda}$を$A$加群上の$G$の互いに同値でない既約表現全体の集合とする(たとえば$\lambda\ne\mu$ならば$(\rho_\lambda,V_\lambda)$と$(\rho_\mu,V_\mu)$は同値な表現でないとする). 直和表現$\displaystyle\left(\bigoplus_{\lambda\in\Lambda}\hat\rho_\lambda,\bigoplus_{\lambda\in\Lambda}V_\lambda\right)$を考え,
\begin{gather} \mathscr{F}:=\bigoplus_{\lambda\in\Lambda}\hat\rho_\lambda \end{gather}
と定義する. この$\displaystyle\mathscr F:A[G]\to\mathrm{End}\left(\bigoplus_{\lambda\in\Lambda}V_\lambda\right)$のことを群環$A[G]$上の離散フーリエ変換(DFT)という. - $h\in G$に対して$\tau_h:A[G]\to A[G]$を
\begin{gather} \tau_h[a]:=h*a\quad\left(=\sum_{g\in G}a_{h^{-1}g} g\right) \end{gather}
と定義する($*$は$A[G]$上の積であることに注意). この写像をシフト作用素という.
この定義から, $\mathscr F$は代数間の準同型であるが, この性質はまさに畳み込み定理の主張そのものである.
\begin{gather}
\psi:\Im(\mathscr{F})\ni \bigoplus_{\lambda\in\Lambda}\hat\rho_\lambda(v)\mapsto (\hat\rho_\lambda(v))_{\lambda\in\Lambda}\in\prod_{\lambda\in\Lambda}\mathrm{End}(V_\lambda)
\end{gather}
は単射準同型となる.
$\psi$は和とスカラー倍と積を保つので準同型. さらに$\ker(\psi)=0$なので, $\psi$は単射.
\begin{gather}
\psi':\prod_{\lambda\in\Lambda}\mathrm{End}(V_\lambda)\ni (f_\lambda)_{\lambda\in\Lambda}\mapsto \bigoplus_{\lambda\in\Lambda}f_\lambda\in \mathrm{End}\left(\bigoplus_{\lambda\in\Lambda}V_\lambda\right)
\end{gather}
は単射準同型となる.
$\displaystyle(v_\lambda)_{\lambda\in\Lambda}\in \bigoplus_{\lambda\in\Lambda}V_\lambda$は, 直和の定義より有限個の$\lambda\in\Lambda$を除いて$v_\lambda=0$である. これに対して
\begin{gather}
\bigoplus_{\lambda\in\Lambda}f_\lambda((v_\lambda)_{\lambda\in\Lambda})=(f_\lambda(v_\lambda))_{\lambda\in\Lambda}
\end{gather}
を考えると, $f_\lambda$の線形性により有限個の$\lambda\in\Lambda$を除いて$f_\lambda(v_\lambda)=0$である. したがって$\psi'$の像が終域に収まっているので$\psi'$はwell-defined. $\psi'$は和とスカラー倍と積を保つので準同型. さらに$\ker(\psi')=0$なので, $\psi'$は単射.
命題11, 12から$\displaystyle \Im(\mathscr{F})\leqq\prod_{\lambda\in\Lambda}\mathrm{End}(V_\lambda)\leqq\mathrm{End}\left(\bigoplus_{\lambda\in\Lambda}V_\lambda\right)$とみなせる. ただし, $\leqq$は部分代数となっていることを表す.
この記事では, DFTを群環$A[G]$の既約表現の直和表現$\displaystyle\mathscr{F}=\bigoplus_{\lambda\in\Lambda}\hat\rho_\lambda$として定義したが, $A$代数$A[G]$の構造を既約表現に分解する準同型写像として定義する流儀も存在する.
つまり, DFTを写像$\displaystyle\mathscr F':A[G]\to\prod_{\lambda\in\Lambda}\mathrm{End}(V_\lambda)$として,
\begin{gather}
\mathscr F'[v]:=(\hat\rho_\lambda(v))_{\lambda\in\Lambda}\quad(=\psi\circ\mathscr F[v])
\end{gather}
と定義する場合がある. 命題11, 12からもわかるように, いずれの定義も本質的には同じことを述べている.
$\mathbb C$ベクトル空間上の$\mathbb Z_n$の既約表現は$(e_{\overline{0}},\mathbb C),\dots,(e_{\overline{n-1}},\mathbb C)$の$n$個であり, $\mathbb C[\mathbb Z_n]$上のDFT$\displaystyle\mathscr{F}:\mathbb C[\mathbb Z_n]\to\Im(\mathscr{F})(\leqq\prod_{k=0}^{n-1}\mathrm{End}(\mathbb C)\cong\mathbb C^n)$は
\begin{eqnarray}
\mathscr{F}[v]&=&(\hat e_{\overline 0}(v),\dots,\hat e_{\overline{n-1}}(v))\\
&=&\left(\sum_{k\in \mathbb Z_n}v_ke_{\overline 0}(k),\dots,\sum_{k\in \mathbb Z_n}v_ke_{\overline{n-1}}(k)\right)\\
&=&\left(\sum_{k\in \mathbb Z_n}v_k\exp\left(-\frac{2i\pi 0k}{n}\right),\dots,\sum_{k\in \mathbb Z_n}v_k\exp\left(-\frac{2i\pi (n-1)k}{n}\right)\right)\\
&\cong&\sum_{m\in\mathbb Z_n}\left(\sum_{k\in \mathbb Z_n}v(k)\exp\left(-\frac{2i\pi mk}{n}\right)\right)m\\
&=&\mathcal{F}_n[v].
\end{eqnarray}
ただし, 式変形の途中で命題9の同型を用いた.
$\mathcal F_n$は全射なので, この例では$\Im(\mathscr F)\cong\Im(\mathcal F_n)\cong\mathbb C^n$とわかる.
\begin{gather} A[G]/\ker(\mathscr F)\cong\Im(\mathscr F). \end{gather}
$A$代数における準同型定理の帰結である.
この定理は, 定理10を一般の群環で見たときの主張である. このことから, $A[G]$上のDFTを$A[G]/\ker(\mathscr F)$上に誘導すれば, この同型によって逆フーリエ変換(IDFT)を考えることができる.
\begin{gather} \mathscr F\circ\tau_h[a]=\mathscr F[h]\mathscr F[a]. \end{gather}
\begin{eqnarray} \mathscr F\circ\tau_h[a]&=&\mathscr F[h*a]\\ &=&\mathscr F[h]\mathscr F[a]. \end{eqnarray}
これはシフト定理の一般化である.
5. おまけ
今回は$\mathbb C[\mathbb Z_n]$を$A[G]$へと一般化する方向で話を進めましたが, $G$を局所コンパクト群, $\mu$を$G$上のハール測度として
\begin{gather}
L^1(G):=\left\{f:G\to\mathbb C\mathrel{\Bigg|} \int_G |f(g)|d\mu(g)<\infty\right\}
\end{gather}
とすると$L^1(\mathbb Z_n)=\mathbb C[\mathbb Z_n]$なので, $L^1(G)$上の写像としてフーリエ変換を一般化する話もあるそうです. ただ, 測度論や解析的な話が苦手でそこまでの議論を追うことができていませんので, ここでは紹介のみにとどめます.
