稀疏表示在信號處理中的應(yīng)用

SparseRepresentationsforSignalProcessingandCoding120140420outlineWhataresparserepresentations/approximations?Howtofindsparserepresentations/approximations?HowtofindthedictionaryD?Whataresparserepresentations/approximationsgoodfor?2Whataresparserepresentations/approximations?定義：用較少的基本信號的線性組合來表達(dá)大部分或者全部的原始信號信號。其中，這些基本信號被稱作原子，是從過完備字典中選出來的；而過完備字典則是由個數(shù)超過信號維數(shù)的原子聚集而來?？梢姡我恍盘栐诓煌脑咏M下有不同的稀疏表示。3Whataresparserepresentations/approximations?4Howtofindsparserepresentations/approximations?尋找少量重要的系數(shù)來表示原始信號的技術(shù)被稱作SparseCoding（稀疏編碼或稀疏分解）；從任意一個字典中為原始信號尋找最稀疏的表示常用的方法分類兩類：①貪婪算法，比如匹配追蹤（MP）、正交匹配追蹤（OMP）、弱匹配追蹤（WMP）、閾值方法等；②松弛算法，比如迭代加權(quán)最小二乘（Iterative-Reweighed-Least-Squares，IRLS）、基追蹤（BP）等。其中，貪婪算法的特點(diǎn)是速度快，精度相對較低；松弛算法是精度高，但速度慢。5Howtofindsparserepresentations/approximations?現(xiàn)假設(shè)已知字典D和信號X，進(jìn)行稀疏編碼的問題可以表示為L0優(yōu)化問題這也是一個組合優(yōu)化問題。窮舉法——NP難：假設(shè)

的非零項(xiàng)數(shù)目為L(sparselevel)，先令L=1，字典里的每一個原子（列向量）嘗試一遍，看是否滿足終止條件，共有K種組合。如果沒有滿足，再令L=2，再次嘗試，共有K(K-1)/2種組合。還沒有滿足條件的，則令L=3……組合的數(shù)目呈指數(shù)增長，于是遇到了NP難問題。貪婪算法——MatchingPursuit第一步，找到最接近X的原子，等效于

向量上僅取一個非零項(xiàng)，求出最接近的原子，保留下來；第二步，計(jì)算誤差是否滿足要求，如果滿足，算法停止，否則，計(jì)算出殘差信號，和第一步類似，找到最接近殘差向量的原子，保留下來；第三步，調(diào)整已選向量的系數(shù)，使得

最接近X，重復(fù)第二步。松弛算法——BasisPursuit，將L0問題轉(zhuǎn)化為L1問題，解決的方法有很多，比如內(nèi)點(diǎn)法、迭代收縮法等。事實(shí)上，它可以化成一個線性規(guī)劃的問題，用MATLAB很容易解。6HowtofindthedictionaryD?尋找字典的過程稱為字典學(xué)習(xí)。字典學(xué)習(xí)的一個假設(shè)是字典對于指定信號具有稀疏表示。因此，選擇字典的原則就是能夠稀疏地表達(dá)信號。兩種方法來設(shè)計(jì)字典:從已知的變換基中選取，比如DCT、小波基等，這種方法很通用，但是不能自適應(yīng)于信號。學(xué)習(xí)字典，即通過訓(xùn)練和學(xué)習(xí)大量的與目標(biāo)數(shù)據(jù)相似的數(shù)據(jù)來獲得。這里，我們介紹一種叫K-SVD的方法。78假設(shè)現(xiàn)在有原始信號矩陣，

該矩陣的每一行表示一個信號或者一張圖片，D矩陣是字典矩陣，右下方是稀疏解矩陣S，紅色的點(diǎn)表示非零項(xiàng)。HowtofindthedictionaryD?——K-SVDHowtofindthedictionaryD?——K-SVDStep2:

SparseCoding.用松弛或者貪婪法進(jìn)行稀疏編碼，使得9Step1:Initialize.在

矩陣中隨機(jī)挑選一些行向量(一些原圖），填滿矩陣D，并歸一化每一列。得到稀疏表示構(gòu)成稀疏矩陣S的第i行。SHowtofindthedictionaryD?——K-SVD10

Step4：StoppingRule.如果則停止迭代。SWhataresparserepresentations/approximationsgoodfor?稀疏性是DFT、WT和SVD分解得以廣泛利用的原因之一，這些變換的目的都是為了反映信號的確定性結(jié)構(gòu)，并用緊湊的或稀疏的表示來表征這些結(jié)構(gòu)；稀疏表示的思想為模式分類方法建立了基礎(chǔ)，比如SVM和RVM，其中稀疏性直接與估計(jì)函數(shù)（estimator）的學(xué)習(xí)能力有關(guān)。稀疏表示解決的問題主要集中在：圖像去噪（Denoise），代表性paper：ImageDenoiseViaSparseandRedundantRepresentationsOverLearnedDictionaries(EladM.andAharonM.IEEETrans.onImageProcessing,Dec,2006);ImageSequenceDenoisingViaSparseandRedundantRepresentations(ProtterM.andEladM.IEEETrans.onImageProcessing,Jan,2009)；超分辨率重建（Super-ResolutionORScale-Up），代表性paper：ImageSuper-ResolutionviaSparseRepresentation（JianchaoYang,JohnWright,ThomasHuang,andYiMa，IEEETransactionsonImageProcessing,Nov,2010）,AShrinkageLearningApproachforSingleImageSuper-ResolutionwithOvercompleteRepresentations(A.Adler,Y.Hel-Or,andM.Elad,ECCV,Sep,2010);另外還有inpaintting，deblurring，compression等等..更多應(yīng)用參考EladM的書。11OutputOriginalInputTrainingpatches12Whataresparserepresentations/approximationsgoodfor?去噪：超分辨率：Whatare