最优方向法（MOD）

算法描述

求解模型：

\min\sum\limits_i\|x_i\|_0 \quad \mathrm{s.t.} \; \|Y-DX\|^2_F \leq \varepsilon

或

\min\|Y-DX\|^2_F \quad \mathrm{s.t.} \; \sum\limits_i\|x_i\|_0 \leq T_0

MOD（Method of Optimal Direction）是早期的基于样本学习的字典学习算法. 设目标函数中$X$已知，信号的误差定义如下：

\|E\|^2_F = \|Y - DX\|^2_F

MOD算法更新字典的策略就是实现表征误差最小化，所以公式两端针对$D$求偏导，会推到出(Y - DX)X^{\mathrm{T}} = 0，整个字典的更新过程如下：

D^{n + 1} = Y (X^n)^{\mathrm{T}} \cdot (X^n(X^n)^{\mathrm{T}})^{-1}

一般MOD算法需要几十次迭代即可收敛是一个比较可行的方法。缺点在于运算中需要对矩阵求逆，造成计算量过大.

流程描述

输入：训练样本集X = \{x_i\}^N_{i=1}

输出：字典D \in \mathbb{R}^{n \times m} (m > n)

初始化：随机构造一个字典初值D^{(0)} \in \mathbb{R}^{n \times m}，并进行列归一化，迭代次数J=1

循环直到满足迭代终止条件

1. 求解稀疏系数：\min\sum\limits_i\|x_i\|_0 \quad \mathrm{s.t.} \; \|Y-DX\|^2_F \leq \varepsilon
2. 更新字典：D^{J+1}=\arg\min \|Y - DX\|^2_F = D^{n + 1} = Y (X^n)^{\mathrm{T}} \cdot (X^n(X^n)^{\mathrm{T}})^{-1}
3. J=J+1

迭代结束