基于指數試探的稀疏度自適應匹配追蹤算法*

于金冬，芮國勝，田文飚，董道廣，于志軍

（1.解放軍91206部隊，山東 青島 266108；2.海軍航空大學信息與信號處理山東省重點實驗室，山東 煙臺 264001）

0 引言

壓縮感知（Compressed Sensing，CS）是一種新的信號壓縮和處理理論，它突破了奈奎斯特采樣定理的限制，同時完成了信號的采樣和壓縮，極大降低了信息存儲、處理和傳輸的成本[1-2]。因此，該理論一經提出，便被廣泛應用于遙感圖像處理、醫學圖像采樣等各個領域。

CS理論有3個核心問題：稀疏表示、壓縮測量和優化重構。其中，優化重構直接影響著CS理論的應用效果，是最為關鍵的部分。貪婪迭代算法由于重建速度快且方法簡便，應用十分廣泛。它的基本思想是通過迭代，基于某種貪婪準則一次找出一個或多個待重構信號的構成元素，擴充支撐域以逼近信號的真實支撐。常用的貪婪算法有：匹配追蹤（Matching Pursuit，MP）[3]、正交匹配追蹤（Orthogonal Matching Pursuit，OMP）[4]、正則化正交匹配追蹤（Regularized Orthogonal Matching Pursuit，ROMP）[5]、分段正交匹配追蹤（Stagewise Orthogonal Matching Pursuit，StOMP）[6]、子空間追蹤（Subspace Pursuit，SP）[7]等。這幾種算法的抗噪聲能力有限，為解決這一問題，Deanna Needell和Joel A TROPP提出了壓縮采樣匹配追蹤（Compressive Sampling Matching Pursuit，CoSaMP）[8]，該算法引入了篩選回退的思想，提高了重構速度和魯棒性。但是，上述算法都需要以稀疏度為先驗信息，而實際問題中，信號的稀疏度往往是未知的，因此，出現了稀疏度自適應匹配追蹤（Sparsity Adaptive Matching Pursuit，SAMP）[9]，它以固定步長逐步擴充支撐集，自適應地完成信號重建，但是步長的選擇無法兼顧重構的精度和速度。近幾年，學者們對稀疏度自適應重構算法進行了一些研究。楊成等[10]基于匹配測試獲取稀疏度估計值，再通過子空間追蹤重構信號，提出了SASP算法。Huang H等[11]引入弱匹配方法分別擴充和剔除原子，自適應獲取稀疏度，提出了BAOMP算法。田文飚等[12]提出的BSAMP算法，基于分治思想預估稀疏度，然后通過自適應分組快速篩選出有效支撐集，進行信號重構。呂偉杰等[13]采用分段思想，先對半減小預估稀疏度，再逐一增加逼近，最后利用子空間追蹤重構，提出了MASP算法。

1 CS理論框架

其中，Φ是M×N維觀測矩陣，y是M×1維觀測信號。將式（1）帶入式（2）得：

信號的重構是利用M維觀測信號y無失真恢復出N維原始信號x的過程。由于x是K稀疏的，因此，可轉化成最小l0范數問題來求解，即：

由于觀測維數M遠小于信號維數N，因此，式（4）所描述的最小l0范數優化問題是一個NP-hard難題，數值計算復雜度高，而且極不穩定。文獻[14]指出可以將該問題轉化為求解一個更簡單的l1范數優化問題來解決，即：

若要完成精確重構，觀測矩陣Φ必須滿足有限等距約束特性[15]（Restricted Isometry Principle，RIP）：

2 EtSAMP算法

2.1 指數試探思路

首先給出稀疏度欠量估計和過量估計的判據，如定理1和定理2所示。

證明：由文獻[10]中給出的相關結論可知，若估計稀疏度 k≥K，則，其中，ΦT表示以T為索引的Φ中各列構成的子矩陣，為 ΦT的共軛轉置。由于 K＜2K，根據δK的單調性可得，RIP常數δK≤δ2K，因此，，證畢。

由于引理1是充分不必要的，因此，在實際問題中，通常利用其逆否命題來判定估計稀疏度是否小于真實值，如定理1所示。

文獻[12]給出了稀疏度過量估計的判據及證明，如定理2所示。

本文引入遞減型指數函數進行試探，令預估稀疏度隨著試探次數自適應發生變化，從而精確快速地逼近真實稀疏度。指數函數的基本形式如式（8）所示：

試探過程示意圖如圖1所示。

初始試探階段：首先進行第一次試探，得到相應支撐集，若滿足，說明稀疏度過量估計，即k＞K，轉入下一次試探，使預估稀疏度不斷減小，直至滿足，說明稀疏度欠量估計，即k＜K，轉入回溯試探階段。

圖1 指數試探過程示意圖

回溯試探階段：當k＜K時，令k=k+1，逐一增加預估稀疏度，直至再次滿足，如此，便可得到有效估計的真實稀疏度。

該方法將試探過程分為兩個階段：初始試探階段和回溯試探階段。在初始試探階段利用遞減指數函數驟降的特性，進行粗略搜索，快速靠攏真實稀疏度；在回溯試探階段以小步長逐步試探逼近，進行精細搜索，最終獲得準確的稀疏度估計值。通過指數試探，不僅避免了SAMP等算法對步長選擇的依賴，而且提升了試探精度，節省了運算時間。

2.2 算法步驟

算法的流程圖如圖2所示。

圖2 算法流程圖

詳細步驟如下。

輸入：觀測矩陣Φ，觀測向量y。

Step 1 指數試探稀疏度

4）i=i+1，逐一增加稀疏度估計值的大小，即ki=ki+1，直至滿足，令k=ki，完成對稀疏度的準確估計。

Step 2 篩選回退重構

Step 3 弱匹配剪枝

Step 4 迭代停止條件

2.3 算法可行性說明

Step1 將稀疏度試探分為兩個階段，先粗略搜索后精細搜索，在2個判據的共同約束下，逐步逼近真實稀疏度，為后面的重構提供了可靠的先驗信息，既保證了試探速度，又兼顧了試探精度，避免了SAMP算法對步長信息的依賴以及RAMP算法[16]中閾值對重構精度的影響。

Step2 首先根據相關性批量選擇2k個原子構成預選集，然后回退篩選出候選集，重構得到估計信號，本質上是一種回溯類方法，同時提高了重構速度和抗噪聲性能。

Step3 采用弱匹配原則選取重構向量大于一定閾值的原子，并將其索引加入支撐集，剪枝得到信號的逼近值。已有實驗表明[11]，弱匹配參數ξ在[0.4，0.8]之間取值時，可以兼顧算法性能和運算速度。

Step4 通過對比前后兩次殘差值的大小，判斷是否停止迭代。這是因為每進行一次迭代，算法都將選擇相關性最大的一批原子構成支撐集，因此，殘差值是不斷減小的，而一旦滿足，說明此時支撐集中已經引入了錯誤的原子，因此，應當退出迭代，保留上一次的迭代結果，輸出重構信號。

3 實驗結果及分析

通過分析可以看出，EtSAMP算法能夠通過調整參數來實現任意稀疏比條件下信號的準確試探及自適應重構，由于工程應用背景各不相同，這里不一一窮舉。文獻[17]中指出，用壓縮感知理論處理稀疏比較低的遙感圖像，更有利于保護圖像邊緣，保留圖像細節，抑制噪聲干擾。

選取隨機生成的一維稀疏信號作為測試信號（N=512），生成M×N維高斯隨機矩陣作為觀測矩陣，觀測數（c取 2，4），弱匹配參數ξ取0.4。為降低隨機因素的影響，所有數據都是經過1 000次蒙特卡洛仿真后求得的平均值。

3.1 相關參數的確定

由稀疏度欠量和過量估計判據可知，RIP常數δ2K關乎判別尺度的大小，進而影響試探的精度；由指數函數的性質可知，參數b能夠改變其變化趨勢，從而影響試探的速度。因此，確定二者的最優取值十分重要。

首先討論δ2K對試探結果的影響，固定參數b，令真實稀疏度K=50，進行 20次實驗，比較δ2K取不同值時稀疏度的試探結果，如圖3所示，可以看出，當δ2K=0.2時，試探結果約為53，與真實稀疏度最為接近，因此，為保證試探的準確性，這里取 δ2K=0.2。

圖3 δ2K與稀疏度試探結果

下面固定δ2K=0.2，研究參數b與試探次數的關系，結果如圖4所示。

圖4 b與試探次數的關系

圖4（a）中，令真實稀疏度K=50，觀察試探次數最小時b的取值。結果表明，當b=-1.2時，試探次數最少，只需3次。此外，試探次數隨著b的增加呈現非線性變化，二者沒有明顯的線性關系，這是由指數試探先粗略搜索后精細搜索的性質決定的。圖4（b）是圖4（a）方法的推廣，令稀疏度由1變化至128（稀疏比為0.25），統計當試探次數最小時，b取值的出現次數直方圖和擬合概率曲線。結果表明，當b在[-2.0，-1.1]之間取值時，試探次數易達到最小，特別是當b=-1.5時，出現的概率密度最高。因此，為保證試探的效率，這里取b=-1.5。

3.2 稀疏度試探結果

為了進一步驗證指數試探方法的可行性，令稀疏比K/N從0.1至0.25變化，比較估計稀疏度k和真實稀疏度K的值，結果如圖5所示。

圖5 估計稀疏度與真實稀疏度對比

可以看出，估計稀疏度與真實稀疏度基本重合，說明通過指數試探得到的結果與真實稀疏度十分逼近，該方法是可行的。此外，實驗結果表明，估計稀疏度略微高于真實稀疏度，保證了即使稀疏度估計出現偏差，也能夠包含重構所需的全部信息，進而重構出原始信號，提高了重構過程的穩定性。

3.3 重構性能比較

首先比較幾種稀疏度自適應重構算法的運行時間。令稀疏比K/N從0.05至0.25變化，SASP算法中，α=0.7，δK=0.3，SAMP算法中步長取2，opt=0.001[10]。圖6展示了在不同稀疏比條件下，4種算法的重構時間。

圖6 不同算法重構時間比較

由圖6可以看出，在稀疏比小于0.25時，各類算法的重構時間均隨稀疏比的增大而增加，EtSAMP算法的重構時間最短，低于相同弱匹配條件下的BSAMP和SASP算法，遠小于SAMP算法，優勢十分明顯。這是由于SAMP算法依據步長逐步擴充支撐集，在選擇原子的候選集和最終支撐集時需要較大的計算量，SASP和BSAMP算法在試探稀疏度時步驟較多，EtSAMP算法利用指數函數提高搜索速度，試探次數最少，而且在重構過程中批量選擇2k數目的原子與重構信號原子的支撐集做并集，節省了時間。

下面將EtSAMP算法與幾種經典的貪婪算法進行對比，其中CoSaMP、OMP、ROMP算法中代入指數試探出的稀疏度k。實驗結果如圖7和圖8所示。通常認為，如果重構信噪比SNR大于40 dB，則重構成功，即式（9）：

圖7 重構成功率隨稀疏比變化曲線

由圖7可得，當稀疏比小于0.25時，EtSAMP算法的重構成功率基本穩定，不低于97%，而其他5種算法的重構成功率均有不同程度下降，當稀疏比提高到[0.25，0.4]之間時，EtSAMP算法的優勢更加突出，重構成功率遠高于其他算法，當稀疏比大于0.4時，6種算法都無法成功重構信號。

圖8 重構成功率隨壓縮比變化曲線

從圖8可以看出，當壓縮比小于0.075時，幾乎所有算法都無法實現重構，隨著壓縮比逐步增大，重構成功率快速提升，特別是當壓縮比到達0.15時，EtSAMP和BSAMP算法就已經能夠高概率完成重構，遠遠優于其他算法。

圖9直觀給出了當稀疏度取不同值時，殘差隨迭代次數的變化情況。

圖9 殘差隨迭代次數的變化情況

由圖9可見，當迭代停止條件尚未滿足時，殘差會隨著迭代次數的增加而減小，直至，即最新一次迭代的殘差大于上一次迭代的殘差，此時無論稀疏度取何值，信號的重構信噪比均大于40 dB，認定重構成功。因此，以作為停止迭代條件是合理的，且說明EtSAMP算法具備一定的收斂性。

4 結論

利用指數函數特性，同時結合篩選回退思想和弱匹配原則，提出了一種新的稀疏度自適應重構算法。算法利用指數函數特性將稀疏度試探過程分為兩個階段，在初始試探階段粗略搜索，在回溯試探階段精細搜索，快速準確地逼近真實值，然后通過篩選回退擴充信號的支撐集，再采取弱匹配剪枝的方法精確重構出原始信號。算法較好解決了貪婪算法需要預知信號稀疏度，以及現有稀疏度試探方法效率較低的問題。實驗表明，新算法的試探結果更加準確穩定，重構成功率提升，特別是當稀疏比小于0.25時，重構時間少于其他算法，適合處理低稀疏比的遙感圖像問題。