スパースモデリング第12章の辞書学習アルゴリズムをjupyter notebookで実装した。jupyter notebookへのリンク
結果
Barbaraから8x8のパッチ約25000個を抽出し、辞書学習を行った。
初期値とした2次元分離可能DCT辞書
K-SVD法でパッチから学習した辞書
辞書学習によりスパース表現誤差が減少した。
K-SVDアルゴリズム
- 信号事例$Y:n \times M$（nは信号の次元、Mは事例数）
- スパース表現$X:m \times M$（mはスパース表現ベクトルの次元）
- 辞書$A:n \times m$
$k_0$個の要素のみが非ゼロの$x_i$で$y_i$をスパース表現する。
タスク：
\min_{A,\{x_i\}^{M}_{1}} \Sigma_{i=1}^{M} ||y_i-Ax_i|| \text{ subject to } ||x_{i}||_0 \leq k_{0}, 1 \leq i \leq M
初期化：
$k=0$として
- 初期辞書：まず8×11の1次元DCT行列$A_{1D}$を作成した。$k$番目のアトム$(k=1,2,\dots,11)$は、
$a^{1D}_{k}=\cos((i-1)(k-1)\pi/11),(i=1,2,\dots,8)$
である。最初のアトム以外は平均を引き去り、クロネッカー積
$A_{2D} = A_{1D} \otimes A_{1D}$
を用いて初期辞書を生成した。
- 正規化：$A$の列を正規化
メインループ：
$k \leftarrow k+1$として、以下のステップを実行する。
- スパース符号化：追跡アルゴリズムを用いて、以下の解を近似する。
\hat{x_{i}} = \arg \min_{x} ||y_{i} - Ax||_{2}^{2} \text{ subject to } ||x||_{0} \leq k_{0}
そして、$1 \leq i \leq M$についてスパース表現ベクトル$\hat{x}_{i}$を得る。これらを用いて行列$X$を構築する。
- K-SVD辞書更新：以下の手順により、辞書の列を更新し、$A$を得る。
$j_0=1,2,\dots,m$について反復する。
-
アトム$a_{j_{0}}$を用いる事例集合を定義する。$$ \Omega_{j_{0}} = \{ i|1 \leq i \leq M, X[j_{0}, i] \neq 0 \}$$
-
残差行列を計算する。$$ E_{j_{0}} = Y - \Sigma_{j \neq j_{0}} a_{j}x_{j}^{T} $$
-
$E_{j_{0}}$から $\Omega_{j_{0}}$に対応する列だけをとりだし$E_{j_{0}}^{R}$とする。
-
$SVD$を適用し、$E_{j_{0}}^{R} = U \Delta V$とする。そして辞書のアトム$a_{j_{0}} = u_{1}$、その表現ベクトルを$x_{j_{0}}^{R}=\Delta[1, 1]v_{1}^{T}$として更新する。
- 停止条件：もし$||Y - AX||^{2}_{F}$の変化が十分に小さければ終了し、そうでなければ反復する。
出力：
結果$A$を得る。
参考
- M. Elad著、玉木徹訳、スパースモデリング、第12章
- https://github.com/greyhill/pypbip/blob/master/ksvd.py