数列で畳み込みを理解りたい！(with 多項式)
0. はじめに
畳み込み積の解釈をするために, あれこれ考えていたことをまとめただけの記事です. 結構雑ですが許してください. 証明などは一部を除いて与えていません(後日付け足すかも).
1. Notations
- $\mathbb N=\{1,2,3,\ldots\}$: 自然数全体の集合,
$\mathbb N_0:=\mathbb N\cup\{0\}$,
$\mathbb Z$: 整数全体の集合,
$\mathbb Q$: 有理数全体の集合,
$\mathbb R$: 実数全体の集合,
$\mathbb C$: 複素数全体の集合. - $n,m\in\mathbb Z$で$n< m$のとき
\begin{gather} \sum_{k=m}^n:=\sum_{k=n}^m \end{gather}
とする(この記法は主に第4章の定理5で用います).
2. 数列や数列の畳み込みを多項式で考えよう
まずは数列を多項式の係数として埋め込みます(多項式と数列を同一視して, 多項式の積として畳み込み積を考えるのが好き).
- 数列$\{a_n\}_{n=0}^\infty$として
\begin{gather} \sum_{n=0}^\infty a_nx^n \end{gather}
という形の元全体の集合を$\mathbb C[[x]]$とかく. 多項式の和と積を入れた$\mathbb C[[x]]$を形式的べき級数環という. - $\mathbb C((x)):=\mathbb C[[x]][x^{-1}]$を形式的ローラン級数体という(つまり$\mathbb C[[x]]$の$x$による局所化). ここで$a(x)\in\mathbb C((x))$を
\begin{gather} a(x)=\sum_{n=-\infty}^\infty a_nx^n \end{gather}
などとかくとする. また, $(a(x))_n:=a_n$とする. - 多項式の積を畳み込み積という.
形式的ローラン級数体$\mathbb C((x))$の元は, 「$n< N$なら$a_n=0$」となる$N\in\mathbb Z$を持つある数列$\{a_n\}_{n=-\infty}^\infty$と対応します.
多項式の積を観察すると,
\begin{gather}
a(x)b(x)=\sum_{n=-\infty}^\infty \left(\sum_{m=-\infty}^\infty a_mb_{n-m}\right)x^n
\end{gather}
となっていて, 係数がちゃんとよく見る畳み込みになっています(各項の係数は有限和になっているので, この積は意味を持ちます).
3. 畳み込みの解釈パート
以下3つの例において, $v(x)=10x^{-1}+10+10x$とします.
\begin{gather}
w(x)=\frac{1}{4}x^{-1}+\frac{1}{2}+\frac{1}{4}x
\end{gather}
とすると,
\begin{gather}
v(x)w(x)=\frac{5}{2}x^{-2}+\frac{15}{2}x^{-1}+\frac{20}{2}+\frac{15}{2}x+\frac{5}{2}x^2.
\end{gather}
この演算結果は, 入力データ$v(x)$をぼかしたものと解釈することができる.
\begin{gather}
w(x)=x^{-1}-x
\end{gather}
とすると,
\begin{gather}
v(x)w(x)=10x^{-2}+10x^{-1}-10x-10x^2.
\end{gather}
この演算結果は, 入力データ$v(x)$のエッジ(変化の大きいところ)を検出していると解釈することができる.
\begin{gather}
w(x)=\sum_{n=0}^\infty\left(\frac{x}{2}\right)^n
\end{gather}
とすると,
\begin{eqnarray}
v(x)w(x)&=&10x^{-1}+15+\sum_{n=1}^\infty\left\{10\left(\frac{1}{2}\right)^{n-1}+10\left(\frac{1}{2}\right)^n+10\left(\frac{1}{2}\right)^{n+1}\right\}x^n\\
&=&10x^{-1}+15+\sum_{n=1}^\infty 35\left(\frac{1}{2}\right)^nx^n.
\end{eqnarray}
この演算結果は, 入力データ$v(x)$が指数的に減衰していく様子だと解釈することができる.
余談: 2Dデータを扱うときは$\mathbb C[x,x^{-1},y,y^{-1}]$を考えれば, これも積が畳み込みになって, ぼかしやエッジの検出が可能となります.
4. 和分差分学
畳み込みを使えば, 総和と差分を数列で表すことができます.
$\Sigma(x),\Delta^+(x),\Delta^-(x)\in\mathbb C((x))$として,
\begin{align}
&\Sigma(x):=\sum_{n=0}^\infty x^n,\\
&\Delta^+(x):=x^{-1}-1,\\
&\Delta^-(x):=x\Delta^+(x)=1-x
\end{align}
と定義する. $\Sigma(x)$を総和, $\Delta^+(x)$を前進差分, $\Delta^-(x)$を後退差分という.
$\displaystyle a(x)\in\mathbb C((x))$とする.
\begin{align}
&\Sigma(x)a(x)=\sum_{n=-\infty}^\infty \left(\sum_{m=-\infty}^n a_m\right)x^n,\\
&\Delta^+(x)a(x)=\sum_{n=-\infty}^\infty(a_{n+1}-a_n)x^n,\\
&\Delta^-(x)a(x)=\sum_{n=-\infty}^\infty(a_n-a_{n-1})x^n.
\end{align}
\begin{gather} \Delta^-(x)\Sigma(x)=\Sigma(x)\Delta^-(x)=1. \end{gather}
$a(x),b(x)\in\mathbb C((x))$として, $a(x)\star b(x)\in\mathbb C((x))$を
\begin{gather}
a(x)\star b(x):=\sum_{n=-\infty}^\infty a_nb_nx^n
\end{gather}
とする. これをアダマール積という(これは多項式の積とは別であることに注意).
記号は少し気持ち悪いですが, この積$\star$は数列$\{a_nb_n\}_{n=-\infty}^{\infty}$を考えているのと同じです.
\begin{gather} \Delta^+(x)(a(x)\star b(x))=(\Delta^+(x)a(x))\star b(x)+(x^{-1}a(x))\star(\Delta^+(x)b(x)). \end{gather}
\begin{gather} \Sigma(x)\{(\Delta^+(x)a(x))\star b(x)\}=x^{-1}(a(x)\star b(x))-\Sigma(x)\{(x^{-1}a(x))\star(\Delta^+(x)b(x))\}. \end{gather}
ここで, 数列に対して離散的なマクローリン展開ができることを示すために, いくつかの記号を定義します.
- $C:\mathbb N_0\times\mathbb N_0\to\mathbb N_0$を二項係数とする. ただし, $n< k$のときに${}_nC_k=0$とする. このとき
\begin{gather} n^{\underline k}:= {}_nC_k\cdot k! \end{gather}
と定義する. これを$n$を底とする下降$k$-乗という. - $n\in\mathbb Z$に対して$\Delta^{(n)}(x)\in\mathbb C((x))$を
\begin{gather} \Delta^{(n)}(x):= \begin{cases} (\Delta^+(x))^n,&(n>0)\\ 1,&(n=0)\\ (-\Delta^-(x))^{-n}&(n<0) \end{cases} \end{gather}
と定義する.
$a(x)\in\mathbb C((x))$に対して
\begin{gather}
a_n=\sum_{k=0}^{n}\frac{(\Delta^{(k)}(x)a(x))_0}{|k|!}|n|^{\underline{|k|}}.
\end{gather}
- $n=0$のときはすぐに分かるので省略.
- $n>0$のとき, $x^{-1}=1+\Delta^+(x)$なので
\begin{eqnarray} x^{-n}&=&(1+\Delta^+(x))^n\\ &=&\sum_{k=0}^n {}_nC_k (\Delta^+(x))^k\\ &=&\sum_{k=0}^n {}_nC_k \Delta^{(k)}(x). \end{eqnarray}
$a_n=(x^{-n}a(x))_0$であるので
\begin{eqnarray} a_n&=&\sum_{k=0}^n {}_nC_k (\Delta^{(k)}(x)a(x))_0\\ &=&\sum_{k=0}^{n} {}_{|n|}C_{|k|} (\Delta^{(k)}(x)a(x))_0. \end{eqnarray} - $n<0$のとき, $x=1-\Delta^-(x)$なので
\begin{eqnarray} x^{-n}&=&(1-\Delta^-(x))^{-n}\\ &=&\sum_{k=0}^{-n} {}_{-n}C_k (-\Delta^-(x))^k\\ &=&\sum_{k=0}^{-n} {}_{-n}C_k \Delta^{(-k)}(x). \end{eqnarray}
$a_n=(x^{-n}a(x))_0$であるので($n<0$に注意)
\begin{eqnarray} a_n&=&\sum_{k=0}^{-n} {}_{-n}C_k (\Delta^{(-k)}(x)a(x))_0\\ &=&\sum_{k=0}^{-n} {}_{|n|}C_{|k|} (\Delta^{(-k)}(x)a(x))_0\\ &=&\sum_{k=0}^{n} {}_{|n|}C_{|k|} (\Delta^{(k)}(x)a(x))_0. \end{eqnarray}
ほぼ観賞用の定理ですね. 使い道がわかる方がいれば教えてください.
