1. k-SVD introduction
1.?????K-SVD usage:
? ? Design/Learn a dictionary adaptively to betterfit the model and achieve sparse signal representations.
2.?????Main Problem:
? ? ? ? ? ? ? ? ?Y = DX
? ? ? ? ? ? ? ? ?WhereY∈R(n*N), D∈R(n*K), X∈R(k*N), X is a sparse matrix.
N is # of samples;
n is measurement dimension;
K is the length of a coefficient.
2. ? ? ? Derivation from K-Means
3.?????? K-Means:
1)???????The sparse representationproblem can be viewed as generalization of the VQ objective.K-SVD can be viewed as generalization of K-Means.
2)???????K-Means algorithm for vectorquantization:
Dictionary of VQ codewords is typically trained using K-Means algorithm.
When Dictionary D is given, each signal is represented as its closestcodeword (under l2-norm distance). I.e.
Yi= Dxi
Where xi= ejis a vector from the trivial basis,with all zero entries except a one in the j-th position.
3)???????VQ的字典訓(xùn)練：
K-Means被視作一個(gè)sparse coding的特例，在系數(shù)x中只有一個(gè)非零元，
MSE定義為：，
所以VQ的問(wèn)題是:
4)???????K-Means 算法實(shí)現(xiàn)的迭代步驟：
1） 求X的系數(shù)編碼
2） 更新字典
3. K-SVD，generalizing the K-Means
4. Objective function ?
5.?????? K-SVD的求解
Iterative solution: 求X的系數(shù)編碼(MP/OMP/BP/FOCUSS),更新字典(Regression).
K-SVD優(yōu)化：也是K-SVD與MOD的不同之處，字典的逐列更新：
假設(shè)系數(shù)X和字典D都是固定的，要更新字典的第k列dk，領(lǐng)稀疏矩陣X中與dk相乘的第k行記做，則目標(biāo)函數(shù)可以重寫為：
? ? 上式中，DX被分解為K個(gè)秩為1的矩陣的和，假設(shè)其中K-1項(xiàng)都是固定的，剩下的1列就是要處理更新的第k個(gè)。矩陣Ek表示去掉原子dk的成分在所有N個(gè)樣本中造成的誤差。
6. ? ? ? 提取稀疏項(xiàng)
? ? 如果在5.中這一步就用SVD更新dk和，SVD能找到距離Ek最近的秩為1的矩陣，但這樣得到的系數(shù)不稀疏，換句話說(shuō)，與更新dk前的非零元所處位置和value不一樣。那怎么辦呢？直觀地想，只保留系數(shù)中的非零值，再進(jìn)行SVD分解就不會(huì)出現(xiàn)這種現(xiàn)象了。所以對(duì)Ek和做變換，中只保留x中非零位置的，Ek只保留dk和中非零位置乘積后的那些項(xiàng)。形成，將做SVD分解，更新dk。
7.總結(jié)
K-SVD總可以保證誤差單調(diào)下降或不變，但需要合理設(shè)置字典大小和稀疏度。
在我的實(shí)驗(yàn)中，隨著字典的增大，K-SVD有整體效果提升的趨勢(shì)，但不一定隨著稀疏度的增大使得整體誤差下降。
8.?????? Reference:
1)???????K-SVD: An algorithm fordesigning overcomplete dictionaries for sparse representation (IEEE Trans. OnSignal Processing 2006)
2)???????From sparse solutions of systemsof equations to sparse modeling of signals and images (SIAM Review 2009 240')
