文档介绍：K-SVD
基于过完备字典的信号稀疏表示
字典
字典:是许多原子的排序集合。比如一个矩阵D,
大小为n*K. D的每一列表示字典的一个原子。
n为字典原子的维数。
K为字典中原子的个数。
过完备字典:是指字典中原子个数大于原子维数。
即K>n.
稀疏表示
稀疏:比如给定一个向量,若x中绝大多数元素都为0,则x是稀疏的。
稀疏表示:对于给定的一个信号Y,字典D可以表示出Y,其表示系数X,若X 是稀疏的,则X是信号Y在字典D下的稀疏表示。
稀疏表示
已知信号Y,字典D,满足目标函数
L为稀疏度,即α中非零元素的上限。
求解稀疏系数α的问题可以采用OMP,BP等算法求得。
对于其中的初始字典D,可以从变换函数初始一个字典比如DCT字典。
K-SVD
K-SVD:算法的基本思想:首先假设字典D是固定的,用MP、OMP或者BP等算法得到字典D上Y的稀疏表示系数矩阵X,然后根据稀疏表示系数矩阵X,找到更好的字典。
K-SVD
K-SVD是广义的k-means
K-means:在k均值中寻找k个代码的码本C(即聚类中心C1,C2,...Ck),在此码本上,根据最近邻分配法则,对有N个样本的训练集Y,将各样本归类于与之最近的代码所代表的的类中。
对于训练集Y中的每个信号,可以用与之最近的一个代码表示,即为
其中,ej是除了第j列为1外,其他元素都为0.
则C中的Cj可以表示yi,这时的误差最小。(画示例图)
可见在K-means中,只用一个原子Cj来表示yi,同时强制其系数为1.
K-SVD
K-means的目标函数为:
其中,。
K-SVD与k-means聚类算法有着很深的联系,当K-SVD算法中要求每个信号只用一个原子来近似表示时,K-SVD就退化为k-means。
K-SVD:Y=DX
Yϵn*N为信号,
Dϵn*K为码本(字典),
XϵK*N是稀疏表示系数。
K-SVD
其中每一个信号yi用多个代码的线性组合来表示.
K-SVD的目标函数为:
K-SVD
K-SVD用于对字典D的更新,同时更新稀疏系数X。对字典的更新是逐列更新。
比如:要更新字典的第k列, ,令系数矩阵中对应的第k行为(不同于X的第k列的转置,代表的是X的第K行)。
D:n*K
X:K*N
所以K-SVD的目标函数中的误差项为:
K-SVD
假设字典中K-1列是固定的,来更新第k列。Ek代表去掉原子dk后,造成的误差。
对Ek进行奇异值分解更新和。
注意:若直接对Ek进行奇异值分解得到的是不稀疏的(即其大多数元素是非零的)