Double?Sparsity: Learning Sparse Dictionaries for Sparse Signal Approximation

12-14是Ron Rubinstein, Student Member, IEEE, Michael Zibulevsky, and Michael Elad, Senior Member, IEEE. 2010.2.10

? ? 字典分兩種，一種是隱性字典，implicit?dictionary，這種主要是由它們的算法表現(xiàn)出來的，而不是矩陣結(jié)構(gòu)，比如wavelet，curvelet，contourlet，等等。另一種是通過機(jī)器學(xué)習(xí)來從樣本中獲取字典，這種字典表現(xiàn)為一種顯性矩陣，explicit?matrix，而算法是用來適應(yīng)矩陣的，比如PCA，GPCA，MOD，K-SVD等等，這種字典的好處在于比前一種靈活，表現(xiàn)也好，壞處就是耗費(fèi)時(shí)間和運(yùn)算資源，另外復(fù)雜的約束限制了字典的大小以及需要處理的信號(hào)的維度（所以論文提出的這個(gè)算法最后用3D圖像去噪來表現(xiàn)優(yōu)越性）。

? ?本文提出的方法跨越了這兩種字典的鴻溝。之前存在的算法，一種是正交基的歸一化組合，這種方法通過塊協(xié)調(diào)松弛（Block-coordinate-relaxation?BCR）可以稀疏表發(fā)，并且算法簡(jiǎn)單有效（有效是指的是字典收斂得快？），但是缺點(diǎn)是字典結(jié)構(gòu)太嚴(yán)格了，并且表現(xiàn)不好。一種是半多層次結(jié)構(gòu)算法，硬性地將子字典排列成一種稀疏的形式，本文的方法就是吸收了這種稀疏字典的形式。還有一種是Signature字典，這種字典來源于一個(gè)緊致的Signature圖像，圖像的沒一個(gè)子塊構(gòu)成了字典的一個(gè)原子。這種字典的好處是幾乎是translation-invariance，減少過重疊，當(dāng)用相鄰信號(hào)塊的關(guān)系的時(shí)候編碼很快，但是這種字典的參數(shù)很少，每個(gè)原子一個(gè)系數(shù)也導(dǎo)致字典更嚴(yán)格，這篇論文提出的方法就是增加了參數(shù)，每個(gè)原子的系數(shù)1到p之間。

? ? 字典的兩個(gè)主要性質(zhì)：復(fù)雜度和適應(yīng)性，第一個(gè)性質(zhì)是指操作性，需要多復(fù)雜的操作步數(shù)，比如OMP等等；第二個(gè)性質(zhì)是指適用性，是否在不同圖像上普遍表現(xiàn)好。第二個(gè)性質(zhì)的代表就是小波。

? ? 怎樣兼顧這兩者呢？這就需要一個(gè)帶參數(shù)的字典模型提供足夠的自由度。從K-SVD方法提取出來的字典中可以看到，字典本身是有結(jié)構(gòu)的，原子本身是規(guī)則的，因此或許可以假設(shè)字典本身在某個(gè)更基礎(chǔ)的字典上是稀疏的。

? ? 因此之前的D就可以代換成Fai*A，A是一個(gè)稀疏矩陣。Y=Fai*A*X；雙稀疏字典的算法就是在已知Y的情況下計(jì)算出稀疏矩陣A和稀疏表示X。Fai其實(shí)和訓(xùn)練字典一樣，隨便選個(gè)初始化的值，會(huì)隨著迭代變化，最后變成理想字典，若用最后的Fai做字典，那么稀疏表示是A*X，若用Fai*A做字典，那么稀疏表示是X。

? ? 算法解釋：大體上就是兩次K-SVD的嵌套，如果按照論文的步驟，12-14步是一次K-SVD，只更新了稀疏表示a，沒有更新字典的原子；5-15步是一次K-SVD，更新了稀疏表示X，字典的原子更新是通過稀疏表示a的更新實(shí)現(xiàn)的。初始化各個(gè)值之后，把Fai*A看做一體，用K-SVD求X，然后注意力集中在A的一行上，以及X的對(duì)應(yīng)一列上，計(jì)算這一行和這一列的貢獻(xiàn)，用K-SVD求這個(gè)貢獻(xiàn)在Fai上的稀疏表示，求出來的稀疏表示替代了A原來那一行，同時(shí)更新X的一列。