基于自適應加速前向后向匹配追蹤的壓縮感知重構算法

潘作舟，孟宗，李晶，石穎

（燕山大學電氣工程學院，河北 秦皇島 066004）

1 引言

隨著社會的發展，人們的日常生活與工作都對信息的需求與日俱增，導致數據處理的任務量大幅上升，這就要求相關硬件設備與處理算法需要以極高的速度進行更新換代[1]。為了緩解硬件設備與處理算法的更新壓力，Cand 等[2]在2006 年提出了壓縮感知（CS,compressed sensing）[2-6]理論，該理論能夠克服Nyquist 采樣定理的限制問題，隨機采集到的信號在遠低于原始信號維數的情況下，依舊可以通過重構算法進行成功重構，極大地緩解了硬件設備與處理算法的壓力。其中，壓縮感知理論能夠實現低采樣率環境下的成功重構，最關鍵的環節便是重構算法的選取，優秀的重構算法能夠保證重構過程的高效率、重構結果的高精度。貪婪類算法和凸優化類算法作為信號重構中的2 類常見算法[7]，皆具備穩定的重構精度，但貪婪類算法因具有較快的速度和簡單的框架而得到更加廣泛的使用[8]。傳統的貪婪類算法主要包括匹配追蹤（MP,matching pursuit）算法[9]、正交匹配追蹤（OMP,orthogonal matching pursuit）算法[10]、正則化正交匹配追蹤（ROMP,regularized orthogonal matching pursuit）算法[11]等。值得注意的是，傳統的貪婪算法通常是根據支撐集的大小來確定算法的迭代次數，同時支撐集的大小是通過信號的稀疏度來進行設定的，因此稀疏度的確定直接影響到該類算法的重構精度。而將信號的稀疏度作為先驗條件，在實際信號的重構過程中往往難以實現，因此限制了該類貪婪算法的實際應用[12]。文獻[13]針對這一局限性提出了前向后向匹配追蹤（FBP,forward-backward pursuit）算法，利用前向后向兩步策略，逐步擴大支撐集進行重構，實現稀疏度未知情況下的精確重構。在此基礎上，文獻[14]提出了一種加速前向后向匹配追蹤（AFBP,acceleration forward-backward pursuit）算法，根據前向階段原子的累計權重，來對后向階段中被刪除的原子進行二次選入，減少了FBP 算法的迭代次數和運算時間。但AFBP 算法在二次選入過程中以權重作為判別標準，導致部分錯誤原子一直存在于支撐集中而無法被刪除，影響該算法的重構精度和重構時間。

針對AFBP 中存在的局限性，本文通過改變原子的選入方式[15]，解決后向階段中的回溯過度問題，得到了一種自適應加速前向后向匹配追蹤（AAFBP,adaptive AFBP）算法，該算法具備更高的重構精度和速度。

2 壓縮感知和重構算法

2.1 壓縮感知策略

壓縮感知理論的本質是將采樣與壓縮相結合，根據信號稀疏表示的先驗知識，采用少量非自適應線性測量的方式即可獲取原信號足夠的信息[16-17]。如待采樣信號xN×1，在Ψ域中稀疏，得到壓縮感知理論模型為

針對該理論模型，利用觀測矩陣ΦM×N對xN×1進行采樣（其中M≤N），得到觀測向量yM×1，即

可以得到

利用觀測矩陣yM×1求信號xN×1是一個欠定問題，無法直接求解。但當xN×1為一稀疏信號時，可以轉化為一個求解最小l0范數問題[18]，用公式表示為

式(4)是一個NP-Hard 問題，此類問題計算困難且穩定性較差，但匹配追蹤類方法為其近似求解提供了有力的工具。

2.2 加速前向后向匹配追蹤算法

FBP 算法屬于一種兩階段迭代算法。該算法在稀疏度未知的情況下，通過迭代以固定步長逐步擴大估計支撐集，最后實現對稀疏信號的逼近，雖然具備較高的重構精度，但運算時間較長。AFBP 算法在FBP 算法的基礎上，根據前向階段選入原子的投影值大小，將原子按從大到小的順序分為s1、s2、s3三部分，并分別為其賦予權重值w1、w2、w3。

在后向階段刪除原子后，并不直接進入下一次迭代過程，而是將刪除原子的權重與設定的閾值η相比較。當原子權重大于閾值時，則認為該原子有很大概率為正確原子，再次將其加入支撐集中，即在FBP 算法的基礎上增加了一條原子選入的渠道；當原子權重小于閾值時，則認為該原子為錯誤原子，不再考慮將該原子加入支撐集中。

該算法利用每次迭代中候選支撐集的信息，實現對已刪除原子的再次加入，以此減少算法迭代次數。相對傳統FBP 算法來看，AFBP 算法在保證較高重構精度的前提下，縮短了重構時間。但AFBP 算法在后向回溯過程中根據原子被賦予的權重大小判斷該原子是否進行二次選入，這種二次選入的標準需要通過大量選入、大量刪除的方式來避免錯誤原子的選入，增加了算法的運算量。此外，AFBP 算法中原子的權重值是通過迭代過程逐漸累加的，而權重值累加達到閾值條件需要一定時間，因此在迭代前期的加速效果并不明顯。而隨著迭代次數的增加，一些錯誤原子權重值逐漸累加達到閾值條件（當閾值設置較小時），錯誤原子就會被不斷選入，導致算法重構的時間增大，重構精度降低。

3 自適應加速前向后向匹配追蹤算法

3.1 自適應加速策略

本文針對AFBP 算法中的優缺點，給出了在保證重構精度前提下的自適應加速策略。首先介紹AAFBP 算法中的2 個模糊參數μ1、μ2，其中μ1為前向階段中原子的選入參數，μ2為后向階段原子的刪除參數。

μ1決定了算法在前向階段選取原子的數量，當μ1的值比較小時，每次迭代選入的原子數目比較多，算法執行的速度會更快。μ2則控制著每次迭代需要更新的原子數目，μ2越大則每次回溯過程中刪除的原子數越多，算法的成功重構率會有所提升，但是算法的執行速度會隨之下降。因此算法的成功重構率和重構時間可以通過調節μ1和μ2值來平衡。模糊參數μ1、μ2設定為

由于在每次迭代中通過模糊參數μ1/μ2選入/刪除的原子數目不是固定的，而是由每個原子在歷次迭代中的具體情況所決定的，從而使AAFBP 算法在每次迭代中自適應地決定所選入/刪除原子的數目。自適應加速策略為：在兩階段回溯過程中，首先根據觀測矩陣與殘差值之間的乘積值，得到各個原子所對應的相關系數值v。

在前向階段中，令原子相關系數v中的最大值vmax與μ1的乘積作為前向階段原子的選入閾值，從而選取相關系數較大的原子放入集合Tf中。

在與前一次迭代所得支撐集合并之后，利用最小二乘法求信號的投影系數，解決了AFBP 算法固定迭代選入的原子數隨機性較差[19]的問題。

在后向階段中，利用刪除參數μ2(0＜μ2＜1)來進行原子的自適應刪除。找出非零系數對應的索引在Tf里的最大投影系數υmax，將非零系數中大于μ2υmax的全部索引放入支撐集Tk中。這樣做的目的是隨著迭代次數的增加，當支撐集中增加了新的原子時，則重新計算信號的投影系數，若以前選入的原子對應的系數變小，小于刪除閾值μ2υmax，則以前選入的原子可能是錯誤的，這時通過回溯方式進行刪除。按照上述方法進行循環迭代，待達到停止條件時，則完成了對信號的重建，這解決了AFBP算法根據原子權重大小判斷該原子是否進行二次選入而存在的運算量過大、重構速度提升較為有限的問題。AAFBP 算法一方面加快了運算的速度，另一方面，由于刪除原子依靠的是原子的投影系數大小，因此相對于AFBP 算法來看，錯誤原子選入的可能性降低，成功重構率將有所提升。

3.2 回溯過度現象

在重構的過程中，為了保證選入原子與殘差的正交性，在每次迭代過程中將選入原子對應的觀測矩陣列中內容清零來避免原子的重復選入。而在回溯刪除錯誤原子的過程中，正確的原子也有被刪除的可能。正確原子一旦被刪除，其對應的觀測矩陣中內容則被清空，無法被再次選入，影響算法本身的精度，這種現象稱作回溯過度現象。圖1 展示了不同稀疏度下由于未及時更新觀測矩陣導致的正確原子被刪除的情況。

圖1 在不同稀疏度下由于回溯過度現象刪除的正確原子數

由圖1 可以看出，隨著稀疏度的增加，正確原子被刪除的概率近似呈直線增長，而正確原子的大量刪除會影響算法的精度。根據AFBP 算法中對刪除原子的二次選入方法，對回溯過度現象給出解決策略：首先將觀測矩陣Φ中的內容進行備份得到Φ1；其次在每次迭代完畢后，找出回溯刪除原子對應的清零矩陣列；最后利用備份觀測矩陣Φ1內的信息對清零矩陣列進行恢復。保證在下一次迭代計算殘差rk-1與觀測矩陣列的相關系數值時，正確原子存在二次選入的機會。

3.3 自適應加速前向后向匹配追蹤算法

依據上述加速策略，在每次迭代的前向階段中，根據原子和殘差的相關系數大小自適應地選取原子加入候選集Tf，再將每次迭代選入候選集中的原子加入支撐集Tk中。在后向階段中，通過設置的刪除閾值來選取刪除原子加入刪除原子集Tb，再通過刪除原子集更新支撐集中的內容。在回溯結束后，為了避免回溯過度現象，及時更新觀測矩陣列。以此進行循環迭代，直到殘差值達到終止條件后，循環結束。算法流程如下。

初始化殘差r0=y，初始支撐集Tk=?，初始索引集Tf=?。對觀測矩陣Φ進行歸一化處理。

步驟1利用模糊參數μ1來設置原子的選入閾值，選擇原子加入集合Tf。

步驟2對集合Tf中選入原子的相關系數進行正則化處理。

步驟3對觀測矩陣Φ中內容進行備份，令Φ1=Φ。

步驟4更新觀測矩陣，即{Φα=0|α∈Tf}。

步驟5將最新得到的索引與支撐集合并，即Tk=Tk-1∪Tf。

步驟6最小二乘處理，得到估計信號的投影系數，

步驟7利用模糊參數μ2來設置原子的刪除閾值，對支撐集中的原子進行回溯，找到投影系數小于閾值的原子放入集合Tb中，Tb={i|(v)i＜μ2max(υ)}。

步驟 8從支撐集中刪除錯誤原子，Tk=Tk-Tb。

步驟9將刪除原子對應的觀測矩陣列向量進行還原，即{Φβ內容還原|β∈Tb}。

步驟10殘差更新過程，即

步驟11如果滿足迭代終止條件||rk||2≤ε，則停止迭代。

輸出估計信號

4 實驗結果及分析

4.1 參數設置

對于FBP 算法，采用文獻[13]中給出的參數設置，即α∈[0.2M，0.3M]，α-β=1，支撐集最大限制參數。對于AFBP 算法，參數α、β以及Kmax與FBP 中保持一致。權重值和閾值參考文獻[14]給出：權重分為三層，其中w1=2，w2=1.5，w3=1；閾值參數設置為η1=5，η2=6，η3=7。通過選取合適的參數值，保證AFBP 算法具有較高成功重構率的同時，重構時間較短。

AAFBP 算法中所包含的2 個模糊參數μ1和μ2通過重構實驗來進行選取。分別取a={0.3，0.4，0.5}，μ2={0.6，0.7，0.8，0.9}進行信號的重構，重構結果如圖2 所示。其中a=0.3，a=0.4，a=0.5 分別用實線、虛線和點劃線來表示。而每種線型下4種不同的圖形，分別用來表示μ2=0.6，μ2=0.7，μ2=0.8，μ2=0.9 的情況。

圖2 不同參數情況下AAFBP 算法的重構結果比較

從圖2 中可以看出，當模糊參數為a=0.4、μ2=0.8時，AAFBP 算法成功重構率僅次于模糊參數為a=0.3、μ2=0.8 和a=0.4、μ2=0.9 這2 種情況。但在重構時間方面相較于二者有較大的縮短，該模糊參數下的平均歸一化最小均方誤差（ANMSE,average normalized mean squared error）值也相對較小。因此，在后面與FBP、AFBP 算法進行對比時，AAFBP算法的模糊參數設置為a=0.4、μ2=0.8。

4.2 一維稀疏信號重構

實驗所采用的稀疏仿真信號長度為N=256，觀測矩陣Φ為100×256 的Gauss 隨機矩陣，其中稀疏信號非零項分別服從Gauss 和均勻分布。算法迭代終止的閾值大小為ε，其中ε=10-3。

本文以成功重構率來衡量算法的重構精度。其中，成功重構的標準設定為：重構信號與原始信號的最大誤差值小于閾值ε1，即，閾值ε1=10-3。每種稀疏度情況下運行500 次，利用總的成功重構次數除以總運行次數來得到該稀疏度下的成功重構率。

平均重構誤差則采用平均歸一化最小均方誤差（ANMSE）進行衡量，定義為

將AAFBP 算法分別與AFBP 算法、FBP 算法進行成功重構率、重構時間以及平均歸一化最小均方誤差的比較，結果如圖3～圖5 所示。

1)當觀測信號為Gauss 稀疏信號時，AAFBP算法在不同稀疏度下與AFBP 算法、FBP 算法、OMP算法、SP 算法的性能比較如圖3 所示。由圖3 可以看出，FBP 和AFBP 算法的成功重構率接近且較高。這是由于FBP 算法都具備回溯的過程，因此成功重構率要優于OMP 算法和SP 算法。但回溯操作的引入導致FBP 算法的重構時間較長，其中，AFBP 算法相對FBP 算法的運行時間較短，但是時間縮短的程度并不高。本文提出的AAFBP 算法成功重構率最高，對FBP 算法重構時間的縮短程度要高于AFBP 算法。圖3(c)中也顯示了AAFBP 算法的相對誤差最小。由此可以看出，AAFBP 算法在兼顧重構性能的同時，對于重構時間的縮短也具備優勢。

圖3 高斯稀疏信號重構結果比較

2)當觀測信號為均勻稀疏信號時，AAFBP 算法在不同稀疏度下與AFBP 算法、FBP 算法、OMP 算法、SP 算法的性能比較如圖4 所示。圖4 測試結果與圖3 基本相似，不具備回溯過程的OMP 算法和SP算法的成功重構率相對較低，AAFBP 算法的成功重構率最高，略高于FBP 和AFBP 算法。在重構時間上可以看出，AAFBP 算法較AFBP 算法有明顯的縮短，當稀疏度K＜35 時，重構時間在5 種算法中最短；當稀疏度K≥35 后，重構時間依然要短于OMP 算法。在ANMSE 上，AAFBP 算法最低，即平均重構誤差最小。對比圖3 和圖4 可以發現，由于原始信號服從均勻分布時，非零元素幅度差異不明顯，通過Φrk-1方式選入錯誤原子的概率變大，FBP 類算法的重構性能下降，但AAFBP 算法相對AFBP 算法，無論在重構精度還是在重構時間方面，都依舊具備優勢。

圖4 均勻稀疏信號重構結果比較

圖5 觀測矩陣更新與否對重構結果的影響

3)為了進一步地分析回溯過度現象對于重構結果的影響，圖5 給出AAFBP 算法是否進行觀測矩陣更新操作所對應的不同稀疏度下的成功重構率、重構時間和ANMSE 值。其中實驗參數與上述一致，觀測矩陣為Gauss 隨機矩陣。從圖5 中可以看出，回溯過度問題對算法的成功重構率從K＞25后產生了較大的影響。由圖1 中可知，K＞25 后正確原子開始被刪除。同時隨著稀疏度增加，由于回溯過度現象，重構過程中算法的殘差值難以低于設定的停止閾值，回溯的迭代過程依靠設定的迭代次數上限來停止，導致回溯時間延長。從ANMSE 值中也可以看出，當K＞25 后，算法未進行觀測矩陣更新操作將產生更大的誤差。因此AAFBP 進行觀測矩陣的更新操作能夠有效避免回溯過度問題。

4.3 二維圖像重構

為了進一步驗證AAFBP 算法對實際非零稀疏分布信號的重構性能，選用256×256的‘Lena’圖像進行壓縮重構實驗[20]。其中實驗過程設置與文獻[12]保持一致，即將圖像分割成8×8 的小塊，將復雜的問題分解成一個個簡單的小部分。對于分割出來的小塊，令其在haar 小波基上稀疏度為K，即保證轉換到小波域時，僅保留K個較大的小波系數，其中K=12。對于每個分塊，信號長度為N=64，測量值M=32，即壓縮比為0.5。觀測矩陣ΦN×M是均值為0、方差為的高斯矩陣，并歸一化每一列。FBP 和AFBP 算法的前向后向步長一致，設置為α=10，β=9。AFBP 算法的權重設置為w1=2.0，w2=1.5，w3=1.0；閾值設置為η1=5，η2=6，η3=7。本文提出的AAFBP 算法的模糊參數設置為a=0.4，μ2=0.8。其中‘Lena’圖像的重構結果如圖6 所示。

圖6 ‘Lena’原圖像及各算法重構圖像

用峰值信噪比（PSNR,peak signal to noise ratio）和均方誤差（MSE,mean squared error）來進行圖像重構質量的判別，其中各算法的PSNR、MSE和重構時間如表1 所示。從表1 中可以看出，當壓縮比為0.5 時，AAFBP 算法重構效果最佳，PSNR值達到28.99 dB。重構時間低于AFBP 和FBP 算法的時間。因此AAFBP 算法有能力在保證重構質量的基礎上，減少重構所需的時間。

5 結束語

為了提升FBP 算法的運算效率，本文在AFBP算法的基礎上，提出了AAFBP 算法。該算法對AFBP算法在前向階段固定選入大量原子的操作進行改進，通過模糊參數自適應地選取合適數量的原子加入支撐集。在后向階段中以原子的投影系數大小作為其是否進行刪除的判別準則，避免AFBP算法中依賴權重作為判別準則所引入的誤差。同時，通過對觀測矩陣內容進行及時更新，來解決回溯過程中存在的回溯過度現象，提升了算法的重構精度。仿真實驗結果表明，AAFBP 算法在每次迭代過程中能夠保留更多正確的原子，因此該算法可以實現在提升重構質量的同時，降低算法的運行時間。

表1 壓縮比為0.5 時各算法重構質量及重構時間對比