基于壓縮感知的信號重構(gòu)算法

《基于壓縮感知的信號重構(gòu)算法》由會員上傳分享，免費在線閱讀，更多相關(guān)內(nèi)容在工程資料-天天文庫。

1、基于壓縮感知的的信號重構(gòu)算法1引言至今，已有眾多國內(nèi)外學(xué)者在重建算法領(lǐng)域做岀了新的研究和探索。Candes等證明了信號重建問題可以通過求解最小厶范數(shù)問題解決，但Donoho指出，求解最小厶范數(shù)是一個NP問題，需要窮舉X屮非零值的所有K屮排列可能，因而無法直接求解。此后，研究人員提岀了一系列求得次最優(yōu)解的算法，主要包括最小厶范數(shù)法、貪婪迭代匹配追蹤系列算法等。其中，匹配追蹤類方法為其近似求解提供了有力工具，文獻中指出了該類方法用于稀疏信號重建時具有一定的穩(wěn)定性。重建算法的關(guān)鍵是如何從壓縮感知得到的低維數(shù)據(jù)中精確地恢復(fù)出原始的高維數(shù)據(jù)，即由M維測量向量重建出長度為N(M

2、號X的過程。傳統(tǒng)的兀配追蹤算法能夠精確的重建出原始信號，但同吋又有不同方面的缺陷，因此有關(guān)壓縮感知重建算法的研究還有很多值得探索和研究的地方。2最小/。范數(shù)模型從數(shù)學(xué)意義上講，基于壓縮感知理論的信號重建問題就是尋找欠定方程組(程的數(shù)量少于待解的未知數(shù))的最簡單解的問題，厶范數(shù)刻畫得就是信號中非零元素的個數(shù)，因而能夠使得結(jié)果盡可能地稀疏。通常我們采用下式描述最小厶范數(shù)最優(yōu)化問題：min

3、

4、x

5、

6、()s.t.Y=^)X(3.1)實際中，允許一定程度的課差存在，因此將原始的最優(yōu)化問題轉(zhuǎn)化成一個較簡單的近似形式求解，其中/是一個極小的常量：minXns.t.Y-d>X；<3(3.2)

7、但是這類問題的求解數(shù)值計算極不穩(wěn)定，很難直接求解。基于壓縮感知的的信號重構(gòu)算法1引言至今，已有眾多國內(nèi)外學(xué)者在重建算法領(lǐng)域做岀了新的研究和探索。Candes等證明了信號重建問題可以通過求解最小厶范數(shù)問題解決，但Donoho指出，求解最小厶范數(shù)是一個NP問題，需要窮舉X屮非零值的所有K屮排列可能，因而無法直接求解。此后，研究人員提岀了一系列求得次最優(yōu)解的算法，主要包括最小厶范數(shù)法、貪婪迭代匹配追蹤系列算法等。其中，匹配追蹤類方法為其近似求解提供了有力工具，文獻中指出了該類方法用于稀疏信號重建時具有一定的穩(wěn)定性。重建算法的關(guān)鍵是如何從壓縮感知得到的低維數(shù)據(jù)中精確地恢復(fù)出原始的高維

8、數(shù)據(jù)，即由M維測量向量重建出長度為N(M

9、

10、x

11、

12、()s.t.Y=^)X(3.1)實際中，允許一定程度的課差存在，因此將原始的最優(yōu)化問題轉(zhuǎn)化成一個較簡單的近似形式求解，其中/是一個極小的

13、常量：minXns.t.Y-d>X；<3(3.2)但是這類問題的求解數(shù)值計算極不穩(wěn)定，很難直接求解。3匹配追蹤類算法匹配追蹤類稀疏重建算法解決的是最小/。范數(shù)問題，最早提岀的有匹配追蹤(MP)算法和止交匹配追蹤(OMP)算法。MP的基本思想是在每一次的迭代過程中，從過完備原子庫里(即感知矩陣)選擇與信號最匹配的原子來進行稀疏逼近并求出余量，然后繼續(xù)選出與信號余量最為匹配的原子。經(jīng)過數(shù)次迭代，該信號便可以由一些原子線性表示。但是由于信號在己選定原子(感知矩陣的列向量)集合上的投影的非正交性使得每次迭代的結(jié)果可能是次最優(yōu)的，因此為獲得較好的收斂效果往往需要經(jīng)過較多的迭代次數(shù)。OM

14、P算法則有效克服了這個問題，該算法沿用了匹配追蹤算法中的原子選擇準(zhǔn)則，在重建時每次迭代得到F的支撐集的一個原子，只是通過遞歸對己選擇原子集合進行正交化以保證迭代的最優(yōu)性，從而減少迭代次數(shù)。實驗表明對固定K-稀疏的N維離散時間信號X,用高斯隨機矩陣時，只要M=O(KlogN),止交匹配追蹤算法將以極大概率準(zhǔn)確重構(gòu)信號，而且運行吋間遠(yuǎn)比最小厶范數(shù)模型短。但是，正交匹配追蹤算法精確重構(gòu)的理論保證比最小厶范數(shù)算法弱，并非對所有信號都能準(zhǔn)確重構(gòu)，而且對于感知矩陣的耍求比約束等距性更加嚴(yán)格。Needell等在OMP的基礎(chǔ)上提出了正則正交匹配追蹤(RegularizedOrthogonal

15、MatchingPinsiiiLROMP)算法，對于所有滿足約束等距性條件的矩陣和所有稀疏信號都可以準(zhǔn)確重構(gòu)。之后，Needell等人又提出了引入回溯思想的壓縮采樣匹配追蹤(CtmpressiveSamplingMatchingPinsuit,CoSaMP)算法，不僅提供了比OMP算法更全面的理論保證，并且能在采樣過程中對噪聲有很強的魯棒性。同樣引入回溯思想的還有子空間追蹤(SubspacePuisuiLSP）算法,在得到F的支撐集之前先建立一個候選集，之后再從候選集中舍棄不需要的原子，形成最終的支撐集