でかいチーズをベーグルする

でかいチーズはベーグルすべきです。

クロネッカー積とvec作用素とRoth's column lemma

クロネッカー積とvec作用素は見た目簡単なんだけど、各要素のインデックスを書き下すと頭の中こんがらがってわけわからなくなるから一旦整理した。インデックスに関する記事ってほとんどないね。あとそれに関連して Roth's column lemma っていうのが便利なのでちょっと紹介する。

まとめ

クロネッカー積とは

クロネッカー積 - Wikipedia

下の式を見ればひと目で分かるけど、 IxJ 行列 {A} と KxL 行列 {B} から IKxJL 行列を作る。

{
A \otimes B = \left(
\begin{array}{ccc}
a_{11} B & \cdots & a_{1J} B \\
\vdots & \ddots & \vdots \\
a_{I1} B & \cdots & a_{IJ} B
\end{array}
\right)
}

Wikipediaの例を見ると分かりやすい。

https://wikimedia.org/api/rest_v1/media/math/render/svg/130f0defabfa409a56ff89937d40f1656fcb108f

クロネッカー積のインデックス

クロネッカー積の定義は一目見ればすぐ分かるのに、各要素の定義を見ると途端にめんどくさくなる。

{
\left[A \otimes B\right]_{(i-1)K+k,(j-1)L+l} = a_{ij}b_{kl}
}

行のインデックスを見ると、K進数みたいになってるのが分かる。 {A} の行のインデックスが1つ増えるためには、{B} の行のインデックスを一回ずつ辿らなきゃいけないって考えるとそうなることが分かる。列についても同じ。

実験

上式のインデキシングが本当に合ってるのか numpy.kron を使って確かめる。

gist6cf39c77df3bf44fe6ed5aaf98c343cc

vec作用素

vec作用素 - Wikipedia

vec作用素は、以下のように IxJ 行列 {A} の列ベクトルを全て一列に並べて1つの大きな IJ 次元列ベクトルを作る。

{
vec(A) = \left(
\begin{array}{c}
a_{1} \\
a_{2} \\
\vdots \\
a_{J}
\end{array}
\right)
}

例えば、以下のようになる

{
vec\left(
\begin{array}{ccc}
1 & 3 & 2 \\
0 & 7 & 4
\end{array}
\right) = \left(
\begin{array}{c}
1 \\
0 \\
3 \\
7 \\
2 \\
4
\end{array}
\right)
}

vec作用素のインデックス

こっちはクロネッカー積よりは簡単。

{
\left[vec(A)\right]_{(i-1)J+j} = a_{ij}
}

クロネッカー積のときと同じで、J進数みたいになってる。各列ベクトルがJ次元なので、{a_{ij}}{i} が増えるためには {j} を全部辿らなきゃならない。

Roth's column lemma

これが成り立つ。

{
vec(XYZ) = (Z^{T} \otimes X)vec(Y)
}

証明

{X} をIxJ行列、{Y} をJxK行列、{Z} をKxL行列とし、

{W = XYZ}

と置く。{W} は IxL 行列。

{W} の各要素は(とうぜん)以下のように書ける。

{
w_{il} = \sum_{pq} x_{ip}y_{pq}z_{ql}
}

クロネッカー積の要素を考えると

{
\left[Z^{T} \otimes X\right]_{(l-1)I+i,(k-1)J+j} = z_{kl}x_{ij}
}

vec作用素の要素を考えると

{
\left[vec(Y)\right]_{(j-1)K+k} = y_{jk}
}

{
\left[vec(W)\right]_{(i-1)L+l} = w_{il}
}

なので、以下の行列ベクトル積の要素を考えると、

{
\left[(Z^{T} \otimes X)vec(Y)\right]_{(i-1)L+l}
}

{
= \sum_{pq} \left[Z^{T} \otimes X\right]_{(l-1)I+i,(q-1)J+p} \left[vec(Y)\right]_{(p-1)J+q}
}

{
= \sum_{pq}z_{ql} x_{ip} y_{pq}
}

{
= \sum_{pq}x_{ip} y_{pq}z_{ql}
}

{
= w_{il} = \left[vec(W)\right]_{(i-1)L+l}
}

{W=XYZ} だから、証明完了。