字典学习与压缩感知的关系

    在压缩感知中，我们面临的信号求解问题是$Y=A\times\theta$Y=A×θ，通过已知的观测向量或者观测矩阵$Y$Y(多向量拼接)和已知的传感矩阵$A$A求解未知的 $\theta$θ ，这个A矩阵由于是降采样观测，故为扁矩阵，造成了这个问题是一个解欠定性方程组的问题，即变量个数大于方程个数，通过匹配追踪类算法可以求解。

    在字典学习中，同样面临的问题是$Y=A\times\theta$Y=A×θ,只不过目前是只知道 $Y$Y，要求两个未知数 $A$A 和 $\theta$θ,这个问题相较于压缩感知的求解问题就相对复杂了一些，但是这个问题出现的时间要早于压缩感知，在最初OMP和MP等算法也是服务于稀疏编码的，而不是应用于压缩感知，这个问题本质上也就转化成了找到一个矩阵A，再找到一个权重向量（或矩阵）使得该权重矩阵中的列向量中的非零元素最少，就是一个有限制条件的矩阵分解问题。

     目前笔者还处于该方向的初级入门阶段，接触到了两种网上及书上提及比较多的字典构造方法，一个是MOD（method of optimal directions）最优方向法，另一个是K-SVD，其二者结构相同都是采用了坐标交替下降迭代算法，即固定一个A后更新X，在固定X后更新A，以此交替前进，直到结果收敛为止，其二者对于A矩阵中的原子更新方式不同，以下分别叙述。

MOD字典学习步骤

输入： 待分析数据 $Y$Y。
输出： 字典矩阵 $A$A 与权重矩阵 $X$X 。

在此过程中首先明确 $Y_{M \times P}$YM×P​ $为P$为P 个 $M$M 长的待分析数据，字典$A_{M \times T}$AM×T​中为 $T$T 个字典原子，权值矩阵$W_{T \times P}$WT×P​为产生的P个T长的数据结果，$T>M$T>M，但是 $T$T 的稀疏度远小于 $M$M 。为保证训练效果和训练字典为一个扁矩阵（超完备），最好是 $P$P 大于 $T$T 。

初始化
迭代计数变量初始化为0，初始化原子信号矩阵$A^0$A0，从 $P$P 个 $y_i$yi​ 中随机选择 $T$T 个作为 $A^0$A0 中的初始原子，此时$W^0$W0为 $0$0 。

迭代过程

1、  首先进行的是根据现有原子矩阵的稀疏编码求解，对 $Y$Y 中的所有列 $y_i$yi​ 分别使用匹配追踪类算法求解,获得了一个跟 $Y$Y同等列数的 $W$W,这个部分与压缩感知中已知观测向量求解原始稀疏向量的思想是一样的，数学求解目标也是相同的，都是求解在最小稀疏度为条件的最小二范数，求得的W在行数上是大于Y的，但是其每一列的稀疏度是小于原始观测数的。
$w_j=OMP(A,y_j,K) \qquad j \in [1,M]$wj​=OMP(A,yj​,K)j∈[1,M]

2、  利用现有求得的稀疏矩阵去更新字典矩阵，其实就是用已知的Y和W去更新A的过程，其数学问题就是抽象成了$argmin||Y-AW^t||^2_F$argmin∣∣Y−AWt∣∣F2​的最小F范数时的A矩阵。这个过程就是求解一个方程数小于未知数个数的欠定性方程组，原理上还是利用最小二乘法或者线性回归的方法解，目前网上参考较多的代码中，Rachel-Zhang大神采用的就是线性回归的方式更新字典矩阵。
最小二乘法的解法就是$A=YW^T(WW^T)^{-1}$A=YWT(WWT)−1
《压缩感知浅析》这本书中对于此处的公式是有错误的。

判断条件后输出

3、  计算残差 $||Y-AW||_2<\sigma$∣∣Y−AW∣∣2​<σ 小于一个预设误差时停止迭代，也可以用新迭代与上一次迭代的差值作为停止条件。

总结
    其算法特点就是交替更新字典矩阵和权重矩阵（稀疏向量矩阵），通过求伪逆实现对欠定性方程组的求解，该算法中一次更新字典的全部信息，更新过程收敛速度较慢，且字典内各列之间存在相互干扰的可能。
这个算法本身思路比较清晰，比较简单。

K-SVD字典学习步骤

    相较于MOD算法，KSVD在字典更新策略上做出了改进，但是本质上依旧是矩阵分解问题，其思想就是逐个考虑原子信号（就是字典中的列称为原子）对数据拟合的额贡献并逐个更新原子信号，在更新字典的同时也更新了稀疏向量。

输入： 待分析数据 $Y$Y。
输出： 字典矩阵 $A$A 与权重矩阵 $X$X 。

初始化
迭代计数变量初始化为0，初始化原子信号矩阵$A^0$A0，从 $P$P 个 $y_i$yi​ 中随机选择 $T$T 个作为 $A^0$A0 中的初始原子，此时$W^0$W0为 $0$0 。

假设我有一个数据集Y，是5个数据长，按列拼接15个数据，即Y的大小为5行15列。从中挑选出10个列组成一个A矩阵作为一个初始矩阵$A^0$A0.

迭代过程

1、  首先进行的是根据现有原子矩阵的稀疏编码求解，对 $Y$Y 中的所有列 $y_i$yi​ 分别使用匹配追踪类算法求解,获得了一个跟 $Y$Y同等列数的 $W$W,这个部分与压缩感知中已知观测向量求解原始稀疏向量的思想是一样的，数学求解目标也是相同的，都是求解在最小稀疏度为条件的最小二范数，求得的W在行数上是大于Y的，但是其每一列的稀疏度是小于原始观测数的。
$w_j=OMP(A,y_j,K) \qquad j \in [1,M]$wj​=OMP(A,yj​,K)j∈[1,M]

利用OMP算法，我设定了一个大于预期的K值来保证迭代次数足够，因为由15个数据，所以对应获得了15个10个数据长的稀疏向量，该向量的稀疏度小于5，此时我有 $Y_{5 \times 15}$Y5×15​，$A_{5 \times 10}$A5×10​，$W_{10 \times 15}$W10×15​。

2、  利用现有的 $W_{10 \times 15}$W10×15​ 再反过来迭代 $A$A ，但是要逐列更新，在当前字典原子中剔除要更新的原子，在稀疏向量中也剔除这一行，然后用剩下的列与稀疏向量矩阵中剩下的行做乘积后加和，此处就是矩阵乘法中列乘行后加和为乘法结果的思想，求出来的就是除了这一列其余原子表示的原信号，然后与原始信号做差，得到残差矩阵。
$E_j=Y-\sum_{j \neq1}^{n} A_jw^T_j$Ej​=Y−j​=1∑n​Aj​wjT​
这个式子中的$w^T$wT为$w$w的行，不是列的转置形式，非常重要，不然维度不对。

3、  问题现在就转化成了已知现有的字典和权重向量，求取单独一个字典中的原子和该原子对应的权重向量。这一个原子和其对应的向量最理想的结果就是完全平掉现在的误差。所以问题变成了$E_1=A_1w^T_1$E1​=A1​w1T​
只需要对$E_j$Ej​ 再做矩阵分解即可，但是！！！！！！
如果直接分解会造成重新获得的$W$W与之前用OMP等算法获得的向量不一样，就有可能造成新生成的向量不稀疏，这是一方面考虑，另一方面是对于W中的向量，只有非零值对计算是有贡献的，所以从提升效率的角度看也可以将非零值单独提取，变成$E'_1$E1′​与$w'_1$w1′​

$E'_1 \approx U\Sigma V^T$E1′​≈UΣVT
该式为向量分解，速度上也会相较于矩阵快很多，虽然计算次数多了，但是剔除了其他列对要求列的影响。最终 $U$U 中的第一列就是$A_1$A1​，第一个特征值与稀疏向量的第一行的乘积就是新的$w_1'$w1′​，再将$w_1'$w1′​的值分别映射到 $w$w中非零值的位置上，最终获得本次迭代中更新的字典原子列和新计算出的一个稀疏向量的行。

判断条件后输出

3、  计算残差 $||Y-AW||_2<\sigma$∣∣Y−AW∣∣2​<σ 小于一个预设误差时停止迭代，也可以用新迭代与上一次迭代的差值作为停止条件。

总结
    其算法特点相对于MOD就是变成了逐步更新，至于K-means算法与之的联系暂时还没有过多了解，先跑跑基础代码，看看运行原理和效果再做补充。