步長自適應(yīng)的前向后向匹配追蹤算法

張松江 周 密 張傳林

(暨南大學(xué)信息科學(xué)技術(shù)學(xué)院 廣東 廣州 510000)

?

步長自適應(yīng)的前向后向匹配追蹤算法

張松江 周 密 張傳林

(暨南大學(xué)信息科學(xué)技術(shù)學(xué)院 廣東 廣州 510000)

稀疏度自適應(yīng)的匹配追蹤算法(SAMP)是基于壓縮感知理論的信號重建經(jīng)典算法。針對稀疏度未知的信號重建，提出步長自適應(yīng)的前向后向匹配追蹤(AFBMP)算法，AFBMP算法在稀疏度自適應(yīng)匹配追蹤算法的框架下，前向搜索過程中采用對數(shù)型自適應(yīng)變化的步長選擇匹配原子，然后通過后向策略修正前向階段造成的錯誤，刪除支撐集中的部分錯誤原子，最終實現(xiàn)信號的精確逼近。實驗表明AFBMP算法比SAMP算法能夠更加高效地重建稀疏度未知的信號。

壓縮感知 重構(gòu) 前向后向 稀疏度自適應(yīng) 匹配追蹤算法

0 引 言

隨著科學(xué)技術(shù)的飛速發(fā)展，在信號的采樣和處理過程中，利用信號的帶寬來表示信號已不能滿足現(xiàn)實的需要，因為隨著信號攜帶的信息量逐漸增加，采樣速度和處理速度就會變得越來越慢，同時這些數(shù)據(jù)的存儲問題也是不容忽視的。雖然人們采用一種壓縮的方式來表示信號，但是這種方式會導(dǎo)致大量的信息資源被拋棄，所以采用帶寬來表示信號的信息是不合理的。而信號的稀疏性是近幾年信號處理領(lǐng)域的新寵，它可以更加本質(zhì)地表示信號，因此基于信號的稀疏性提出的壓縮感知理論得到了廣泛的認(rèn)可。

壓縮感知理論(CS)[1,2]作為一種全新的采樣理論，利用隨機采樣獲取信號的離散樣本，然后通過非線性重建算法對信號進行重建。該理論指出：如果信號在某個變換域上是稀疏的或者認(rèn)為是可以壓縮的，那就可以通過一個新的觀測矩陣將高維的信號映射到一個低維空間中，這樣就可以將問題轉(zhuǎn)化為最優(yōu)化問題，進而重構(gòu)出原始信號。該理論通過稀疏性以及等距約束準(zhǔn)則來完成高速率的采樣，又包含了大量的重要信息。壓縮感知理論因為可以同時完成數(shù)據(jù)的采集和壓縮，大大節(jié)約了時間和資源，所以得到了廣泛的應(yīng)用。

雖然壓縮感知理論可以大大降低采樣和計算的成本，但是如何設(shè)計出一種快速的魯棒的重建算法是該理論的核心問題。隨著對CS理論研究的不斷深入，為了通過低維數(shù)據(jù)來實現(xiàn)對原始信號的重構(gòu)，近年來越來越多的重構(gòu)算法被提出。目前貪婪迭代算法是學(xué)者們研究最多的算法，這種算法重構(gòu)精度高、計算量小并且易于實現(xiàn)。比如Mallat等人采用正交策略提出了正交匹配追蹤算法(OMP)[4,5]、Needell又在正交匹配追蹤算法放入基礎(chǔ)上加入正則化思想，提出正則化正交匹配追蹤算法(ROMP)[6]、Tropp根據(jù)隨機測量矩陣思提出了壓縮采樣匹配追蹤算法(CoSaMP)[7]、Dai借鑒回溯序貫編碼理論，提出了子空間追蹤算法(SP)[8]以及Donoho等人考慮稀疏度未知的情況，打破傳統(tǒng)局限，提出了一種稀疏度自適應(yīng)的匹配追蹤算法(SAMP)[9,10]。貪婪迭代算法因其重建速度快和精度高而得到廣泛應(yīng)用，然而大部分貪婪算法都是通過已知稀疏度來控制算法重建的迭代次數(shù)，而在實際問題中，稀疏度不一定是已知的，并且當(dāng)稀疏度固定時也可能會對重構(gòu)精度造成影響。

SAMP算法突破了傳統(tǒng)的匹配算法要以稀疏度已知為前提的限制，解決了在稀疏度未知的條件下的重建問題。SAMP算法的重建速度主要取決于固定步長的選擇，雖然在重構(gòu)精度上有了一定的提高，但是依然不能得到滿意的效果。另外根據(jù)該算法的迭代機制，每次迭代過程中都會增加支撐集中的原子個數(shù)，這樣就會有越來越多的原子被加入到支撐集中，而又無法刪除支撐集中部分錯誤原子，所以該算法有一定的局限性。為了解決這一問題，有學(xué)者提出了MSAMP算法[11]，該算法在SAMP算法的框架下通過原子匹配估計稀疏度，然后利用階段步長來實現(xiàn)對原始信號的估計，但這種算法在同一階段的步長依然是一個固定值，因此重構(gòu)精度很大程度上依賴于每個階段步長的選擇。而LSAMP算法[12]則是在不同的階段采用了對數(shù)型變化的步長，該算法在采樣率較低時重構(gòu)效果依然很好。但是這些算法本質(zhì)上都屬于前向貪婪算法，前向算法最大的缺點就是不能修改前一步迭代造成的錯誤，原子一旦被選入支撐集便無法刪除。例如圖1所示，假設(shè)特征向量x是由觀測矩陣中的向量α1、α2構(gòu)成，然而觀測矩陣中另外一個向量α3比其他兩個向量更接近特征向量x，這樣當(dāng)采用像OMP、SAMP這類前向貪婪算法時首先會選擇α3，之后才會選擇α1、α2，并且這類算法還不能刪除α3，這樣的結(jié)果并不是我們想要的。事實上，只有在觀測矩陣中的向量不相關(guān)時前向貪婪算法才比較適用。

圖1 特征向量圖示

考慮到前向貪婪算法的缺點，很容易想到利用后向貪婪算法來進行改善。后向貪婪算法首先選擇全部原子，然后逐一刪除使重建誤差最小的原子。這種算法雖然不會陷入局部最優(yōu)問題，但是其計算代價非常高，因為一般情況下觀測矩陣中M<

目前壓縮感知理論在很多方面得到了應(yīng)用，比如：吳延海提出了基于改進SP算法的壓縮感知圖像重構(gòu)[13]，廖斌提出了一種基于壓縮感知的盲數(shù)字水印算法[14]，李秀霞提出了基于壓縮感知的合成孔徑雷達圖像目標(biāo)識別[15]等。越來越多的學(xué)者們將壓縮感知利用到人臉識別、醫(yī)學(xué)CT圖像重建、語音識別、衛(wèi)星遙感圖像融合、無線傳感器網(wǎng)絡(luò)、探地雷達成像中。因此對壓縮感知理論的進一步研究就變得十分有意義。

1 壓縮感知理論以及重構(gòu)算法

假設(shè)x為長度為N的原始稀疏信號，即x的稀疏度為K，K<

通常采用求解以下最優(yōu)化問題來從測量信號y中重建出信號x：

min‖x‖0s.t. y=Φx

(1)

對于式(1)求最優(yōu)解問題是NP難題[16-18]，而最小化l2范數(shù)問題又不能保證解的稀疏性。但是Candes等人指出，如果x足夠稀疏，Φ滿足約束等距條件RIP(Restricted Isometry Property)[19]時：

(2)

其中， δK∈(0,1)表示K稀疏度下的約束等距常數(shù)，此時就可以將問題轉(zhuǎn)化為求解l1范數(shù)最小化：

min‖x‖1s.t. y=Φx

(3)

通過利用匹配追蹤算法就可以進行對式(3)的近似求解。OMP算法、ROMP算法等都是在給定稀疏度的基礎(chǔ)上進行的重構(gòu)，然而在實際應(yīng)用中，信號的稀疏度K往往是未知的，這在一定程度上給信號的重構(gòu)帶來了挑戰(zhàn)，于是Thong T.Do等人為了解決這一問題，提出了稀疏度自適應(yīng)的匹配追蹤算法，將信號重構(gòu)問題轉(zhuǎn)化為分階段處理的過程，打破了傳統(tǒng)的稀疏度已知的限制。之后更多學(xué)者專注于對SAMP算法的改進，比如變步長的MSAMP算法和對數(shù)型變步長的LSAMP算法。這些算法很好地解決了步長固定問題，重構(gòu)效果也得到了很大的改善。

2 SAMP算法及其改進

SAMP算法實現(xiàn)了在稀疏度未知的情況下對信號的重構(gòu)。該算法首先選取步長step，然后計算余量r和觀測矩陣Φi的內(nèi)積，其中Φi表示觀測矩陣的每一列，根據(jù)內(nèi)積值，選取size個最大的相關(guān)系數(shù)，將這些系數(shù)所對應(yīng)的原子加入到索引集中。接著合并上一階段產(chǎn)生的支撐集得到候選集，再進行一次余量與候選集的內(nèi)積，同樣選取size個相關(guān)系數(shù)最大的原子作為支撐集F。此時更新余量r，如果當(dāng)前余量小于迭代前的余量，則繼續(xù)迭代，否則進入下一階段，根據(jù)步長更新支撐集容量size=size×step，重復(fù)上述步驟，直到余量r小于某個閾值停止迭代。

具體算法如下：

(1) 余量r=y，支撐集長度size=step，階段stage=1，支撐集F=?；

(2) 計算余量r和Φi內(nèi)積的絕對值，從中選取size個最大值對應(yīng)的索引值得到索引集S；

(3) 將索引集與上一階段的支撐集進行合并，得到候選集C=F∪S，再計算候選集與余量的內(nèi)積，并提取size個最大值，將其相對應(yīng)的原子加入到支撐集Fnew；

(5) 若‖rnew‖2≥‖r‖2，則進行下一迭代階段，stage=stage+1，利用初始步長更新支撐集容量size=stage×step，返回步驟(2)繼續(xù)迭代；否則更新支撐集和余量F=Fnew，r=rnew，此時迭代次數(shù)k=k+1，返回步驟(2)繼續(xù)迭代。

從上述算法中可以看到各個迭代階段步長step的取值是一個常數(shù)，步長的選擇關(guān)系到支撐集的容量，因此該算法的重構(gòu)精度與該步長選擇有很大的關(guān)系。但是該算法的最大缺點就是不能后向刪除部分錯誤原子，在原子的原子過程中很有可能會產(chǎn)生一些錯誤的、冗余的原子，如果沒有辦法進行二次修正，不僅會影響算法的時間，也會影響算法的精度。因此本文結(jié)合以上算法的優(yōu)點，針對不能后向刪除錯誤原子提出了利用對數(shù)型自適應(yīng)變化步長的前向后向算法來實現(xiàn)信號的重建。

3 步長自適應(yīng)的前向后向匹配追蹤算法

SAMP算法雖然突破了在傳統(tǒng)匹配算法中對稀疏度的限制，但是通過相關(guān)實驗表明，為了加快重構(gòu)速度，初始步長step取較大值時，算法只需要很少的迭代次數(shù)，但是算法的效率就會很低。如果想保證算法的重構(gòu)精度，step取很小的值時，迭代次數(shù)就會大大增加。另外傳統(tǒng)的算法在選擇原子過程中支撐集的容量是不斷增加的，但是又無法刪除那些錯誤的或者冗余的原子。因此選取合適的步長和利用后向策略來對算法進行修正是提高算法性能的關(guān)鍵。根據(jù)文獻[12]結(jié)合對數(shù)函數(shù)的性質(zhì)，在SAMP算法的框架下，提出了步長自適應(yīng)變化的前向后向匹配算法。該算法首先進行前向選擇匹配原子，然后進行向后剔除部分錯誤原子[20]，在確保重建精度的情況下，彌補了前向貪婪算法自身的缺點。接下來將從兩個方面對新算法進行具體描述：步長選擇和算法描述。

3.1 步長選擇

根據(jù)相鄰迭代階段重建信號差的變化規(guī)律，設(shè)置兩個閾值ε1、ε2(ε1>ε2)，當(dāng)‖xt-xt-1‖>ε1時，選取一個較大的步長，實現(xiàn)快速逼近；當(dāng)ε2<‖xt-xt-1‖<ε1時，選取較小的步長，以實現(xiàn)逐漸逼近，此時步長變?yōu)樯想A段步長的一半；當(dāng)‖xt-xt-1‖<ε2時說明相鄰階段的能量差變化趨于平穩(wěn)，則停止迭代。

設(shè)步長step為：

step(s)=alog2s+b

(4)

(5)

而當(dāng)采取緩慢逼近策略時就選取前一階段步長的一半，即：

(6)

這里的步長均向上取為正整數(shù)，c≥1的正整數(shù)，M、N分別表示觀測信號和待估信號的長度。

3.2 算法描述

(1) 初始化稀疏度：余量r=y，支撐集F，支撐集長度size=step，階段stage=1，迭代次數(shù)t=1，索引值集合S=?，候選集C=?；

(2) 計算相關(guān)系數(shù)，從中提取size個最大值對應(yīng)的索引值放入到集合S中；

(3) 合并索引集S與支撐集F，得到候選集C=F∪S，再計算候選集中索引值對應(yīng)的原子與余量的內(nèi)積，并提取size個最大值對應(yīng)的索引值得到新的支撐集F；

(4) 由最小二乘得到xt=argmin‖y-ΦFxt-1‖2，更新余量rt=y-Φtxt-1；

(5) 如果‖xt-xt-1‖>ε1則轉(zhuǎn)步驟(6)，否則轉(zhuǎn)步驟(8)；

(6) 如果‖rt‖≥‖rt-1‖則轉(zhuǎn)入步驟(7)，否則轉(zhuǎn)入步驟(9)；

(7) 進入下一階段，stage=stage+1，利用式(5)求出新步長step，擴大支撐集大小size=size+step，t=t+1,返回步驟(2)；

(8) 如果‖xt-xt-1‖<ε2則停止迭代，否則轉(zhuǎn)入步驟(10)；

(9) 更新支撐集和余量返回步驟(2)繼續(xù)迭代；

(10) 進入小步長階段，stage=stage+1，利用式(6)求出新步長step，擴大支撐集大小size=size+step，t=t+1，返回步驟(2)；

(12) j=argmini∈Fq(F/i)；

(13) d-=q(F/j)-q(F)；

(14) d+=ε3；

(15) 如果d-d+；

4 實驗與分析

實驗一

為了驗證本文算法的有效性，通過MATLAB處理平臺對該算法進行了驗證。實驗一中采用長度為N=256的一維高斯稀疏信號，觀測矩陣為部分快速傅里葉變換矩陣(FFT)。閾值設(shè)置為ε1=e-6，迭代停止條件閾值ε2=e-12，ε3=e-14。在實驗一中比較了SAMP算法、MSAMP算法、LSAMP算法和AFBMP算法在不同采樣率下的重構(gòu)效果。實驗中除本文算法以外其他算法的參數(shù)均按照原參考文獻中設(shè)置。實驗表明該算法的重構(gòu)效果很好，相對誤差非常小，能夠很好地對原始信號進行重建，在理論上說明了新算法的有效性。

圖2是SAMP、MSAMP算法、LSAMP算法與AFBMP算法在不同采樣率下重構(gòu)信號信噪比的比較。其中橫坐標(biāo)表示采樣率，縱坐標(biāo)為信噪比，實驗結(jié)果顯示，該算法在前向階段通過采用對數(shù)型變化的步長選取匹配原子，后向階段刪除錯誤原子，使得該算法的性能得到了明顯的提升，AFBMP算法提高了對原始信號的重構(gòu)精度。

圖2 不同采樣率下重構(gòu)信號的信噪比

圖3比較了四種算法在不同采樣率下的重構(gòu)相對誤差。實驗發(fā)現(xiàn)，SAMP算法在不同采樣率下的重構(gòu)誤差相對很高，而MSAMP算法和LSAMP算法是對原來算法的改進在一定程度上均降低了重構(gòu)的相對誤差，而AFBMP算法結(jié)合了前面幾種算法的優(yōu)點，使得重構(gòu)相對誤差變得更低。我們發(fā)現(xiàn)，在相同采樣率下，AFBMP算法比其他三種算法的相對誤差低很多，因此該算法充分保證了對稀疏信號的重構(gòu)精度，同時也證明了該算法的有效性。

圖3 不同采樣率下幾種算法的相對誤差

實驗二

為了更為充分地說明新算法在實際問題中的應(yīng)用，本文實驗二對大小為256×256的圖像進行實驗。閾值設(shè)置為ε1=e-6，迭代停止條件閾值ε2=e-12，ε3=e-14。將本文算法和經(jīng)典SAMP算法、MSAMP算法對三組測試圖像進行比較。圖4表明，改進的SAMP算法重構(gòu)效果均好于經(jīng)典SAMP算法，而AFBMP算法的重構(gòu)效果也明顯好于其他算法，同時也證實了本文算法的實用價值。

圖4 二維圖像重建效果

表1是這三組測試圖進行重構(gòu)的運行時間，從上節(jié)的實驗可知不同的采樣率下對算法性能的影響很大，因此采樣率為0.5的情況下重構(gòu)時間如表1所示。

表1 不同圖像不同算法的重構(gòu)時間

通過表1可以看出在相同的采樣率下，對于不同的圖像，各種算法的重構(gòu)時間也有所不同，而AFBMP算法的重構(gòu)時間略低于傳統(tǒng)的SAMP算法，進一步說明了本文算法在運行時間上有一定的優(yōu)勢。

5 結(jié) 語

本文深入研究了壓縮感知理論的經(jīng)典算法，在稀疏度未知的情況下結(jié)合SAMP算法，提出了一種對數(shù)型自適應(yīng)步長的前向后向匹配算法。SAMP算法在迭代過程中固定步長可能會導(dǎo)致過估計或者欠估計的問題，并且迭代結(jié)束之后不能刪除某些冗余原子和錯誤原子。針對這兩個問題，在SAMP算法框架基礎(chǔ)上，前向迭代過程中采用改進的對數(shù)型可變化的步長選取匹配原子，而向后階段逐一測試支撐集中的每一個原子，刪除前向階段所產(chǎn)生的錯誤原子，通過設(shè)置雙閾值來控制步長選擇和停止準(zhǔn)則，分段逐步實現(xiàn)對稀疏度的逼近，最終實現(xiàn)信號的精確重構(gòu)。實驗結(jié)果表明，新算法可以較好地實現(xiàn)未知稀疏度信號的重建，且重建性能明顯優(yōu)于SAMP算法。

[1] Candes E J,Wakin M B.An introduction to compressive sampling[J].IEEE Signal Proc Mag,2008,25(2):21-30.

[2] Donoho D L.Compressed sensing[J].IEEE Transactions on Information Theroy,2006,52(4):1289-1306.

[3] Chen S B,Donoho D L,Saunders M A.Atomic decomposition by basis pursuit[J].SiamJ.Sci.comput,2001,20(1):129-159.

[4] Mallat S,Zhang Z.Matching Pursuit with time-frequency dictionaries[J].IEEE Trans.Sig.Proc,1993,41(12):3397-3415.

[5] Tropp J,Gilbert A.Signal recovery form random measurements via orthogonal matching pursuit[J].IEEE Transactions on Information theory,2007,53(12):4655-4666.

[6] Needell D,Vershynin R.Signal recovery from incomplete and inaccurate measurements via regularized orthogonal matching pursuit[J].IEEEJournal of Selected Topics in SignalProcessing,2010,4(2):310-316.

[7] Needell D,Tropp J A.Iterative signal recovery from incomplete and inaccurate samples[J].Applied and Computational Harmonic Analysis,2009,26(3):301-321.

[8] Dai W,Milenkovic O.Subspace pursuit for compressive sensing signal reconstruction[J].IEEE Transactions on information theory,2009,55(5):2230-2249.

[9] 郭永紅,楊毅彬.一種稀疏自適應(yīng)的正交互補匹配追蹤算法[J].計算機工程與應(yīng)用,2013,49(7):144-146.

[10] Donoho D L,Tsaig Y,Drori I,et al.Sparse solution of underdetermined linear equations by stage wise orthogonal matching pursuit[J].IEEE Transaction on Information Theroy,2012,58(2):1094-1121.

[11] 朱延年,趙擁軍,孫兵.一種改進的稀疏度自適應(yīng)匹配追蹤算法[J].信號處理,2012,28(1):80-86.

[12] 畢學(xué)霞,尚振宏.一種基于變步長的稀疏度自適應(yīng)匹配追蹤算法[J].系統(tǒng)仿真學(xué)報,2014,26(9):2116-2125.

[13] 吳延海,閆迪.基于改進SP算法的壓縮感知圖像重構(gòu)[J].計算機應(yīng)用與軟件,2013,30(7):200-203,216.

[14] 廖斌,任美玲,徐俊剛.一種基于壓縮感知的盲數(shù)字水印算法[J].計算機應(yīng)用與軟件,2014,31(2):307-311.

[15] 季秀霞,卞曉曉.基于壓縮感知的合成孔徑雷達圖像目標(biāo)識別[J].計算機應(yīng)用與軟件,2013,30(12):120-123.

[16] 李然,干宗良,朱秀昌.基于最佳線性估計的快速壓縮感知圖像重建算法[J].電子與信息學(xué)報,2012,34(12):3006-3012.

[17] Baraniukr R.Compressive sensing[J].IEEE Signal Processing Magazine,2007,24(4):118-126.

[18] Candes E,Romberg J,Tao T.Robust uncertainty principles:exact signal reconstruction from highly incomeplete frequency information[J].IEEE Transactions on Information Theory,2006,52(2):489-509.

[19] Do T T,Gan L,Nguyen N,et al.Sparisity adaptive matching pursuit algorithm for practical compressed sensing[J].IEEE Asilomar Conference on Signals,Systems and Computers,2008,10(7):581-587.

[20] Wei Tang,Zhenwei Shi.Regularized simultaneouss forward-backward greedy algorithm for sparse unmixing of hyperspectral data[J].IEEE Transactions on geoscience and remote sensing,2014,52(9):5271-5288.

ADAPTIVE STEPSIZE FORWARD-BACKWARD MATCHING PURSUIT ALGORITHM

Zhang Songjiang Zhou Mi Zhang Chuanlin

(School of Information and Science Technology,Jinan University,Guangzhou 510000,Guangdong,China)

Sparsity adaptive matching pursuit algorithm (SAMP) is a classical algorithm of signal reconstruction based on compressed sensing theory. Aiming at reconstructing signals with unknown sparsity, we presented an adaptive stepsize forward-backward matching pursuit algorithm (AFBMP). In the framework of SAMP, AFBMP selects matching atoms in its forward search process by using logarithmic adaptive changing steps, and then amends the mistakes caused in forward stage by backward strategy to delete part of the false atoms in support set, and finally realises accurate signal approaching. Experiments show that the AFBMP algorithm can reconstruct the signals with unknown sparsity more efficiently than SAMP algorithm.

Compressed sensing Reconstruction Forward-backward Sparsity adaptive Matching pursuit algorithm

2015-09-15。張松江，碩士，主研領(lǐng)域：圖像處理。周密，碩士。張傳林，教授。

TP391.9

A

10.3969/j.issn.1000-386x.2016.11.057