基于指數(shù)試探的稀疏度自適應(yīng)匹配追蹤算法*

于金冬，芮國(guó)勝，田文飚，董道廣，于志軍

（1.解放軍91206部隊(duì)，山東 青島 266108；2.海軍航空大學(xué)信息與信號(hào)處理山東省重點(diǎn)實(shí)驗(yàn)室，山東 煙臺(tái) 264001）

0 引言

壓縮感知（Compressed Sensing，CS）是一種新的信號(hào)壓縮和處理理論，它突破了奈奎斯特采樣定理的限制，同時(shí)完成了信號(hào)的采樣和壓縮，極大降低了信息存儲(chǔ)、處理和傳輸?shù)某杀綶1-2]。因此，該理論一經(jīng)提出，便被廣泛應(yīng)用于遙感圖像處理、醫(yī)學(xué)圖像采樣等各個(gè)領(lǐng)域。

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

1 CS理論框架

其中，Φ是M×N維觀測(cè)矩陣，y是M×1維觀測(cè)信號(hào)。將式（1）帶入式（2）得：

信號(hào)的重構(gòu)是利用M維觀測(cè)信號(hào)y無(wú)失真恢復(fù)出N維原始信號(hào)x的過(guò)程。由于x是K稀疏的，因此，可轉(zhuǎn)化成最小l0范數(shù)問(wèn)題來(lái)求解，即：

由于觀測(cè)維數(shù)M遠(yuǎn)小于信號(hào)維數(shù)N，因此，式（4）所描述的最小l0范數(shù)優(yōu)化問(wèn)題是一個(gè)NP-hard難題，數(shù)值計(jì)算復(fù)雜度高，而且極不穩(wěn)定。文獻(xiàn)[14]指出可以將該問(wèn)題轉(zhuǎn)化為求解一個(gè)更簡(jiǎn)單的l1范數(shù)優(yōu)化問(wèn)題來(lái)解決，即：

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

2 EtSAMP算法

2.1 指數(shù)試探思路

首先給出稀疏度欠量估計(jì)和過(guò)量估計(jì)的判據(jù)，如定理1和定理2所示。

證明：由文獻(xiàn)[10]中給出的相關(guān)結(jié)論可知，若估計(jì)稀疏度 k≥K，則，其中，ΦT表示以T為索引的Φ中各列構(gòu)成的子矩陣，為 ΦT的共軛轉(zhuǎn)置。由于 K＜2K，根據(jù)δK的單調(diào)性可得，RIP常數(shù)δK≤δ2K，因此，，證畢。

由于引理1是充分不必要的，因此，在實(shí)際問(wèn)題中，通常利用其逆否命題來(lái)判定估計(jì)稀疏度是否小于真實(shí)值，如定理1所示。

文獻(xiàn)[12]給出了稀疏度過(guò)量估計(jì)的判據(jù)及證明，如定理2所示。

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

試探過(guò)程示意圖如圖1所示。

初始試探階段：首先進(jìn)行第一次試探，得到相應(yīng)支撐集，若滿足，說(shuō)明稀疏度過(guò)量估計(jì)，即k＞K，轉(zhuǎn)入下一次試探，使預(yù)估稀疏度不斷減小，直至滿足，說(shuō)明稀疏度欠量估計(jì)，即k＜K，轉(zhuǎn)入回溯試探階段。

圖1 指數(shù)試探過(guò)程示意圖

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

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

2.2 算法步驟

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

圖2 算法流程圖

詳細(xì)步驟如下。

輸入：觀測(cè)矩陣Φ，觀測(cè)向量y。

Step 1 指數(shù)試探稀疏度

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

Step 2 篩選回退重構(gòu)

Step 3 弱匹配剪枝

Step 4 迭代停止條件

2.3 算法可行性說(shuō)明

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

Step2 首先根據(jù)相關(guān)性批量選擇2k個(gè)原子構(gòu)成預(yù)選集，然后回退篩選出候選集，重構(gòu)得到估計(jì)信號(hào)，本質(zhì)上是一種回溯類方法，同時(shí)提高了重構(gòu)速度和抗噪聲性能。

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

Step4 通過(guò)對(duì)比前后兩次殘差值的大小，判斷是否停止迭代。這是因?yàn)槊窟M(jìn)行一次迭代，算法都將選擇相關(guān)性最大的一批原子構(gòu)成支撐集，因此，殘差值是不斷減小的，而一旦滿足，說(shuō)明此時(shí)支撐集中已經(jīng)引入了錯(cuò)誤的原子，因此，應(yīng)當(dāng)退出迭代，保留上一次的迭代結(jié)果，輸出重構(gòu)信號(hào)。

3 實(shí)驗(yàn)結(jié)果及分析

通過(guò)分析可以看出，EtSAMP算法能夠通過(guò)調(diào)整參數(shù)來(lái)實(shí)現(xiàn)任意稀疏比條件下信號(hào)的準(zhǔn)確試探及自適應(yīng)重構(gòu)，由于工程應(yīng)用背景各不相同，這里不一一窮舉。文獻(xiàn)[17]中指出，用壓縮感知理論處理稀疏比較低的遙感圖像，更有利于保護(hù)圖像邊緣，保留圖像細(xì)節(jié)，抑制噪聲干擾。

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

3.1 相關(guān)參數(shù)的確定

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

首先討論δ2K對(duì)試探結(jié)果的影響，固定參數(shù)b，令真實(shí)稀疏度K=50，進(jìn)行 20次實(shí)驗(yàn)，比較δ2K取不同值時(shí)稀疏度的試探結(jié)果，如圖3所示，可以看出，當(dāng)δ2K=0.2時(shí)，試探結(jié)果約為53，與真實(shí)稀疏度最為接近，因此，為保證試探的準(zhǔn)確性，這里取 δ2K=0.2。

圖3 δ2K與稀疏度試探結(jié)果

下面固定δ2K=0.2，研究參數(shù)b與試探次數(shù)的關(guān)系，結(jié)果如圖4所示。

圖4 b與試探次數(shù)的關(guān)系

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

3.2 稀疏度試探結(jié)果

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

圖5 估計(jì)稀疏度與真實(shí)稀疏度對(duì)比

可以看出，估計(jì)稀疏度與真實(shí)稀疏度基本重合，說(shuō)明通過(guò)指數(shù)試探得到的結(jié)果與真實(shí)稀疏度十分逼近，該方法是可行的。此外，實(shí)驗(yàn)結(jié)果表明，估計(jì)稀疏度略微高于真實(shí)稀疏度，保證了即使稀疏度估計(jì)出現(xiàn)偏差，也能夠包含重構(gòu)所需的全部信息，進(jìn)而重構(gòu)出原始信號(hào)，提高了重構(gòu)過(guò)程的穩(wěn)定性。

3.3 重構(gòu)性能比較

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

圖6 不同算法重構(gòu)時(shí)間比較

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

下面將EtSAMP算法與幾種經(jīng)典的貪婪算法進(jìn)行對(duì)比，其中CoSaMP、OMP、ROMP算法中代入指數(shù)試探出的稀疏度k。實(shí)驗(yàn)結(jié)果如圖7和圖8所示。通常認(rèn)為，如果重構(gòu)信噪比SNR大于40 dB，則重構(gòu)成功，即式（9）：

圖7 重構(gòu)成功率隨稀疏比變化曲線

由圖7可得，當(dāng)稀疏比小于0.25時(shí)，EtSAMP算法的重構(gòu)成功率基本穩(wěn)定，不低于97%，而其他5種算法的重構(gòu)成功率均有不同程度下降，當(dāng)稀疏比提高到[0.25，0.4]之間時(shí)，EtSAMP算法的優(yōu)勢(shì)更加突出，重構(gòu)成功率遠(yuǎn)高于其他算法，當(dāng)稀疏比大于0.4時(shí)，6種算法都無(wú)法成功重構(gòu)信號(hào)。

圖8 重構(gòu)成功率隨壓縮比變化曲線

從圖8可以看出，當(dāng)壓縮比小于0.075時(shí)，幾乎所有算法都無(wú)法實(shí)現(xiàn)重構(gòu)，隨著壓縮比逐步增大，重構(gòu)成功率快速提升，特別是當(dāng)壓縮比到達(dá)0.15時(shí)，EtSAMP和BSAMP算法就已經(jīng)能夠高概率完成重構(gòu)，遠(yuǎn)遠(yuǎn)優(yōu)于其他算法。

圖9直觀給出了當(dāng)稀疏度取不同值時(shí)，殘差隨迭代次數(shù)的變化情況。

圖9 殘差隨迭代次數(shù)的變化情況

由圖9可見(jiàn)，當(dāng)?shù)Ｖ箺l件尚未滿足時(shí)，殘差會(huì)隨著迭代次數(shù)的增加而減小，直至，即最新一次迭代的殘差大于上一次迭代的殘差，此時(shí)無(wú)論稀疏度取何值，信號(hào)的重構(gòu)信噪比均大于40 dB，認(rèn)定重構(gòu)成功。因此，以作為停止迭代條件是合理的，且說(shuō)明EtSAMP算法具備一定的收斂性。

4 結(jié)論

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