字典学习（KSVD ）详解
关于字典学习
对于⼀个事物，我们如何表征它呢？很明显，这个事物是有特征的，或者说，这个事物它是由许多个不同的特征经过⼀定的组合⽽形成的。字典学习的⽬标是提取实物的最本质特征。⽤字典来表征该事物的特征。（⽤尽可能少的资源表⽰尽可能多的知识，这种表⽰还能带来⼀个附加的好处，即计算速度快）
当提取出了事物的特征，这就相当于⼀种降维。
对于如何理解字典学习，我想到这样⼀个例⼦，⽐如⼀堆三维向量，找寻它们的特征，实际上，我们可以⽤三维直⾓坐标系（x，y，z三个单位向量）来表征它们，这三个向量通过组合可以表⽰所有的三维向量，它们就是我们的字典，再搭配上每个三维向量的x，y，z组合⽅式（稀疏编码），也就可以还原成那⼀堆三维向量了。
SVD
在理解KSVD之前，⾸先需要了解的是SVD（奇异值分解）。学习过矩阵理论的同学对SVD肯定是不陌⽣的。
在了解奇异值分解之前，需要了解⼀下特征值分解。所谓特征值分解，是为了提取出⼀个矩阵的特征。特征值，特征向量。这都是我们⽼⽣常谈的问题了。这⾥对于⼀个⽅阵，我们⼜这样的定义：，其中 是 的特征值， 就是我们 的对应 的特征向量。当矩阵可以相似对⾓化时，矩阵 便可以被分解为：
其中 是矩阵 的特征向量组成的矩阵， 是⼀个对⾓阵，其对⾓线上的元素是 的特征值。
⼀个矩阵其实就是⼀个线性变换，当我们将矩阵成以向量之后，其实就是对这个向量进⾏了线性变换。对应我们的特征值分解，分解的 矩阵是⼀个对⾓阵，我们将其中的特征值从⼤到⼩排列，这些特征值对应的特征向量就是描述这个矩阵从主要到次要的变化⽅向。通过特征值分解得到前N个特征向量，那么就对应了这个矩阵最主要的N个变化⽅向。利⽤这前N个变化⽅向，我们就可以近似矩阵，也就是提取这个矩阵的特征。总的来说，特征向量表⽰特征，特征值表⽰特征的重要程度，可以把它在应⽤中当做权重。这种分解⽅法很好，但是也有特别明显的局限性，那就是它只适合⽅阵。
所以下⾯就要引出更适合⼀般矩阵的分解⽅式。也就是奇异值分解⽅法。我们在课上学过，这⾥我们设矩阵 是 的。奇异值分解形式为：
其中是⼀个 的⾣矩阵，其⾥⾯的向量是相互正交的，我们称它们为做左奇异向量； 是⼀个 的矩阵，只有对⾓线上的元素⾮零，这些值就是我们的奇异值， 是⼀个 的矩阵，和⼀样，它也是⾣矩阵，⾥
⾯的向量也是互相正交的，称为右奇异向量。我们将矩阵 的转置乘上它⾃⼰，便会得到⼀个⽅阵，⽤这个⽅阵来求特征值：
这⾥的 就是右奇异向量，
同理 是我们的左奇异向量。我们这⾥的 就是奇异值。在矩阵中，我们让它以从⼩到⼤的顺序排列。在⼤多数情况下，我们会得到很好的结果，就是少部分的奇异值的和占了全部奇异值的和的⼤多数，那么我们就可以⽤前 个奇异值来近似的描述矩阵。
对于⼀个矩阵，我们可以选取 的前 列， 的前 个奇异值， 的前 ⾏，它们分别相乘累加的结果就可以近似表⽰我们的 矩 阵，这不仅是⼀种近似，也相当于⼀种降维。
字典学习
A Ax =λx λA x A λA A =Q ΛQ −1
Q A ΛA ΛA m ∗n A =U ΣV T
U m ∗m Σm ∗n V T n ∗n A A Av =T i λv i i
v i σ=i λi
新闻的时效性u =i σi
Av i
采取措施英文
v i σt U t Σt V T t A铁木山
字典学习主要是将原始样本 给分解中字典矩阵 和稀疏码矩阵 ，这⾥的稀疏码 ⾃然是⼗分稀疏，数据量⽐较少。字典 ⾥便存储了原始样本 中的特征，⽽稀疏码则是⽤表⽰原始样本使⽤特征来组合成⾃⼰的⽅式。
理想情况是
当 远⼩于 与 时， 和 的维度会远低于原来的 。当我们把矩阵 的看做列向量形式 ，然后
这⾥ 就是Y中的第
列向量，我们可以⽤⼀个⽰意图来理解。
（图⽚来源Network Spar Reprentation: Decomposition, Dimensionality-Reduction and Reconstruction）
求解过程
为了得到 和 ，这⾥需要进⾏求解。这⾥提出⼀个优化问题：
该优化问题就是在约束条件 的零范数尽量⼩的情况下，原矩阵与分解的字典矩阵和稀疏码矩阵乘积的差值的矩阵⼆范数最⼩，此时的的字典矩阵和稀疏码矩阵 是多少。
说⽩了就是，稀疏码矩阵⽐较稀疏的情况下，追求 和 差值最⼩(可以以通过 来还原出)，求 和 。（这⾥可以把⽬标函数和约束函数调换位置求解，本质上没有什么区别，只是这⼀种更容易理解）
然后就是如何求解这个优化问题了，这⾥的求解思路是对字典矩阵的每⼀列和稀疏码矩阵的每⼀⾏来进⾏更新，多次迭代，从⽽最终实现 与 的求解。
Y D X X D Y Y =m ∗n D ∗m ∗s X s ∗n
s m n D X Y X s ∗n (x ,x ...x )12n Y =D ∗(x ,x ...x )=12n D ∗x ，D ∗1x ，...，D ∗2x n
单刀赴会
分分操在线观看D ∗x i i D X min Y −DX ,s .t .∀i ,x ≤D ,X ∥∥F 2
∥i ∥0εx i D X Y DX DX Y D X D X
老是掉头发什么原因女
这⾥假设是在迭代过程中的某⼀步，字典矩阵和稀疏矩阵都是有的，只是还不是最终结果。那么此时假设要更新的是字典的第i列和稀疏矩阵的第i⾏。优化⽬标公式是上⾯提到过的
这⾥需要对该公式进⾏变形，⾸先将 写成列向量乘以⾏向量形式（为什么这样写呢，因为我们这⾥要更新的就是字典的第i列和稀疏矩阵的第i⾏）。从⽽，优化⽬标公式变成了
然后将要更新的 抽取出来，公式变成了
此时将前⾯两项合并，则就得到了这样⼀个式⼦
此时优化问题就变成了这个。来分析⼀下这个式⼦，⾸先 是⼀个矩阵， 也是⼀个矩阵，它们是同维度的；然后 是和 毫不相关的，因为它并没有计算有关 的值。
这⾥我们可以这样理解： 是字典矩阵乘以稀疏码矩阵，就是我们恢复的结果，那么 就是原始矩阵与我们恢复矩阵的误差。⽽这个误差项再减去 就是不考虑字典矩阵第⾏和稀疏码矩阵第 ⾏的误差。当执⾏更新字典矩阵第 ⾏和稀疏码矩阵第 ⾏时，更新的标准是，⽤新的 去弥补其他⾏列造成的误差。（有点贪⼼的感觉）
（这⾥我写的不是很清楚，即使看了⽰意图可能也不是很理解，也有⼩伙伴问这⾥，为什么要将Xi中的⾮零元素提取出来形成⾏的Xi’，并构建新的Ei’呢？所以我在⽂章末尾进⾏了补充，该补充内容建议在阅读完全⽂之后对此处抱有疑惑再阅读，当然，如果理解了也可以不读）
然后我们的优化⽬标公式就变成了
对这个式⼦进⾏求解。
这个步骤的意义在于什么呢？在更新稀疏码第 ⾏时，选择继承之前该⾏稀疏码的稀疏性，本次更新我们只更新这个稀疏码的⾮零元素。这样就保证了⼀个什么问题呢，就是之前是零的元素在更新之后⼀定还是零，之前⾮零的元素呢，这就不好说，可能继续⾮零，也可能为零，这要取决于计算结果。
总之，这⾥提取⾮零元素与⾮零列，就保证了稀疏码只会朝着不变或者更稀疏的⽅向发展，⽽不会更稠密。然⽽，这也是有问题的，你只更新⾮零元素，虽然提取除了 ，但它和 ，是不⼀样的，⽆论你最后求得的 有多么解决 ，它和 的误差始终存在，⽆法解决。这就是保证了稀疏性，⽽损失了准确性，只能寄希望靠更多的迭代次数去弥补。min Y −DX D ,X ∥∥F
DX min Y −d x D ,X ∥∥∥∥∥j =1∑s j j ∥∥∥∥∥F
d ,x i i min Y −d x −d x D ,X ∥∥∥∥∥∥j =1,j =i
解读西游记
∑s j j i i ∥∥∥∥∥∥F min E −d x D ,X ∥i i i ∥F
E i d ,x i i E i d ,x i i i DX Y −DX d ,x i i i i i i d ,x i i min E −d x D ,X ∥∥i ′i i ′∥∥F
2i E i ′
E i d x i i ′E ;i ′E i
之后就是来求解
这是⼀个最⼩⼆乘问题，也就是你只能找 去逼近 ，⽽⽆法直接求出其结果。这⾥就采⽤SVD（奇异值分解，前⾯讲的终于派上⽤场了）来求解。基础美
求解的步骤就是将 进⾏奇异值分解，得到
然后取 的第⼀列作为新的 ，⽽ 乘积结果的第⼀⾏作为新的 （其实就是 的主对⾓线第⼀个元素乘以的i第⼀⾏（这⾥ 中的奇异值按从⼤到⼩顺序来排列））。
⾄于为什么这样取呢？这在矩阵理论中是叫做秩⼀逼近。对于 ，我们可以将其表⽰如下即分解成k个⼩矩阵，它们分别是 的第 ⾏和 的第 个奇异值和 的第 个列向量的成绩，它们是同维度的矩阵。
同时因为奇异值分解的性质， 是相互正交的，同样， 是相互正交的，所以我们在计算 的 范数的平⽅时，便会有这样⼀个结果
可以得到这样⼀个结果，因为 中的奇异值是从⼤到⼩排列，⽽ 占据了 的⼤部分能量，所以⽤第⼀个⼩矩阵来近似原矩阵会
让误差尽可能⼩，这样也能达到⽐较好的逼近效果。同时，这个⼩矩阵已经为我们分解好了 ，所以我们选择这样的⽅式来进⾏求解。
⾄此，以上便是求解的全部过程。
不过还存在⼀个问题，就是我们假设更新时建⽴在字典和稀疏码已经存在情况下，那么第⼀次迭代时
字典怎么办呢。我们可以采⽤对原始矩阵直接进⾏奇异值分解，取左歧义矩阵的前 列作为字典，⽽稀疏码甚⾄可以选择全是1的矩阵，⼀开始误差较⼤，反正迭代次数够的话也是可以解决的。
补充
这⾥接着上⾯解释为什么要将Xi中的⾮零元素提取出来形成⾏的Xi’，并构建新的Ei’来进⾏求解的问题。
答⽈：
这⾥是假设是某⼀次迭代更新字典的某⼀列和稀疏码某⼀⾏时，你现在的稀疏码假设是[0,0,1,0,1,1]，现在你要对残差Ei来进⾏奇异值分解，⽤最⼤能量来逼近对吧，但如果你直接对Ei进⾏分解，你怎么保证你的稀疏码更稀疏呢，⽆法保证，你可能会得到[1,2,3,1,1,1]这样的稀疏码，这种稀疏码⽐之前的还更离谱，⼀点都不稀疏，我们进⾏字典学习的⽬的有⼆，⼀是为了使分解的结果逼近原始样本，⼆是让稀疏码尽量稀疏，显然现在的更新⽆法满⾜我们的⽬的。所以我们采取这样⽅式，对于稀疏码[0,0,1,0,1,1]，为了保证之后更新的稀疏码往更稀疏的⽅向⾛，我们把其中⾮零元素提取出来[0,0,1,0,1,1]就提取出[1,1,1]，也就是第2,4,5列，对应的Ei也提取出2,4,5列形成Ei’，那么此时再奇异值分解，得到的新稀疏码假设是[a,b,c]，那么我们来更新稀疏码，就是[0,0,a,0,b,c]，（原来的0不动，只更新⾮零元素），那么⽆论a,b,c为何值，我们的这⾏稀疏码的稀疏程度都不会越更新越差，只会往稀
疏性越好或不变的⽅向⾛。
参考资料min E −d x D ,X ∥∥i ′i i ′∥∥F
2d ,x i i ′E i ′E i ′E =i ′U ΣV T
U d i ΣV T x i ′ΣV T ΣE =i ′
U ΣV T E =i ′U ΣV =T σu v +111T ...+σu v k k k T
U i Σi V T i u ,u ...u 12m v ,v ...v 12n E i F E =∥∥i ′∥∥F 2σu v +12∥∥11T ∥∥...σu v =k 2∥∥k k T ∥∥σ+12...σk
2Σσ12E ∥∥i ′∥∥F 2
u v k k T k
