稀疏編碼演算法

『壹』 稀疏表示的性質

信號稀疏表示的目的就是在給定的超完備字典中用盡可能少的原子來表示信號，可以獲得信號更為簡潔的表示方式，從而使我們更容易地獲取信號中所蘊含的信息，更方便進一步對信號進行加工處理，如壓縮、編碼等。信號稀疏表示方向的研究熱點主要集中在稀疏分解演算法、超完備原子字典、和稀疏表示的應用等方面。
在稀疏表示理論未提出前，正交字典和雙正交字典因為其數學模型簡單而被廣泛的應用，然而他們有一個明顯的缺點就是自適應能力差，不能靈活全面地表示信號，1993年，Mallat基於小波分析提出了信號可以用一個超完備字典進行表示，從而開啟了稀疏表示的先河，經研究發現，信號經稀疏表示後，越稀疏則信號重建後的精度就越高，而且稀疏表示可以根據信號的自身特點自適應的選擇合適的超完備字典。對信號稀疏表示的目的就是尋找一個自適應字典使得信號的表達最稀疏。
稀疏分解演算法首先是由Mallat提出的，也就是眾所周知的匹配追蹤演算法（Matching Pursuit,MP）演算法，該演算法是一個迭代演算法，簡單且易於實現，因此得到了廣泛的應用。隨後，Pati等人基於MP演算法，提出了正交匹配追蹤演算法（Orthogonal Matching Pursuit,OMP），OMP演算法相較於MP演算法，收斂速度更快。在以後的研究中，為了改進OMP演算法，學者也提出了各種不同的其它演算法，例如：壓縮采樣匹配追蹤（Conpressive Sampling Matching Pursuit,CoSaMP）演算法、正則化正交匹配追蹤（Regularized Orthogonal Matching Pursuit,ROMP）演算法、分段式正交匹配追蹤（Stagewise OMP,StOMP）演算法、子空間追蹤（Subspace Pursuit,SP）演算法等等。
信號稀疏表示的兩大主要任務就是字典的生成和信號的稀疏分解，對於字典的選擇，一般有分析字典和學習字典兩大類。常用的分析字典有小波字典、超完備DCT字典和曲波字典等，用分析字典進行信號的稀疏表示時，雖然簡單易實現，但信號的表達形式單一且不具備自適應性；反之，學習字典的自適應能力強，能夠更好的適應不同的圖像數據，在目前的研究中，常用的學習字典的方法包括：Engan於1999年提出的最優方向（Method Of Optimal Directions,MOD）演算法，該演算法是學習字典的鼻祖，它的字典更新方式簡單，但與此同時，它的收斂速度很慢，在該演算法的基礎上，一些研究人員同時還提出了一些其它的字典學習演算法，如FOCUSS字典學習演算法，廣義PCA（Generalized PCA）演算法等等，Micheal Elad也於2006年提出了基於超完備字典稀疏分解的K-SVD演算法，該演算法相較於MOD演算法，收斂速度有了很大的提高，但是隨著雜訊的逐漸加大，使用該演算法進行去噪後的圖像因紋理細節的丟失會產生模糊的效果。Mairal於2010年提出了一種online字典學習演算法，該演算法速度較快且適用於一些特殊的信號處理，例如視頻信號，語音信號等等 。

『貳』 稀疏自編碼器出自哪個論文

出自AndrewNg教授的教程。
稀疏自編碼器（SparseAutoencoder）可以自動從無標注數據中學習特徵，可以給出比原始數據更好的特徵描述。在實際運用時可以用稀疏編碼器發現的特徵取代原始數據，這樣往往能帶來更好的結果。本文將給出稀疏自編碼器的演算法描述，並演示說明稀疏編碼器自動提取邊緣特徵。
稀疏性可以被簡單地解釋如下。如果當神經元的輸出接近於1的時候我們認為它被激活，而輸出接近於0的時候認為它被抑制，那麼使得神經元大部分的時間都是被抑制的限制則被稱作稀疏性限制。這里我們假設的神經元的激活函數是sigmoid函數。

『叄』 KSVD去噪

      在解釋KSVD去噪原理之前先解釋幾個名詞，首先：

       原子：信號的基本李物構成成分，比如一個長為N的列向量；

       字典：許多原子的排序集合，一個N*T的矩陣，如果T>N（列數大於行數），則為過完備或冗餘字典。信號稀疏之前在壓縮感知學習的時候有介紹過，就是信號的非零值很少，這個概念主要應用與信號處理領域，自然信號中主要是低頻信息，高頻信息大多就是雜訊了，在圖像中應用濾波器濾除高頻成分也就是去噪了。具體怎麼完成，就要依靠下面介紹的KSVD。

       KSVD的目的就是找到最稀疏的稀疏矩陣X，使得原始矩陣（Y）有最稀疏的表示。假設現在有了一個N*T的過完備字典 D，一個要表示的對象y（要還原的圖像），求一套系數x，使得y=Dx，這里y是一個已知的長為N的列向量，x是一個未知的長為T的列向量，解方程。這是一個T個未知數，N個方程的方程組，T>N，所以是有無窮多解，但是針對問題目標我們會給這個方程添加約束條件，比如在圖像去噪中，我們想要x最稀疏，就是非零值最少，這個在已知D和y求解x的過程就是稀疏編碼。

       稀疏編碼求解的模型就是：x = argminxnorm(y − Dx, 2)2,  s.t.norm(x, 1)≤ε。這里又被分為了兩種可能，D已知情況下可以用OMP演算法（大意是先找到D和y最接近的一個原子D(m)，求出合適的系數x(m)，新的y'=D(m) * x(m)，再找下一個最接近的原子，直到找完合適的x）；當D未知時就變成了矩陣分解問題，比如MOD演算法的路子：Sparse Coding和Dictionary Update，兩步走，第一步固定D,更新x：x = argminxnorm(y − Ax, 2)2, s.t.norm(x, 1)≤k；第二步更新D: D = argminxnorm(y − Ax, 2)2很像EM演算法。

       KSVD和MOD最大的不同就是K每次只更新D當中的一個原子，就是D矩陣當中的某一列，因為矩陣相乘可以看做是前一個矩陣的列向量分別乘後一個矩陣的行向量。Loss函數在這里可以進行轉化：

      而SVD就用在對E的分解，和上面的MOD類似，也是迭代察擾皮進行就是每次更改D的原子。就比如敗差說KSVD用於圖像去噪的話，假如有一個零均值高斯白雜訊，即 n ∼ N(0, σ) ，σ是雜訊的標准差，有雜訊的圖像為 z = y + n ，目的是從信號 z 中恢復出原始無噪信號 y，通過最大後驗概率，求得目標函數的解，即可恢復出y：x = argminx∥z−Dx∥22,   s.t.∥x∥0 ≤ T 。其中T依賴於 ε 和 σ 。為方便優化計算，實際操作中往往轉化成： x = argminx∥z−Dx∥22+ μ∥x∥0選取恰當的μ可以讓上面兩式等價。

『肆』 稀疏編碼的研究歷史

1959年,David Hubel和Toresten Wiesel通過對貓的視覺條紋皮層簡單細胞感受野的研究得出一個結論:主視皮層V1區神經元的感受野能對視覺感知信息產生一種「稀疏表示」。
1961年,H.B.Barlow[5]基於這一知識提出了「利用感知數據的冗餘」進行編碼的理論.
1969年,D.J.Willshaw和O.P.Buneman等人提出了基於Hebbian 學習的局部學習規則的稀疏表示模型.這種稀疏表示可以使模型之間有更少的沖突,從而使記憶能力最大化.Willshaw模型的提出表明了稀疏表示非常有利於學習神經網路中的聯想.
1972年,Barlow推論出在稀疏性(Sparsity)和自然環境的統計特性之間必然存在某種聯系.隨後,有許多計算方法被提出來論證這個推論,這些方法都成功地表明了稀疏表示可以體現出在大腦中出現的自然環境的統計特性.
1987年,Field提出主視皮層V1區簡單細胞的感受野非常適於學習視網膜成像的圖像結構,因為它們可以產生圖像的稀疏表示.基於這個結論,1988年,Michison明確提出了神經稀疏編碼的概念,然後由牛津大學的E.T.Roll 等人正式引用.隨後對靈長目動物視覺皮層和貓視覺皮層的電生理的實驗報告,也進一步證實了視覺皮層復雜刺激的表達是採用稀疏編碼原則的.
1989年,Field提出了稀疏分布式編碼(Sparse Distributed Coding)方法.這種編碼方法並不減少輸入數據的維數,而是使響應於任一特殊輸入信息的神經細胞數目被減少,信號的稀疏編碼存在於細胞響應分布的四階矩(即峭度Kurtosis)中.
1996年,Olshausen和Field在Nature雜志上發表了一篇重要論文指出,自然圖像經過稀疏編碼後得到的基函數類似於V1區簡單細胞感受野的反應特性.這種稀疏編碼模型提取的基函數首次成功地模擬了V1區簡單細胞感受野的三個響應特性:空間域的局部性、時域和頻域的方向性和選擇性.考慮到基函數的超完備性(基函數維數大於輸出神經元的個數),Olshausen 和Field在1997年又提出了一種超完備基的稀疏編碼演算法,利用基函數和系數的概率密度模型成功地建模了V1區簡單細胞感受野.
1997年,Bell和Sejnowski 等人把多維獨立分量分析(Independent Component Analysis, ICA)用於自然圖像數據分析,並且得出一個重要結論:ICA實際上就是一種特殊的稀疏編碼方法.
2014年，
21世紀以來,國外從事稀疏編碼研究的人員又提出了許多新的稀疏編碼演算法,涌現出了大量的稀疏編碼方面的論文,國內研究者在稀疏編碼演算法和應用方面也作了一些工作],但遠遠落後於國外研究者所取得的成果.