呂冠男， 劉海鵬， 王 蒙， 盧建宏

(昆明理工大學 信息工程與自動化學院， 云南 昆明 650500)

壓縮感知(Compressed Sensing，CS)[1-3]是近年來新興的信號獲取理論，它表明當一個信號是稀疏信號，或者說這個信號具有稀疏性，就可以用一個與原信號不相關的測量矩陣，以遠低于奈奎斯特(Nyquist)采樣率采集到的信號測量值進行壓縮采樣，用重構算法將壓縮采樣后的信號實現(xiàn)對原信號的高概率重建。壓縮感知具有所需采樣點少、數(shù)據(jù)儲存量低等特點，在信號采集[4]、雷達探測、數(shù)據(jù)通信[5]等領域被廣泛研究。

目前對壓縮感知理論所做的研究主要集中在信號重構算法上，而貪婪算法由于其計算結果的有效性和穩(wěn)定性得到廣泛研究。例如，前向搜索正交匹配追蹤(Look Ahead Orthogonal Matching Pursuit，LAOMP)算法[6]。

雖然LAOMP算法目前已經(jīng)得到了較為廣泛的應用，但是LAOMP算法是在稀疏度k已知的條件下進行的，同時選擇的L個最大內(nèi)積值未必是最佳值，所對應的原子索引也未必是最佳的索引值。因而通過LAR得到最小殘差也未必是最小的，這就意味著可以在提升LAOMP的重構精度上做工作。因此，本文在繼承LAOMP算法優(yōu)點的同時，對其不足之處加以改正，提出了一種基于稀疏度自適應的回溯前向搜索正交匹配追蹤(Sparsity Adaptive Backtracking Look Ahead Orthogonal Matching Pursuit，SABLAOMP)算法。SABLAOMP算法首先通過回溯策略選擇能量組最大的原子集，然后將這些能量最大的原子加入到LAR中，根據(jù)殘差性能選擇加入支撐集的原子的個數(shù)，更新支撐集，更新殘差，自適應地更新步長，使得支撐集中的原子構造更加合理，提升了重構效果。

1 算法描述

1.1 LAOMP算法

正交匹配追蹤(Orthogonal Matching Pursuit，OMP)算法發(fā)展較早[6]，為后面的各種同類型算法的提出奠定了基礎，它繼承了匹配追蹤(Matching Pursuit，MP)算法在傳感矩陣中挑選原子的方式，由于MP算法在進行投影時，所選用的列向量之間不具備正交性，故而任意一次迭代都可能達不到理想的結果。針對MP算法的缺點，OMP算法作出了改進，在投影之前通過正交化方法對篩選的原子進行正交處理，這樣就能使反復挑選到同一個原子的概率幾乎為0，從而保證了每次迭代的最優(yōu)性，不僅能加快算法的收斂速度，同時還提高了重構精度。但是Saikat Chatterjee[7-9]等反復試驗發(fā)現(xiàn)OMP算法每次進行原子選擇時不一定選擇了最優(yōu)原子，于是在OMP算法的基礎上提出了LAOMP算法。

前向搜索殘差[10](Look Ahead Residual，LAR)是LAOMP篩選原子的主要手段。所謂的LAR就是在算法的迭代中，通過對未來迭代的影響來選擇原子。首先，該算法選擇L個與傳感矩陣內(nèi)積最大的原子，并將這L個原子的下標存儲在一個集合;然后把這L個原子逐個放入LAR中迭代，L個原子通過前向預測會得到L個殘差，殘差最小的那個原子就是最佳原子;再把最佳原子加入原子集，更新殘差，進行下次迭代，迭代結束，輸出近似信號，完成重構。

LAOMP算法的核心就是LAR算法，具體描述如下：

輸入：感知矩陣A，測量向量Y，稀疏度K，先前支撐集Ipre，新選擇的原子索引t。

迭代過程：

1)迭代次數(shù)k=1：K；

3)更新支撐集Ik=Ipre∪tk；

5)更新殘差rk=Y-AIkΘIk；

6)判斷是否滿足迭代停止條件‖rk‖2>‖rk-1‖2，若滿足，則停止迭代，否則，重復步驟1—6。

輸出：rk=Y-AIkΘIk。

LAR算法中A={aij}，i∈M，j∈N，Y∈RM，t∈{1，2，…，N}?；贚AR算法中LAR的迭代過程定義前向預測殘差為

r=LAR(Y,A,K,Ipre,t)。

(1)

1.2 SABLAOMP算法

雖然LAOMP算法選出的迭代原子比OMP算法選出來的質(zhì)量更高，但是LAOMP算法是在稀疏度K已知的條件下進行的，同時選擇的L個最大內(nèi)積值未必是最佳值，所對應的原子索引也未必是最佳的索引值，因而通過LAR得到最小殘差也未必是最小的；其次,當?shù)啻魏髷?shù)個殘差性能均能小于τ(定義τ作為判決殘差性能趨于穩(wěn)定的門限值，τ一般取10-6)，如果每次仍然固定的選擇L個最佳原子加入到LAR中，并且每次仍只選擇一個殘差值，這樣就增加了迭代的次數(shù)耗費了時間。為了解決這些問題，本文提出了SABLAOMP算法，該算法在保證不失LAOMP算法優(yōu)良性能的同時克服其不足之處。SABLAOMP算法首先通過回退篩選[11]的思想選擇能量組最大的原子集，再通過最小二乘法求得此原子集中每個原子的重構系數(shù)θ，選出系數(shù)最大的前L個原子，并將這些原子一一加入到前向預測中，根據(jù)殘差性能選擇加入支撐集的原子個數(shù)，更新支撐集，更新殘差，自適應的更新步長，判斷是否滿足終止條件，從而輸出結果。

SABLAOMP算法的核心由回溯策略和LAR子算法組成。回溯策略具體操作如下：

輸入：感知矩陣A，測量值y，稀疏度K。

初始化：矩陣空集A0=?，索引集合Λ0=?，初始殘差r0=y，迭代次數(shù)t=1，索引值集合J0=?，重構值初始化θ=0。

1)利用u=|Art-1|，求得u中K個較大的值，然后將這K個值對應的序列號j構成集合J0；

2)更新索引集Λt=Λt-1∪J0，At=At-1∪aj(其中所有的j∈J0)；

4)更新集合Λt=ΛtK，并更新殘差rt=y-Atθt；

5)通過判斷滿足‖rk‖2>‖rk-1‖2和迭代次數(shù)t≥K來輸出重構系數(shù)θtK和其對應原子索引值ΛtK，否則循環(huán)(1—5)。

輸出：重構系數(shù)θtK、θtK對應原子索引值ΛtK。

匹配追蹤(Matching Pursuit)算法、OMP算法、正則化正交匹配追蹤[12](Regularization Orthogonal Matching Pursuit，ROMP)算法以及稀疏自適應匹配追蹤[13](Sparsity Adapitive Matching Pursuit，SAMP)算法、LAOMP算法等，都是通過每一次的迭代來尋找最佳原子。但是由于數(shù)據(jù)的隨機不確定性，導致選出來的原子不一定是最佳原子。因此SABLAOMP算法在此基礎上引入回溯策略，該算法在不需要知道信號稀疏度的情況下，選擇出最大內(nèi)積值所對應的若干個原子，然后在這些原子中選擇出能量組最大的原子，將原子的索引值加入到支撐集中，再將這些索引值進行LAR處理。由于迭代初期處理后的殘差值相差較大，因此為了得到更好的殘差需要在LAR算法中迭代多次判斷殘差的性能，而隨著迭代次數(shù)的增多，相鄰內(nèi)積值間的差別逐漸縮小再迭代多次已沒必要，因此本論文選擇的迭代次數(shù)為floor(M/L)次。隨著迭代次數(shù)的增多，L也會自適應的增大，故而迭代次數(shù)就會減少，正合本文要求。如果經(jīng)過LAR輸出的殘差值中有f個值小于τ，那么就將這f個值對應的F位置加入到支撐集，否則直接將最小的一個殘差所對應的F中的位置加入支撐集，更新近似系數(shù)，更新殘差，自適應的更新步長，判斷是否滿足終止條件，輸出近似系數(shù)。具體描述如下：

輸入：感知矩陣AM×N，測量矩陣YM×1，初始步長S。

初始化：近似系數(shù)Θ=0，初始殘差r0=Y，支撐集I=?，步長L=S，pos_theat=。

起始階段：Stage=1，最大循環(huán)次數(shù)Itermax=M，迭代次數(shù)K=floor(M/L)。

迭代過程：

1)外部循環(huán)次數(shù)k=1：Itermax；

2)A的各列與殘差的內(nèi)積P=ATrk-1；

3)從P中選取L個具有較大能量的原子所對應的索引序號，將它們放入支撐集Jl中；

4)內(nèi)部循環(huán)次數(shù)l=1：f，

a)由LAR得到殘差值r=(Y，A，K，pos_theta，Jl)，

b)存儲殘差nf=‖r‖2，

c)根據(jù)殘差值的大小確定更新索引值ik的個數(shù)；

5)更新支撐集Ik=Ik-1∪ik；

7)存儲支撐集pos_theta=Ik；

8)更新殘差rk=Y-ΘIk；

9)若參數(shù)滿足：‖rk‖2≥‖rk-1‖2或者norm(rk，2)<τ，更新步長Stage=Stage+1，L=Stage×S；

10)判斷迭代停止條件k≥Itermax或者L>M。

2 實驗部分

以下仿真結果均在MATLAB R2017a環(huán)境下進行得到，稀疏基矩陣和觀測矩陣[14-15]均選擇小波變換正交基和高斯隨機矩陣[16-17]。

2.1 一維試驗仿真及分析

首先，為了驗證本文提出的改進算法，即SABLAOMP算法，能否實現(xiàn)信號的高精度重構，先對其進行一維點目標重構實驗，其中信號的個數(shù)設置為256，稀疏度K設定為12，測量值的個數(shù)為128，實驗結果如圖1所示。圖中不帶點的線表示原始信號，帶點的線表示重構信號，在這個圖中可以看出帶點線和不帶點線基本是重合的，且重構誤差為5.532 5×10-15，算法收斂時間約為0.17 s。由此可以看出，本文算法可以實現(xiàn)一維信號的高精度重構。

圖1 SABLAOMP算法的一維重構實驗

然后,在不考慮噪聲的情況下，通過精確重構率(ERP)性能指標測試SABLAOMP算法的重構性能，并與OMP算法、LAOMP算法、ALAOMP算法對比。設原始信號X為長度N=700的高斯隨機信號和N=500的二值信號，當X為高斯隨機信號時采樣率區(qū)間設為[0.1，0.2]共11個點，測量次數(shù)為200次。當X為二值信號時采樣率區(qū)間設為[0.1，0.3]共11個點，測量次數(shù)為200次。由于OMP算法、LAOMP算法、ALAOMP算法需要知道信號的稀疏性，因此設稀疏度K=20，LAOMP算法的前向參數(shù)設為L=5，SABLAOMP算法的初始步長設為S≤5，判決門限τ=10-12。對比結果如圖2、圖3所示。

圖2 高斯信號下的ERP對比圖 圖3 二值信號下的ERP對比圖

隨著壓縮率的增大，4種算法的ERP均增大，但本文算法的增大效果更明顯。在高斯隨機信號下當采樣率相同時，本文算法的ERP要比其他4種算法效果好，同時隨著壓縮率的增大ERP增長的更快，在采樣率達到0.15時ERP就已趨近于1(見圖2)，優(yōu)于其他3種算法。而在二值信號下，由于二值信號的二值固定性，導致采樣率低于0.16時效果不明顯(見圖3)，但當采樣率高于0.16時，ERP明顯上升，SABLAOMP算法的ERP在0.24時就已趨近于1，其他3種算法均未達到此效果，這充分體現(xiàn)了本文算法的優(yōu)越性。

2.2 二維圖像重構實驗比較

為了進一步說明改進后算法的優(yōu)良性，本文給出了OMP算法、LAOMP算法、ALAOMP算法、SABLAOMP算法在采樣率分別為0.3、0.4和0.5時的二維圖像重構直觀視覺效果對比圖。仿真結果如圖4—圖6所示?？梢钥闯?，對于同一張圖片，隨著采樣率的增加圖像變得越來越清晰，當采樣率為0.3時圖像相對來說最模糊，采樣率為0.4時圖像比采樣率為0.3時要清晰許多，而采樣率為0.5時圖像最為清晰；而不論采樣率為何值時，本文提出的SABLAOMP算法重構后的圖像均比其他算法重構后的圖像清晰。

(a)原始圖像 (b)OMP重構圖像 (c)LAOMP重構圖像

(a)原始圖像 (b)OMP重構圖像 (c)LAOMP重構圖像

(a)原始圖像 (b)OMP重構圖像 (c)LAOMP重構圖像

以重構圖像的峰值信噪比(PSNR)和相對誤差(RE)作為圖像恢復質(zhì)量的評判依據(jù)，不同的采樣率下4種算法的結果見表1。從表中可知，當采樣率固定為某個值時，SABLAOMP算法的PSNR最大，RE最小，說明SABLAOMP算法的重建質(zhì)量優(yōu)于其他算法；隨著壓縮比的增大，各算法的PSNR均增大，RE均減小，且SABLAOMP的效果最為明顯，其PSNR相比于其他3種算法提高了約25%，而RE相比于其他算法減少量超過了三分之一。進一步說明的本算法的重構效果優(yōu)于其他3種算法。

表1 壓縮比為0.3時二維圖像重建質(zhì)量比較

3 結論

本文就LAOMP的不足之處進行改進，引入了回溯策略，加強了對原子的選擇，提出了稀疏度自適應的回溯前向搜索正交匹配追蹤算法，即SABLAOMP算法。該算法不需要知道信號的稀疏度，也不需要確定每次篩選的原子個數(shù)，只需設定初始的步長，通過回溯策略選出能量最大的若干原子，然后將這些原子加入LAR算法中判斷其對最終性能的影響效果，通過判斷選擇殘差性能滿足閾值條件的若干原子加入支撐集，然后進行后續(xù)迭代，進而判斷是否更新迭代步長。經(jīng)過一維點目標仿真和二維圖像仿真對比，發(fā)現(xiàn)該算法的重構質(zhì)量明顯優(yōu)于同類算法。但是，在運行時間上SABLAOMP算法并沒有做到最好。比如在一維信號重構實驗中，SABLAOMP算法的運行時間約為0.17 s，OMP算法的運行時間只有大概0.06 s，ALAOMP算法的重構時間約為0.15 s，但是相比于LAOMP算法約為0.19 s的運行時間還是有所改進的。所以說，相比于LAOMP算法而言，本文提出的SABLAOMP算法在降低了運算速度的同時還提高了重構精度。但這是在運行多次求取平均值后獲得的，復雜度高，速度慢，因此，如何通過在提高重構精度的同時，保證重構速度基本不變，是需要研究的一個方向。