壓縮感知的重構(gòu)算法

1、壓縮感知的重構(gòu)算法算法的重構(gòu)是壓縮感知中重要的一步，是壓縮感知的關(guān)鍵之處。因?yàn)橹貥?gòu)算法關(guān)系著信號能否精確重建，國內(nèi)外的研究學(xué)者致力于壓縮感知的信號重建，并且取得了很大的進(jìn)展，提出了很多的重構(gòu)算法，每種算法都各有自己的優(yōu)缺點(diǎn)，使用者可以根據(jù)自己的情況，選擇適合自己的重構(gòu)算法，大大增加了使用的靈活性，也為我們以后的研究提供了很大的方便。壓縮感知的重構(gòu)算法主要分為三大類：1.組合算法2.貪婪算法3.凸松弛算法每種算法之中又包含幾種算法，下面就把三類重構(gòu)算法列舉出來。組合算法：先是對信號進(jìn)行結(jié)構(gòu)采樣，然后再通過對采樣的數(shù)據(jù)進(jìn)行分組測試，最后完成信號的重構(gòu)。(1)傅里葉采樣(FourierReprese

2、ntaior)(2)鏈?zhǔn)阶粉櫵惴?ChainingPursuit)(3)HHS追蹤算法(HeavyHittersOnSteroidS)貪婪算法：通過貪婪迭代的方式逐步逼近信號。(1) 匹配追蹤算法(MatchingPursuitMP)(2) 正交匹配追蹤算法(OrthogonalMatchingPursuitOMP)(3)分段正交匹配追蹤算法(StagewiseOrthogonalMatchingPursuitStOMP)正則化正交匹配追蹤算法(RegularizedOrthogonalMatchingPursuitROMP)(5)稀疏自適應(yīng)匹配追蹤算法(SparistyAdaptiveMat

3、chingPursuitSAMP)凸松弛算法：(1)基追蹤算法(BasisPursuitBP)(2) 最小全變差算法(TotalVariationTV)(3)內(nèi)點(diǎn)法(Interior-pointMethod)(4) 梯度投影算法(GradientProjection)(5) 凸集交替投影算法(ProjectionsOntoConvexSetsPOCS)算法較多，但是并不是每一種算法都能夠得到很好的應(yīng)用，三類算法各有優(yōu)缺點(diǎn)，組合算法需要觀測的樣本數(shù)目比較多但運(yùn)算的效率最高，凸松弛算法計(jì)算量大但是需要觀測的數(shù)量少重構(gòu)的時(shí)候精度高，貪婪迭代算法對計(jì)算量和精度的要求居中，也是三種重構(gòu)算法中應(yīng)用最大的一

4、種。下面分別就貪婪算法中的MP,OMP算法以及凸松弛算法中的BP算法進(jìn)行詳細(xì)的介紹。三種重建算法本節(jié)主要是介紹一些基本的重建算法，比如貪婪迭代算法中的匹配追蹤算法，正交匹配追蹤算法，以及凸松弛算法中的基追蹤算法，對其原理進(jìn)行了介紹，并用matlab代碼重構(gòu)出來一維和二維的圖形，進(jìn)而比較這幾種算法的性能。1 .匹配追蹤算法(MatchingPursuitMP)匹配追蹤算法是Mallat和ZHANG在小波分析的基礎(chǔ)上提出的，是貪婪迭代算法中的比較基本的算法，有其顯著的特點(diǎn)，是學(xué)習(xí)研究貪婪算法的基礎(chǔ)。1.1 MP算法的原理y=x,其中測量矩陣中又稱為過完備字典，每一列被稱為一個(gè)原子，則測量矩陣中有n

5、個(gè)原子，而y的長度為m,原子的個(gè)數(shù)遠(yuǎn)遠(yuǎn)大于信號的長度，即m<<n,因此測量矩陣又稱為過完備字典。信號y在測量矩陣上進(jìn)行分解，可以用中中n來表示，單位向量長度為1,要對過完備字典的原子進(jìn)行歸一化處理。MP算法的基本思想：從觀測矩陣(過完備字典)中選擇一個(gè)與信號y相關(guān)性最大(最匹配)的原子，也就是觀測矩陣中的一列，構(gòu)建信號的稀疏逼近，求出信號的殘差，重復(fù)上面的操作，繼續(xù)選擇與信號殘差最匹配的一個(gè)原子，如此反復(fù)迭代直到達(dá)到迭代次數(shù)，最后信號y就可以表示為這些原子的線性組合。MP進(jìn)行稀疏分解的步驟12：從觀測矩陣中選擇一個(gè)與信號y最匹配的原子，也就是內(nèi)積最大的一個(gè)原子，即：|<y，&

6、gt;|=sup|<y，產(chǎn)|(1)-0i.(1,.n)其中，。表示字典矩陣的列索引。先將信號y投影到向量中產(chǎn)上，信號y也可以表示為:廠y。R(2)式等號右邊的第一項(xiàng)為觀測矩陣中最匹配原子中的垂直投影分-0量，等式右邊的第二項(xiàng)R1是y通過中0分解后的殘差，且與y正交。(2)式可以寫為：222Ilyl-o+lRII對殘差Rl進(jìn)行上面同樣的分解，在第n次迭代過程中：FTR'D+Ri因?yàn)镽n和中r正交，則(4)式可以表示為：n2,.,22IlRnHT<Rnrn>|+|lRn+lII最后，信號y可以表示為：ny=£<yF7>卬+R由(6)1 =0i-i因?yàn)?/p>

7、最后的殘差R十正交于上次迭代產(chǎn)生的殘差Rn，則最后的表達(dá)式為：2 n22IlylLFy，片IlRdli=o由(7)式可知，當(dāng)殘差Rn力為零時(shí)，可以得到信號的精確分解。定理13存在兒>0,使得一切對于n20時(shí)，有一'nIRil卜2llyli成立。這樣(7)式中，llR1li按照指數(shù)衰減的形式趨于零，也就是2n2|y|Jy,i|成立。參考文獻(xiàn)：1曹離然.面向壓縮感知的稀疏信號重建算法研究.D.哈爾濱工業(yè)大學(xué)，2011.2Y.C.PATI.OrthogonalMatchingPursuit:RecursiveFunctionApproximationwithApplicationsto

8、WaveletDecomposition.IEEE.1993:40-443韓紅平.壓縮感知中信號重構(gòu)算法的研究.D.南京郵電大學(xué)，2012.1.2 MP算法的理論框圖根據(jù)上面的MP算法的原理，得出MP算法的理論圖1,這樣更容易理解圖1:MP算法框圖參考文獻(xiàn)：1韓紅平.壓縮感知中信號重構(gòu)算法的研究D,南京郵電大學(xué)，20121.3 MP算法的算法流程根據(jù)1.2中介紹的MP算法的理論框圖，現(xiàn)在寫出MP算法的算法流程12,這樣讓我們對MP算法有一個(gè)更加清晰的理解。輸入：測量矩陣中(MMN),測量向量y(N>1),稀疏度k輸出：重構(gòu)信號x(1):初始化余量0=y,迭代次數(shù)n=01;(2):計(jì)算余量

9、與測量矩陣的每一列的內(nèi)積gn=Tn；共有N個(gè)內(nèi)積數(shù)值。(3):找出N個(gè)gn中的絕對值最大的元素gn(k),k為對應(yīng)的最大內(nèi)積的列號。(4):計(jì)算信號的近似解xnk=xn/k+gnk；xx(5)：更新余量rn=rn.gnk%；(6):若滿足迭代條件，則n=n+1,x'=xn,若不滿足迭代條件則x返回步驟(2);迭代次數(shù)為稀疏度的2倍。參考文獻(xiàn)：1 LinfengDu,RuiWang.AnalysisonGreedyReconstructionAlgorithmsBasedonCompressedSensing.J.IEEE2012:783-7892文首先.壓縮感知匹配追蹤算法的研究.D.

10、20131.4MP算法的信號重構(gòu)本節(jié)分別通過對一維離散信號，二維Lena為例，進(jìn)行MP算法的信號重構(gòu)。(1) 一維離散信號的MP算法仿真本次仿真使用matlab隨機(jī)生成的一維離散信號，稀疏度k=23，信號長度N=256,觀測向量的長度M=80,那么采樣率M/N=0.3,其中的觀測矩陣中是高斯隨機(jī)矩陣。采用MP算法對一維信號進(jìn)行重構(gòu)，重構(gòu)圖如1:origin圖1:MP算法重構(gòu)一維信號通過上面的重構(gòu)可以得出，MP算法對一維信號有很好的重構(gòu)效果。(2)二維lena圖像的MP算法重構(gòu)我們上面的研究知道MP算法對一維信號有很好的重構(gòu)作用，但是算法不只是要在一維信號中有好的重構(gòu)功能，還要能很好的重構(gòu)二維信

11、號才可以，這樣應(yīng)用的范圍才會(huì)更大。我們知道壓縮感知重構(gòu)的是可壓縮的稀疏信號，二維信號是不稀疏的，這就要在進(jìn)行算法重構(gòu)的時(shí)候進(jìn)行一些處理，我們可以先采用離散余弦變換（dot）使數(shù)據(jù)稀疏，算法重構(gòu)結(jié)束之后再進(jìn)行離散反余弦變換（idct）,這樣就轉(zhuǎn)化為了我們所需要的。本次在matlab中的仿真，我們采用的是256M256的Lena的二維圖像，M=180,N=256,稀疏度k=40,M/N=0.7,觀測矩陣是高斯隨機(jī)矩陣，采用MP算法對二維圖像進(jìn)行重構(gòu)，重構(gòu)效果如圖2（b）:（a）原始圖片（b）MP算法重構(gòu)（M/N=0.7）通過上面的（a）圖和（b）圖可知，采樣率為0.7的時(shí)候，MP算法也能對二維圖像

12、進(jìn)行精確重構(gòu)。2.正交匹配追蹤算法（OMP）2.1OMP算法的原理OMP算法是在MP算法的基礎(chǔ)上進(jìn)行改進(jìn)的，沿用了MP算法的重構(gòu)的思想，但是又對MP算法進(jìn)行了改進(jìn)，使得算法的效率更高,應(yīng)用更加的廣泛。MP算法的信號分解中步驟中介紹：y=<y,中>中+R1,這說-0-0明信號在已經(jīng)選擇的原子上的投影(等是右邊第一項(xiàng))是非正交的，還存在著殘差，也就是說每次迭代的過程是次最優(yōu)的，不是最優(yōu)解，要想最終的迭代收斂，需要的迭代次數(shù)較多。OMP算法就是根據(jù)MP算法的不足之處加以改進(jìn)，把所選擇的原子首先通過Schimidt正交化處理，使得在達(dá)到迭代條件的時(shí)候需要的迭代次數(shù)較MP算法少，但是正交化的

13、過程中會(huì)增加計(jì)算量。在每一步中如何對選擇的全部原子進(jìn)行正交化處理呢？這是OMP算法和MP算法的不同之處。下面介紹OMP算法正交化原理1:ky="n=1信號y經(jīng)k步分解:(1)*Rk且<Rk卅>=0,n=1,，k-n(1)式和MP算法的不同在于，MP算法是殘差和前面的一個(gè)分量正交，而OMP算法是殘差和前面的每個(gè)分量都正交。k+1步分解為：k1k1y-Zan'rRk中且，Rir>_0n=1,，k+1n=1'n-nk+1階減去k階：k工(an41-ah)tPr十式?rRYRnW'n'k1要想對選擇的全部原子進(jìn)行正交化處理，要求(3)式等于零

14、。測量矩陣的原子不正交，為了說明（3）式等于零，下面引入一個(gè)輔助模型，模型表示的是中對前k個(gè)項(xiàng)中（n=1,，k）的依賴，數(shù)學(xué)語言描述如下：kk邛=2bn''rk且kW>=0,n=1,kn1nz1-n-n平在件1,.gk）上張成的正交投影，等式右邊的第二項(xiàng)是殘差，（4）-k11k式代入（3）式中：kk1kk1kk1"（ananakibn）自nRk/R）=0（5）n1一n如果（6）和（7）式成立，則（5）式必然成立，k1kk1kan-anak書bn=0（6）k1ak1”RkRk=0（7）人k1令ak由=ak，有：k1kkan=a<akbnn=1,k（8）arR

15、書R=0n=1,k（8）和（9）兩式成立，以上就是OMP算法進(jìn)行正交化的過程。參考文獻(xiàn)：1Y.C.PATI.OrthogonalMatchingPursuit:RecursiveFunctionApproximationwithApplicationstoWaveletDecomposition.IEEE.1993:40-442.2 OMP算法的流程圖和上面的MP算法一樣，我們同樣畫出OMP算法的流程圖，可以讓我們更加清晰的理解算法圖：OMP算法的流程圖2.3 OMP算法的算法步驟和MP算法一樣，我們也在給出OMP算法的流程圖之后，再給出OMP算法的算法步驟12。輸入：感知矩陣(MmN),測量

16、向量y(N父1),稀疏度K八輸出：重構(gòu)信號X(1)初始化余量0=y,迭代次數(shù)n=0,重建信號X0=°，索引集r0=口；(2)計(jì)算余量和測量矩陣每一列的內(nèi)積：g'G)心；(3)找出gn中絕對值最大的元素；(4) 更新原子組合G=63中J和新索引集n=rnJk；_n-n1k1(5)利用最小二乘法計(jì)算信號的近似解：T1tXn=(小品M)rny；(6)計(jì)算更新余量：rn=y"xn；(7)更新迭代次數(shù)n=n+1,若滿足迭代條件，則X=Xn；若不滿足迭代的的條件則返回(2),繼續(xù)進(jìn)行迭代；參考文獻(xiàn)1文首先.壓縮感知匹配追蹤算法的研究.D.20132Y.C.PATI.Orthog

17、onalMatchingPursuit:RecursiveFunctionApproximationwithApplicationstoWaveletDecomposition.IEEE.1993:40-44上面提到最小二乘法，首先我們先較少一下什么殺死最小二乘法，然后再說明一下為什么OMP算法可以用最小二乘法就信號的解。名詞解釋：最小二乘法最小二乘法(最小平方法)是一種數(shù)學(xué)優(yōu)化技術(shù)，它通過使數(shù)據(jù)誤差的平方和最小來尋找數(shù)據(jù)的最佳函數(shù)匹配。最小二乘準(zhǔn)則：使全部樣本觀測值的殘差平方和達(dá)到最小。即min“q2=min”e(YiYi)來確定未知的參數(shù)，未知的參數(shù)=(01,k)，未知參數(shù)的估計(jì)為/,下面

18、我們來推導(dǎo)二階估計(jì)量的公式:(0,1,.k)2Q(：0,：-1,.,二J='ei設(shè)所有殘差的平方和為：、=a'e(YiYi)e=VY-2vYvX:I、工X、EXA其中，Yi是第i次的樣本觀測值，Yi為相應(yīng)的第i次的樣本估計(jì)值,e2AAe=lemY-yt-xu,對上式進(jìn)行求導(dǎo)，以便得到最小二乘估計(jì).£n1值：''AA.Q；'A'A'''一)丫丫一2XyXX)=2XY2XX：=0白cc,A1移項(xiàng)可得，XXa=XY，在這里我們假定(x'X)存在，用(XX)左乘上式的；兩邊，得到。的最小二乘估計(jì)量，A,1,豆=(

19、XX)XY,這個(gè)公式也就是OMP算法步驟中的步驟(5),以上就證明了最小二乘法估計(jì)OMP算法的方法。2.4OMP算法的信號重構(gòu)本節(jié)對OMP算法進(jìn)行重構(gòu)，采用一維離散信號和二維lena信號對其進(jìn)行信號重構(gòu)，來觀察OMP算法的重構(gòu)功能。(1)一維離散信號的OMP算法仿真本次仿真使用matlab隨機(jī)生成的一維離散信號，稀疏度k=15，信號長度N=512,觀測向量的長度M=128,那么采樣率M/N=0.25,其中的觀測矩陣中是高斯隨機(jī)矩陣。采用OMP算法對一維信號進(jìn)行重通過上面的重構(gòu)可以得出，OMP算法對一維信號有很好的重構(gòu)作用。(2)二維lena圖像的OMP算法重構(gòu)OMP算法對二維信號進(jìn)行重構(gòu)，在這

20、里我們采取和MP算法二維信號重構(gòu)的方法，也是先采取離散余弦變換(dot)使數(shù)據(jù)稀疏,算法重構(gòu)結(jié)束之后再進(jìn)行離散反余弦變換(idct),這樣就轉(zhuǎn)化為了我們所需要的。本次在matlab中的仿真，我們采用的是256乂256的Lena的二維圖像,M=180,N=256,稀疏度k=40,M/N=0.7,觀測矩陣是高斯隨機(jī)矩陣，采用OMP算法對二維圖像進(jìn)行重構(gòu)，重構(gòu)效果如圖2（b）:（a）原始圖像（b）OMP算法重構(gòu)圖片（M/N=0.7）通過上面（a）圖和（b）圖的重構(gòu)可知，采樣率為0.7的時(shí)候,OMP算法也能對二維信號很好的重構(gòu)。3基追蹤算法（BP）壓縮感知中很重要的一步就是重構(gòu)算法，重構(gòu)算法關(guān)系著重建

21、信號的質(zhì)量?；粉櫵惴ㄊ峭顾沙诜ㄊ呛苡写硇缘囊环N算法。3.1凸松弛法介紹凸松弛法是信號在重構(gòu)的過程中把重構(gòu)問題由l0范數(shù)問題轉(zhuǎn)化為了l1范數(shù)的凸優(yōu)化問題。下面首先介紹幾個(gè)涉及到的概念凸優(yōu)化：定義域是閉合的凸集；函數(shù)是定義域上的凸函數(shù)的最優(yōu)化問題，只有兩個(gè)條件同時(shí)滿足才是凸優(yōu)化。凸集：數(shù)學(xué)定義，D為集合DwRNMXi，X2WD產(chǎn)WO,13QX"(1DxD凸集的幾何意義：集合中的任意兩點(diǎn)連線段都在集。凸函數(shù)：凸集上的g(x)函數(shù)和任意的實(shí)數(shù)«/0,1,Xi，XJD,使gQXl+(1-cc)X2)"叼"尸”必由成立,g(x)就是凸函數(shù)。下面介紹一下0范數(shù)為什

22、么可以用|1范數(shù)進(jìn)行求解，可以用|2范數(shù)進(jìn)行求解嗎？首先給出這三個(gè)范數(shù)的統(tǒng)一的數(shù)學(xué)表達(dá)式：m叫卜TX|ps,t.丫=6型TXP=0,1,2將三種范數(shù)投影到二維空間中，直線丫=6空tx在二維空間中是一條直線，圖1是三種范數(shù)在二維空間構(gòu)成的圖形和直線之間的直觀圖。圖1:三種范數(shù)與直線的關(guān)系圖其中(a)是|0范數(shù)與丫=中TX直線關(guān)系圖，(b)是l1范數(shù)與Y=中中TX直線關(guān)系圖，（c）是12范數(shù)與丫=中中TX直線關(guān)系圖。由（a）圖可知，1。范數(shù)在二維空間中是沿著坐標(biāo)軸的兩條垂直的線，直線向坐標(biāo)原點(diǎn)逼近的時(shí)候首先是和坐標(biāo)軸相交，這也就是我們所要求的稀疏的解；由（b）圖可知，11范數(shù)在二維空間中的圖形是一

23、個(gè)如（b）圖的菱形，排除直線和菱形的一條邊平行的情況，直線向菱形逼近的過程中，首先相交于菱形的四個(gè)點(diǎn)，也就是坐標(biāo)軸上的點(diǎn)，這也就是我們所要求的稀疏的解；由（c）圖可知，l2范數(shù)在二維空間中的圖形是圓形，直線向圓形逼近的時(shí)候，直線和圓相交的點(diǎn)幾乎都不在坐標(biāo)軸上，只有直線和坐標(biāo)軸平行的小概率的時(shí)候。通過上面的介紹可以知道，可以用范數(shù)來代替1。范數(shù)進(jìn)行求解。3.2BP算法的原理上節(jié)提到的l。范數(shù)，由于我們所要求解的問題是方程的個(gè)數(shù)遠(yuǎn)遠(yuǎn)大于未知數(shù)的個(gè)數(shù)，用l。范數(shù)求解是很難求解出來的，這樣就找到一種用11范數(shù)來代替1。范數(shù)求解的方法，BP（BasisPursuit）算法就是利用卜范數(shù)求解的一種很好的方

24、法。BP算法不是直接尋求信號的稀疏表示，只是表示的用于最小化的I1的系數(shù)1,通過等價(jià)信號的最小化的11范數(shù)表示2。下面介紹BP算法的原理。BP算法中1o范數(shù)的模型為：八X二min|x|。s.t.y=X（1）1o范數(shù)是稀疏變換中不為零的個(gè)數(shù)，（1）式的求解比較困難，通過上面的說明，1o范數(shù)可以用范數(shù)進(jìn)行代替，則（1）式可以表示為：x=min|x|s.t,y=：'X式表示的是理想的一種情況，在實(shí)際的應(yīng)用中，會(huì)混入噪聲，也就是：y=6x+noise(3)那么(2)式可表示為：(4)X=min|x|s.t.|y-：x|2三；(4)式中名為噪聲的能量。由于實(shí)際模型中會(huì)混入噪聲，這就需要一種抑制噪

25、聲的模型，也就是改進(jìn)后的BP算法，改進(jìn)后的BP算法對噪聲有一定的抑制作用，那么改進(jìn)后的模型為3:m>n(1/2)|y-:-X|2|X|1(5)其中，(5)式的第一項(xiàng)是信號經(jīng)觀測矩陣之后的觀測值，式子的第二項(xiàng)是噪聲產(chǎn)生的觀測值，表示觀測值中中非零元素的位置。BP算法中就把凸松弛算法轉(zhuǎn)化為了線性規(guī)劃問題求解，則(5)式可以轉(zhuǎn)化為13:Ax+6p=bx-0,6=1(6)T、，12miipnCX2|p|s.t.(6)式中,c，1,1,.,1x':1”2，.，nmincTX等價(jià)于最小化的l1范數(shù)的系數(shù)，p表示噪聲產(chǎn)生的觀測值。參考文獻(xiàn):GreedyBasis1 PatrickS.Huggi

26、ns,StevenW.ZuckerPursuit.IEEE.2007,55(7):3760-37722 S.S.Chen；'BasisPursuit,Ph.D.dissertation,Dept.Statistic§StanfordUniversity,Stanford,CA,1995.3文首先.壓縮感知匹配追蹤算法的研究.D.20133.3BP算法的信號重構(gòu)本節(jié)對BP算法進(jìn)行重構(gòu)，采用一維離散信號和二維lena信號對其進(jìn)行信號重構(gòu)，來觀察BP算法的重構(gòu)功能。(1) 一維離散信號的BP算法仿真本次仿真使用matlab隨機(jī)生成的一維離散信號，稀疏度k=30，信號長度N=1000

27、,觀測向量的長度M=200,那么采樣率M/N=0.2,其中的觀測矩陣9是高斯隨機(jī)矩陣。采用BP算法對一維信號進(jìn)行重構(gòu)，重構(gòu)圖如圖1:圖1:BP算法一維信號重構(gòu)圖由圖1可以得到，BP算法對一維信號有很好的重構(gòu)功能。（2）二維lena圖像的BP算法重構(gòu)BP算法對二維信號進(jìn)行重構(gòu)，在這里我們采取和MP算法二維信號重構(gòu)的方法，也是先采取離散余弦變換（dot）使數(shù)據(jù)稀疏，算法重構(gòu)結(jié)束之后再進(jìn)行離散反余弦變換（idct）,這樣就轉(zhuǎn)化為了我們所需要的。本次在matlab中的仿真，我們采用的是256乂256的Lena的二維圖像，M=180,N=256,稀疏度k=40,M/N=0.7,觀測矩陣是高斯隨機(jī)矩陣，采

28、用BP算法對二維圖像進(jìn)行重構(gòu)，重構(gòu)效果如圖2(b):（a）原始圖像（b）BP算法重構(gòu)圖片（M/N=0.7）通過上面（a）圖和（b）圖的重構(gòu)可知，采樣率為0.7的時(shí)候,BP算法也能對二維信號很好的重構(gòu)本章小結(jié)本章詳細(xì)介紹了三種比較典型的重構(gòu)算法，分別是MP,OMP,BP算法，介紹了三種算法的原理，還有三種算法對一維信號和二維lena信號的重建功能，得出結(jié)論是三種算法都有很好的信號重建的功能不同算法的比較上一章中只是對三種算法的原理進(jìn)行了詳細(xì)的說明，并用matlab驗(yàn)證三種算法可以對信號進(jìn)行很好的重構(gòu)，沒有對算法進(jìn)行分析，即采樣率的不同對算法的影響和對lena信號重構(gòu)的清晰度的影響。在這一章中，就

29、對三種重構(gòu)算法進(jìn)行分析。1采樣率對三種算法的影響1.1 采樣率對MP算法的影響我們先看一下采樣率對一維信號的影響，首先用重構(gòu)圖來直觀的區(qū)別一下，表1是MP算法中采樣率對重構(gòu)時(shí)間和誤差的表格：采樣率0203040.50.60.703MSE5.65782.2428L7904031250.22240.05330.04760.0279時(shí)間（S）0.07400.07500.08110.08320.08530.0802Q.O9850.0885表1:MP算法采樣率對重構(gòu)時(shí)間和誤差的影響表1中測量了不同采樣率對應(yīng)的MP算法中重構(gòu)的MSE和時(shí)間的值,從表格中可知，采樣率越大，重構(gòu)產(chǎn)生的MSE越小，重構(gòu)的圖形越接

30、近原始圖形，但是時(shí)間也會(huì)增大，增加了計(jì)算的復(fù)雜度。下面我們再看一下采樣率的不同對lena信號的影響，可以用采樣率為0.30.50.8這三個(gè)采樣率，對比一下采樣率的不同重構(gòu)出來的圖片的清晰度。圖3的（a）圖是原始圖片，（b）為采樣率為0.3時(shí)的重構(gòu)圖，（c）圖是采樣率為0.5時(shí)的重構(gòu)圖，（d）圖是采樣率為0.8（c）MP重構(gòu)圖片（M/N=0.5）（d）MP重構(gòu)圖片（M/N=0.8）圖3:MP重構(gòu)的不同采樣率的lena重構(gòu)圖形由圖3中的四個(gè)圖片可知，采樣率越大，重構(gòu)的圖形效果越好，在應(yīng)用的時(shí)候要想獲得很好的重構(gòu)圖片就需要較高的采樣率，但是所需要的時(shí)間也會(huì)越大。1.2 采樣率對OMP算法的影響和MP

31、算法一樣，也是先對一維信號重構(gòu)進(jìn)行分析，表2是OMP算法中采樣率對重構(gòu)的MSE和時(shí)間的對應(yīng)表格：采樣率0J020.3G.40.50.60,70金MSE13.5407625236.49814.88824.1499372232.938025875時(shí)間（s）0.13920.14730.14%0.15100,15530.16310.17050.1737表2:MP算法采樣率對重構(gòu)時(shí)間和誤差的影響表2中測量了不同采樣率對應(yīng)的OMP算法中重構(gòu)的MSE和時(shí)間的值，從表格中可知，OMP算法和MP算法一樣，也是采樣率越大，重構(gòu)產(chǎn)生的MSE越小，重構(gòu)的圖形越接近原始圖形，但是時(shí)間也會(huì)增大，同樣增加了計(jì)算的復(fù)雜度。下

32、面我們再看一下采樣率的不同對lena信號的影響，同MP算法一樣，采用采樣率為0.30.50.8這三個(gè)采樣率，對比一下采樣率的不同重構(gòu)出來的圖片的清晰度。圖4的（a）圖是原始圖片，（b）為采樣率為0.3時(shí)的重構(gòu)圖，（c）圖是采樣率為0.5時(shí)的重構(gòu)圖，（d）圖是采樣率為0.8時(shí)的重構(gòu)圖。（a）原始圖片（b）OMP重構(gòu)圖片（M/N=0.3）(c)OMP重構(gòu)圖片(M/N=0.5)(d)OMP重構(gòu)圖片(M/N=0.8)圖4：OMP重構(gòu)的不同采樣率的lena重構(gòu)圖形由圖4中的四個(gè)圖片可知，OMP算法和MP算法一樣，采樣率越大,重構(gòu)的圖形效果越好，在應(yīng)用的時(shí)候要想獲得很好的重構(gòu)圖片就需要較高的采樣率，但是所

33、需要的時(shí)間也會(huì)越大。1.3 采樣率對BP算法的影響研究采樣率對BP算法的影響，研究方法和上面的MP,OMP算法一樣，首先研究采樣率大的不同多一位信號大的影響，表3是采樣率對重構(gòu)誤差和重構(gòu)時(shí)間的關(guān)系表格：果樣率0.10.20.30.40.50.60.70.8MSI：474461,.7«X7).44761.4701.35731.28851.2337.0IS5時(shí)間（s）0.57960.67290.73K80.95041.22521.324215385表3:BP算法采樣率對重構(gòu)時(shí)間和誤差的影響表3中測量了不同采樣率對應(yīng)的BP算法中重構(gòu)的MSE和時(shí)間的值，從表格中可知，BP算法和MP,OMP算

34、法一樣，也是采樣率越大，重構(gòu)產(chǎn)生的MSE越小，重構(gòu)的圖形越接近原始圖形，但是時(shí)間也會(huì)增大，同樣增加了計(jì)算的復(fù)雜度。下面我們再看一下采樣率的不同對lena信號的影響，仍然采用采樣率為0.30.50.8這三個(gè)采樣率，對比一下采樣率的不同重構(gòu)出來的圖片的清晰度。圖5的（a）圖是原始圖片，（b）為采樣率為0.3時(shí)的重構(gòu)圖，（c）圖是采樣率為0.5時(shí)的重構(gòu)圖，（d）圖是采樣率為0.8時(shí)的重構(gòu)圖(b)BP重構(gòu)圖片(M/N=0.3)(a)原始圖片(c)BP重構(gòu)圖片(M/N=0.5)(d)BP重構(gòu)圖片(M/N=0.8)圖5:BP重構(gòu)的不同采樣率的lena重構(gòu)圖形由圖5中的四個(gè)圖片可知，BP算法和MP,OMP算

35、法一樣，采樣率越大，重構(gòu)的圖形效果越好，在應(yīng)用的時(shí)候要想獲得很好的重構(gòu)圖片就需要較高的采樣率，但是所需要的時(shí)間也就會(huì)會(huì)越長。從上面的三種算法中采樣率對重構(gòu)時(shí)間和誤差的影響中，可以得出相同的結(jié)論，在一維信號中，采樣率越大，重構(gòu)的誤差越小，重構(gòu)所需要的時(shí)間越大。在二維圖片中，采樣率越大，重構(gòu)的圖片越清晰。2.信噪比對三種算法的影響在實(shí)際的應(yīng)用中，會(huì)混入噪聲，沒有噪聲那是理想的情況，這里就研究一下信噪比對重構(gòu)信號產(chǎn)生的MSE的影響。2.1 信噪比對MP算法的影響首先研究信噪比對MP算法產(chǎn)生的影響，圖6是信噪比和MSE的關(guān)系曲線圖，在matlab的環(huán)境中，試驗(yàn)了100次產(chǎn)生的曲線。8765UJ54名3

36、21°%、XA"-S.%,-j、h7111015202530SNR(dB)圖6:SNR和MSE關(guān)系曲線由圖6可知，信噪比越大，MSE就越小。2.2 信噪比對OMP算法的影響研究信噪比對OMP算法的影響，研究方法和所用的環(huán)境和MP算法一樣，圖7是SNR和MSE的關(guān)系曲線:4J11111.21,1:08；：:!UJS;1;三11*I106<'*k1tH1;:VI11110.4、；:、：:;、；:1、*1：!7!0.2i-.“一:；J-J-.-_0life!&111151015202530SNR(dB)圖7:SNR和MSE關(guān)系曲線由圖7可知，隨著信噪比的增大

37、，均方差減小。2.3 信噪比對BP算法的影響研究信噪比對BP算法的影響，研究方法和所用的環(huán)境和MP算法一樣，圖8是SNR和MSE的關(guān)系曲線：10.5109.59UJ岑8.587.57-*1/寸/XX/*L/X，iJ/J/*1V111/f/i1JJ,廠fffII11Jfir'51015202530SNR(dB)圖8:SNR和MSE關(guān)系曲線由圖8可以得出，BP算法和MP,OMP算法的SNR和MSE的關(guān)系曲線不同，是一個(gè)折線的形式。3三種算法之間的比較本章上面的分析中，分析的是采樣率和信噪比對三種算法各自的一些影響，這里要分析的是三種算法之間的性能分析。圖9表示的是采樣率對三種算法重構(gòu)時(shí)間的

38、影響圖，圖10表示的采樣率對三種算法重構(gòu)的均方差的影響圖，圖11表示的是信噪比對三種算法MSE的影像圖：16回aQsB-TE*4*0JJJJ0.10.20.30.40506采樣率圖9:采樣率對三種算法重構(gòu)時(shí)間的影響圖由圖9可知，采樣率相同的情況下，BP算法重構(gòu)的時(shí)間最長，MP算法重構(gòu)所需要的時(shí)間最短。MP和OMP算法的重構(gòu)時(shí)間變化較小，而BP算法在采樣率為0.3之后，變化較快。OMP算法中迭代次數(shù)較MP算法少，但是需要正交化處理，所以重構(gòu)的時(shí)間會(huì)比MP算法長。I4!1fMl產(chǎn)rEADiijUmrI士108LJ5蒞6nCQO口or>arJ1,1411i4-E4L4T*=1U01020304

39、050采樣率60708圖10:采樣率對三種算法重構(gòu)MSE的影響圖由圖10可知，隨著采樣率的增加，算法的誤差都減小，MP算法的誤差下降的更快。111111111111111JJ1tMP-OMP：X!OBP:-：1'Il!1ih;Jij._SNRfdBl圖11:信噪比對三種算法重構(gòu)MSE的影響圖由圖11可知，三種算法都是隨著信噪比的增加，MSE下降。BP算法的均方差最大，OMP算法的均方差最小。由上面的圖9,圖10,圖11中三種算法的對比圖中可知，從重構(gòu)時(shí)間，重構(gòu)誤差方面考慮的話，OMP算法是三種算法中性能最折中的算法。正則化正交匹配追蹤算法（ROMP）本章介紹一種匹配追蹤算法中的改進(jìn)算法

40、，正則化正交匹配追蹤算法（ROMP）,是在正交匹配追蹤算法（OMP）的基礎(chǔ)上改進(jìn)的，是Needell和Vershynin1提出來的，是貪婪迭代算法中較成熟的一種算法。ROMP算法改進(jìn)的地方是：OMP算法對每個(gè)原子做處理的時(shí)候都要做K次迭代，而ROMP算法是首先選出符合要求的K個(gè)原子，再從中進(jìn)行篩選，減少了迭代的次數(shù)，同時(shí)也增加了算法重構(gòu)的精度，但是ROMP算法也有自己的缺點(diǎn)，就是算法首先要知道信號的稀疏度K,這樣才能精確的重構(gòu)。在實(shí)際的應(yīng)用中，信號可能的稀疏度很小，或者是經(jīng)過變換才是稀疏的，還有一種情況是在不同的環(huán)境中，信號的稀疏度可能是不一樣的，這幾種情況下信號的重構(gòu)誤差大，需要進(jìn)一步的研究來克服這個(gè)缺點(diǎn)。ROMP算法的步驟23:輸入：觀測值y,測量向量中，稀疏度K;輸出：重構(gòu)信號x；初始化：°=y，n=1,r0=4，a=4迭代：（1）gn=6Trn；（2）A=gn幅度的前K個(gè)最大值的索引;（3）利用正則化找到AUA,使得1g尸2|gJ對所有i,jwA成立；,nn4（4）1=1-上；(5)最小二乘法x；n=(；nGn)G；ny；(6)更新殘差/=y-rnxn；A(7)若|A戶2K,則停止迭代，貝U