这几天看了稀疏表示的一些文章,对字典学习方法K-SVD[1]查阅了相关资料,特此总结如下,如有理解上不正确的地方,还望指正,本人还处于初学者的状态。
K-SVD是一种迭代算法,是K-means算法的扩展,一般是用来在稀疏表示问题中的字典训练方面。这里的“字典”是一个过完备的矩阵,由其,使得一个信号向量可以表示成字典中原子(字典的列向量)的稀疏线性组合。
K-SVD和K-means方法本质上都属于一种压缩的思想,都主要包含以下两个步骤:
1) 稀疏编码
2) 字典更新
在K-means方法中,K-means 先随机选择K个初始点作为字典,K个初始点就代表K类。然后在每次迭代过程中,稀疏编码阶段:计算数据集中每个数据点与这K个点的距离,距离最短则代表改点属于该类;字典更新:每一类中所有点的均值作为新的字典。
而在K-SVD中,稀疏编码可以采用任何基方法(MP、OMP、BP);字典更新采用SVD奇异值分解。文章原文引用如下:The K-SVD algorithm is an iterative method that alternates between sparse coding of the examples based on the current dictionary and an update process for the dictionary atoms so as to better fit the data, generalizing the K-means algorithm. The update of the dictionary columns is done jointly with an update the sparse representation coefficients related to it, resulting in accelerated convergence.
这里给出文章中对K-SVD方法的描述
以下简要描述该算法:
用数学表达式表示稀疏表示问题,K-SVD即是求解满足以下式子的字典D
其中
1、初始化操作:初始化字典矩阵D,D中原子(列向量)必须是单位向量,
2、重复以下步骤直到满足收敛条件:
1)稀疏编码:这里使用OMP(正交匹配基)来得到每一个信号样本
- OMP算法
本质思想:以贪婪迭代的方法选择字典原子,使得每次迭代的过程中原子与信号最大相关(内积最大),从信号向量减去相关部分得到残差,残差按照上述方法反复迭代,直到迭代次数达到稀疏度K 或者残差小于误差阈值,停止迭代。
OMP算法步骤:
输入:字典矩阵D, 采样信号
输出:稀疏系数
初始化:残差
循环执行步骤1-5:
步骤1:找出残差
步骤2:更新索引集
步骤3:由最小二乘得到
这里给出OMP的Matlab代码,以助于理解
function [A]=OMP(D,X,L); %=============================================% Sparse coding of a group of signals based on a given % dictionary and specified number of atoms to use. % input arguments: % D - the dictionary (its columns MUST be normalized).% X - the signals to represent% L - the max. number of coefficients for each signal.% output arguments: % A - sparse coefficient matrix.%=============================================[n,P]=size(X);[n,K]=size(D);for k=1:1:P, a=[]; x=X(:,k); residual=x; indx=zeros(L,1); for j=1:1:L, proj=D'*residual; [maxVal,pos]=max(abs(proj)); pos=pos(1); indx(j)=pos; a=pinv(D(:,indx(1:j)))*x; residual=x-D(:,indx(1:j))*a; if sum(residual.^2) < 1e-6 break; end end; temp=zeros(K,1); temp(indx(1:j))=a; A(:,k)=sparse(temp);end;return;
2)字典更新:采用逐次更新字典原子向量,通过K次迭代完成字典的一次更新。具体如下:
首先 将 DX表示成D中原子(列)与X中每行的乘积,
然后剥离第k个原子,上述表达式会产生一个“空洞”,字典更新的目的就是寻找新的
[1]http://ieeexplore.ieee.org/xpls/abs_all.jsp?arnumber=1710377&tag=1
联系客服