辞書学習の問題設定

許容誤差を $\epsilon$ として、以下の問題設定で辞書 $A$ とスパース表現ベクトル $\boldsymbol{x}$ を推定する。（許容誤差のことを書籍ではモデル誤差と呼んでいるが、誤差が既知な状況はほぼないのでここでは許容誤差と呼ぶことにする。）

$$ \begin{align} \min _{\boldsymbol{A}, \left\{\boldsymbol{x}_{i}\right\}_{i=1}^{M}} \sum_{i=1}^{M}||\boldsymbol{x}_{i}||_{0} \quad \text { subject to } \quad ||\boldsymbol{y}_{i}-\boldsymbol{A} \boldsymbol{x}_{i}||_{2} \leq \epsilon, 1 \leq i \leq M \end{align} $$

また、ペナルティとスパース性を入れ替えて

$$ \begin{align} \min _{\boldsymbol{A}, \left\{\boldsymbol{x}_{i}\right\}_{i=1}^{M}} \sum_{i=1}^{M}||\boldsymbol{y}_{i}-\boldsymbol{Ax}_{i}||_{2}^{2} \quad \text { subject to } \quad||\boldsymbol{x}_{i}||_{0} \leq k_{0}, 1 \leq i \leq M \end{align} $$

という誤差最小化問題を考える。

$\epsilon=0$ とすると、解の一意性が保証されるらしい（驚き）。

辞書とスパース表現ベクトルを同時に求める問題は行列分解とみることもできる。

K-SVDアルゴリズム

A中の $j_0$ 番目以外の列（辞書の列のことをアトムと呼ぶ）を固定し、 $j_0$ 番目に対応するアトムとそのアトムにかかる係数（スパース表現ベクトル）を更新する。そこで、誤差計算を以下のように分解する。

$$ \begin{align} ||\mathbf{Y}-\mathbf{A} \mathbf{X}||_{F}^{2} &=\left|\left|\mathbf{Y}-\sum_{j=1}^{m} \mathbf{a}_{j} \mathbf{x}_{j}^{\top}\right|\right|_{F}^{2} \\ &=\left|\left|\left(\mathbf{Y}-\sum_{j \neq j_{0}} \mathbf{a}_{j} \mathbf{x}_{j}^{\top}\right)-\mathbf{a}_{j_{0}} \mathbf{x}_{j_{0}}^{\top} \right|\right|_{F}^{2} \end{align} $$

$\mathbf{x}_j^{\top}$ は $\mathbf{X}$ の $j$ 番目の行（列じゃないことに注意）とし、更新ステップで $\mathbf{a}_{j_0}$ と $\mathbf{x}_{j_0}^{\top}$ の両方を更新する。 $j_{0}$ 番目以外は固定しているので、

$$ \begin{align} \mathbf{E}_{j_{0}} = \mathbf{Y}-\sum_{j \neq j_{0}} \mathbf{a}_{j} \mathbf{x}_{j}^{\top} \label{ksvd_error} \end{align} $$

は計算済みとしている。

ここで、\eqref{ksvd_error}を最小化する $\mathbf{a}_{j_0}$ と $\mathbf{x}_{j_0}^{\top}$ は、 $\mathbf{E}_{j_{0}}$ の低ランク近似（ランク１近似）とみることができる。

このことは一見するとわかりにくいが、 $\mathbf{a}_{j_{0}} \mathbf{x}_{j_{0}}^{\top}$ が $\mathbf{Y}$ と同じサイズになっていることに気がつけば難しくない。仮に $\mathbf{Y}_{j_{0}} = \mathbf{Y} - \mathbf{E}_{j_{0}}$ とすれば、 $\mathbf{Y}_{j_{0}}$ を $\mathbf{a}_{j_{0}} \mathbf{x}_{j_{0}}^{\top}$ で近似しているだけだからである。