算法描述
求解模型:
[minsumlimits_i|x_i|_0 quad mathrm{s.t.} ; |Y-DX|^2_F leq varepsilon
]
或
[min|Y-DX|^2_F quad mathrm{s.t.} ; sumlimits_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 imes m} (m > n))
初始化:随机构造一个字典初值(D^{(0)} in mathbb{R}^{n imes m}),并进行列归一化,迭代次数(J=1)
循环直到满足迭代终止条件
- 求解稀疏系数:(minsumlimits_i|x_i|_0 quad mathrm{s.t.} ; |Y-DX|^2_F leq varepsilon)
- 更新字典:(D^{J+1}=argmin |Y - DX|^2_F = D^{n + 1} = Y (X^n)^{mathrm{T}} cdot (X^n(X^n)^{mathrm{T}})^{-1})
- (J=J+1)
迭代结束