1、目標：找到一個字典D，使得對于給定的訓練信號集能獲得稀疏表達。具體目標為：

2、具體迭代步驟

（1）第一階段：固定字典 D ，找最好的稀疏矩陣 X 。

此為NP難問題。 給定T0，可以采用任何approximation pursuit method去求解 X。論文采用OrthogonalMatching Pursuit (OMP) algorithms。

（2）第二階段：也是K-SVD與MOD的不同之處，字典D是逐列更新的。

因為矩陣的相乘A*B=A的列向量*B的行向量的線性相加。

假設系數X和字典D都是固定的，要更新字典的第k列d_k，令稀疏矩陣X中與d_k相乘的第k行記做，則目標函數可以重寫為：?

上式中，DX被分解為K個秩為1的矩陣的和，假設其中K-1項都是固定的，剩下的1列就是要處理更新的第k個。矩陣E_k表示去掉原子d_k的成分在所有N個樣本中造成的誤差。

如果在這一步就用SVD更新d_k和，SVD能找到距離E_k最近的秩為1的矩陣，但這樣得到的系數不稀疏，換句話說，與更新d_k前的非零元所處位置和value不一樣。那怎么辦呢？直觀地想，只保留系數中的非零值，再進行SVD分解就不會出現這種現象了。所以對E_k和做變換，中只保留x中非零位置的，E_k只保留d_k和中非零位置乘積后的那些項。形成，將SVD分解，更新d_k。

?這里因為X的系數很多是0的，所以我們可以用E的SVD分解出來的E=UWV;W是E的特征向量的根號，很多是0可以得到X。

3、K-SVD總可以保證誤差單調下降或不變，但需要合理設置字典大小和稀疏度。

?

4、在Michael Elad的主頁上有KSVD的matlab代碼下載：http://www.cs.technion.ac.il/~elad/software/。感覺速度還是有點慢。

????A newer version with various improvements, created by Ron Rubinstein, is available in his webpag:

http://www.cs.technion.ac.il/~ronrubin/software.html

?

function [A,x]= KSVD(y,codebook_size,errGoal) %============================== %input parameter % y - input signal % codebook_size - count of atoms %output parameter % A - dictionary % x - coefficent %============================== if(size(y,2)<codebook_size) disp('codebook_size is too large or training samples is too small'); return; end % initialization [rows,cols]=size(y);r=randperm(cols); A=y(:,r(1:codebook_size)); A=A./repmat(sqrt(sum(A.^2,1)),rows,1); ksvd_iter=10; for k=1:ksvd_iter % sparse coding x=OMP(A,y,5.0/6*rows); % update dictionary for m=1:codebook_size mindex=find(x(m,:)); if ~isempty(mindex) mx=x(:,mindex); mx(m,:)=0; my=A*mx; resy=y(:,mindex); mE=resy-my; [u,s,v]=svds(mE,1); A(:,m)=u; x(m,mindex)=s*v';end end end

總結

以上是生活随笔為你收集整理的K-SVD算法的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。