Double Sparsity: Learning Sparse Dictionaries for Sparse Signal Approximation
12-14是Ron Rubinstein, Student Member, IEEE, Michael Zibulevsky, and Michael Elad, Senior Member, IEEE. 2010.2.10
字典分两种，一种是隐性字典，implicit dictionary，这种主要是由它们的算法表现出来的，而不是矩阵结构，比如wavelet，curvelet，contourlet，等等。另一种是通过机器学习来从样本中获取字典，这种字典表现为一种显性矩阵，explicit matrix，而算法是用来适应矩阵的，比如PCA，GPCA，MOD，K-SVD等等，这种字典的好处在于比前一种灵活，表现也好，坏处就是耗费时间和运算资源，另外复杂的约束限制了字典的大小以及需要处理的信号的维度（所以论文提出的这个算法最后用3D图像去噪来表现优越性）。
本文提出的方法跨越了这两种字典的鸿沟。之前存在的算法，一种是正交基的归一化组合，这种方法通过块协调松弛（Block-coordinate-relaxation BCR）可以稀疏表发，并且算法简单有效（有效是指的是字典收敛得快？），但是缺点是字典结构太严格了，并且表现不好。一种是半多层次结构算法，硬性地将子字典排列成一种稀疏的形式，本文的方法就是吸收了这种稀疏字典的形式。还有一种是Signature字典，这种字典来源于一个紧致的Signature图像，图像的没一个子块构成了字典的一个原子。这种字典的好处是几乎是translation-invariance，减少过重叠，当用相邻信号块的关系的时候编码很快，但是这种字典的参数很少，每个原子一个系数也导致字典更严格，这篇论文提出的方法就是增加了参数，每个原子的系数1到p之间。
字典的两个主要性质：复杂度和适应性，第一个性质是指操作性，需要多复杂的操作步数，比如OMP等等；第二个性质是指适用性，是否在不同图像上普遍表现好。第二个性质的代表就是小波。
怎样兼顾这两者呢？这就需要一个带参数的字典模型提供足够的自由度。从K-SVD方法提取出来的字典中可以看到，字典本身是有结构的，原子本身是规则的，因此或许可以假设字典本身在某个更基础的字典上是稀疏的。
因此之前的D就可以代换成Fai*A，A是一个稀疏矩阵。Y=Fai*A*X；双稀疏字典的算法就是在已知Y的情况下计算出稀疏矩阵A和稀疏表示X。Fai其实和训练字典一样，随便选个初始化的值，会随着迭代变化，最后变成理想字典，若用最后的Fai做字典，那么稀疏表示是A*X，若用Fai*A做字典，那么稀疏表示是X。
算法解释：大体上就是两次K-SVD的嵌套，如果按照论文的步骤，12-14步是一次K-SVD，只更新了稀疏表示a，没有更新字典的原子；5-15步是一次K-SVD，更新了稀疏表示X，字典的原子更新是通过稀疏表示a的更新实现的。初始化各个值之后，把Fai*A看做一体，用K-SVD求X，然后注意力集中在A的一行上，以及X的对应一列上，计算这一行和这一列的贡献，用K-SVD求这个贡献在Fai上的稀疏表示，求出来的稀疏表示替代了A原来那一行，同时更新X的一列。
