壓縮感知增強型自適應(yīng)分段正交匹配追蹤算法

何雪云 湯可祥 梁 彥

(南京郵電大學(xué)通信與信息工程學(xué)院，江蘇南京 210003)

1 引言

當今時代，信息技術(shù)迅速發(fā)展，需要處理的信號帶寬越來越寬，如果對模擬信號用奈奎斯特采樣率進行采樣，將需要更大的存儲和傳輸代價，同時對硬件采樣系統(tǒng)也有更高的要求。于是，為了解決上述難題，有學(xué)者便提出了新的理論—壓縮感知理論(Compressed Sensing, CS)[1-2]。CS理論是一種新的信號獲取和處理方式，它在數(shù)據(jù)采集的同時完成數(shù)據(jù)的壓縮，從而節(jié)約了軟硬件資源和數(shù)據(jù)處理的時間?；趬嚎s感知的信號采樣速率遠低于傳統(tǒng)奈奎斯特采樣方法。這些優(yōu)點使得其在很多領(lǐng)域有著廣闊的應(yīng)用前景,如在雷達[3-5]、成像[6]、信號處理[7]、信道估計[8-9]等。CS理論利用信號的稀疏特性或者將其變換到稀疏域，通過求解優(yōu)化問題實現(xiàn)信號的精確重建。

重建算法是CS理論的關(guān)鍵問題，它應(yīng)該在已知測量矩陣和測量向量的前提下，高效并且精確的實現(xiàn)對原始信號的重建。目前主要的重建算法有：組合優(yōu)化類重建算法、凸優(yōu)化類算法和統(tǒng)計分析類算法以及貪婪迭代類算法。組合優(yōu)化類算法,如傅里葉采樣算法[10]的重建效果比較好，但是在實際條件下由于系統(tǒng)要求比較嚴格，存在各種約束，因此很難廣泛運用；凸優(yōu)化類算法，如基追蹤算法(Basis Pursuit, BP)[11]等算法，其需要的采樣值較少，重建精度較好，但是算法復(fù)雜度高，在壓縮感知系統(tǒng)的實際應(yīng)用中很難得以廣泛運用；統(tǒng)計分析類算法，如貝葉斯壓縮感知[12]重建算法、從稀疏到結(jié)構(gòu)化稀疏: 貝葉斯方法[13]、結(jié)合自適應(yīng)字典學(xué)習(xí)的稀疏貝葉斯重建算法[14]等, 其在優(yōu)化上達到局部最優(yōu)，誤差較小，重建效果較好，具有一定的應(yīng)用前景；貪婪迭代類算法運算量小，運行效率和采樣效率較高，且具有一定的重建精度，因此應(yīng)用最為廣泛。

作為應(yīng)用最為廣泛的貪婪迭代算法，現(xiàn)在已經(jīng)有一些傳統(tǒng)的算法，如正交匹配追蹤算法(Orthogonal Matching Pursuit, OMP)[15]。除此之外,還有一些由OMP算法加以優(yōu)化所形成的算法[16-17]。上述算法的前提均要求已知信號的稀疏度，這一要求在實際應(yīng)用中很難實現(xiàn)。能否在信號稀疏度未知的情況下，通過基于貪婪迭代的算法自適應(yīng)的估計信號的稀疏度，使之更加精確的重建信號？針對該問題，有學(xué)者研究并且提出了具有一定程度自適應(yīng)能力的分段正交匹配追蹤算法(Stagewise Orthogonal Matching Pursuit, StOMP)[18]，它能夠在未知信號稀疏度的前提下重建信號，因為其預(yù)先只需要把迭代次數(shù)設(shè)定為某一固定值即可，在文獻[18]中,作者建議迭代次數(shù)取10，但其重建性能不夠理想。本文在StOMP重建算法的基礎(chǔ)上提出了一種增強型自適應(yīng)分段正交匹配追蹤算法(Enhanced Adaptive Stagewise Orthogonal Matching Pursuit Algorithm，EAStOMP)。該算法在已有StOMP算法的基礎(chǔ)上，引入回溯思想，在原有的閾值參數(shù)的基礎(chǔ)上通過引入一個新的標識參數(shù)，達到有效的二次支撐集篩選，從而可以更好的進行稀疏度估計，更加準確地重建信號。仿真結(jié)果表明，本文提出的重建算法具有很好的重建性能，重建精確度高，運算量適中，具有很好的實際應(yīng)用場景。

2 壓縮感知理論與傳統(tǒng)重建算法

假設(shè)x∈RN是長度為N的原始信號向量，非零值元素個數(shù)為K，即稀疏度為K，y∈RM是長度為M的測量信號向量，Φ∈RM×N是M×N維的測量矩陣(或稱為觀測矩陣，其滿足M?N),x與Φ相乘得到y(tǒng)，即

y=Φx

(1)

當滿足約束等距性質(zhì)[19]時，重建端通過y與Φ則能以很大概率完成信號重建，前提是式(2)成立：

M≥cKlog(N/K)?N

(2)

其中c是一個很小的常數(shù)[20]。

對于信號的重建，實際上就是由式(1)求解最小l0范數(shù)優(yōu)化問題，即

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

(3)

這是一個NP難問題，但是可以在一定條件下將其轉(zhuǎn)化為更簡單的最小l1范數(shù)優(yōu)化問題來近似求解，即

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

(4)

當有噪聲時，式(1)就變?yōu)椋?/p>

y=Φx+n

(5)

其中n表示噪聲向量。

類似的，此時的信號重建，實際上就是由式(5)求解最小l0范數(shù)優(yōu)化問題，即

min‖x‖0, s.t.y=Φx+n

(6)

式(6)同樣可以在一定條件下轉(zhuǎn)化為更簡單的最小l1范數(shù)優(yōu)化問題來近似求解，即

min‖x‖1, s.t.y=Φx+n

(7)

對于最小l1范數(shù)優(yōu)化問題可以通過線性規(guī)劃方法來求解，如基追蹤(BP)算法，但是其計算復(fù)雜度太高。所以，便出現(xiàn)了一類計算復(fù)雜度較低并且易于實現(xiàn)的貪婪迭代類重建算法，如比較經(jīng)典的OMP算法以及一些改進算法[16-17]。

傳統(tǒng)的OMP，它在每次迭代時首先通過計算此時殘差向量與觀測矩陣的內(nèi)積，然后選取相關(guān)性最大的一個原子，放入索引集，然后更新殘差和進行迭代次數(shù)的判斷。不斷重復(fù)上述過程，當?shù)螖?shù)增加到信號的稀疏度時，則迭代終止，并輸出重建信號估計值。由于每次迭代只選取一個原子，所以當稀疏度很大時需要的步數(shù)會大幅增加，重建效率有所降低。而分段正交匹配追蹤StOMP算法則是在每次迭代時根據(jù)閾值參數(shù)來選取一個原子集合，然后利用最小二乘法求得重建信號，同時更新支撐集和殘差，在一定程度上改善了重建效率。

StOMP算法的主要步驟[18]如下：

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

1)初始化殘差r0=y，初始支撐集F0=?，迭代次數(shù)k=1，終止最大迭代次數(shù)P；

3)合并形成新的支撐集：

Fk=Fk-1∪Jk;

對于上述的一些傳統(tǒng)重建算法，如OMP、ROMP算法，它們都是以信號的稀疏度作為先驗條件的，然而這在實際當中是很難實現(xiàn)的，所以需要一種具有稀疏度認知能力的自適應(yīng)重建算法。雖然StOMP算法可以通過預(yù)先設(shè)定的迭代次數(shù)，實現(xiàn)在未知信號稀疏度的情況下的信號重建，但重建性能并不是很好。本文在StOMP算法的基礎(chǔ)上進行了相應(yīng)的改進，提出了增強型自適應(yīng)分段正交匹配追蹤算法，簡記為EAStOMP。

3 EAStOMP算法

3.1 算法思想

本文在StOMP算法的基礎(chǔ)上，引入回溯思想[21-22]，在原有的閾值參數(shù)的基礎(chǔ)上通過引入一個新的標識參數(shù)I，通過標識參數(shù)來進行每步的可變步長的操作以及殘差的更新，以更好的逼近估計信號稀疏度，更加有效的進行二次支撐集篩選，達到更好的信號重建的目的。該算法的停止迭代條件也有所變化，不再是最大迭代次數(shù)而是一個閾值參數(shù)ε。該閾值參數(shù)是一個很小的值，可根據(jù)實際情況來進行設(shè)置，也可以是噪聲功率。這樣通過更加有效的選取原子，以及更加合理的稀疏度估計過程，逐漸逼近信號稀疏度，最后可以更加高效的完成信號重建。

3.2 算法步驟

EAStOMP的主要算法步驟如下：

輸入：測量矩陣Φ，測量信號向量y，初始迭代次數(shù)s。

1)初始化殘差r0=y,初始支撐集F0=?，起始步長L=s，迭代次數(shù)k=1，階段標識I=0;

2)初選原子形成候選集：

Jk={j:|gk(j)|>tσk};

3)階段標識值判斷與更新：

如果size(Ck)>μ*M，則I=1，其中size(Ck)表示候選集中的元素個數(shù)；

4)支撐集形成：

8)k=k+1，轉(zhuǎn)步驟2)。

4 仿真結(jié)果及分析

本節(jié)將通過Matlab仿真，在測量值無噪聲和有噪聲兩種情況下，對比本文提出的EAStOMP算法和其他現(xiàn)有相關(guān)算法的重建性能。本文仿真實驗中，仿真時所采用的觀測矩陣為高斯隨機矩陣，稀疏信號為一維高斯隨機信號，稀疏信號長度記為N，稀疏度記為K。對于K稀疏的信號而言，向量中有K個服從高斯分布的非零元素，其余元素為0值，不同信號非零元素的位置是隨機變化的。噪聲為加性高斯白噪聲，測量值個數(shù)也即測量向量長度記為M。由于比較的是稀疏度未知情況下的重建性能，為了比較的公平性，仿真中所用OMP算法均為未知稀疏度，迭代停止條件為‖r‖2<ε，ε是一個很小的值。仿真中OMP算法和EAStOMP算法的ε均取10-6。

當沒有噪聲的時候，用信號的準確重建概率作為重建性能指標。本節(jié)仿真中，準確重建定義為：重建信號與原始信號之差的2-范數(shù)小于一個極少值(仿真中取10-6)，即滿足式(8)：

(8)

當有噪聲的時候采用歸一化均方誤差(Mean Square Error, MSE)來衡量信號的重建性能。歸一化MSE定義為:

(9)

4.1 無噪聲條件下準確重建概率

該仿真是在無噪聲條件下，即式(4)所示模型。稀疏信號長度N取256時，M分別取128、64時，得到的不同算法的準確重建概率與稀疏度的關(guān)系。

圖1 不同算法的準確重建概率與稀疏度的關(guān)系(N=256, M=128) Fig.1 The exact reconstruction probability to the sparisty of different algorithms(N=256, M=128)

圖2 不同算法的準確重建概率與稀疏度的關(guān)系(N=256, M=64)Fig.2 The exact reconstruction probability to the sparisty of different algorithms(N=256, M=64)

從圖1、圖2可以看出，本文提出的EAStOMP算法在未知信號稀疏度的條件下，準確重建概率性能明顯優(yōu)于OMP和StOMP算法，如在M=128，K=55時，StOMP算法已經(jīng)幾乎無法重建信號，僅有1.8%的準確重建概率，OMP算法也僅有61.2%的準確重建概率，但是EAStOMP算法仍然有高達96.8%的準確重建概率。

4.2 有噪聲條件下MSE的比較

該仿真是在測量值存在加性高斯白噪聲條件下進行的，即采用式(7)所示模型。

圖3 不同算法信號重建性能MSE與信噪比SNR的關(guān)系(N=256,M=128,K=48)Fig.3 The reconstruction performance MSE to SNR of different algorithms(N=256,M=128,K=48)

從圖3可以看出，在加性高斯白噪聲條件下，當N=256，M=128，K=48時，EAStOMP算法重建信號的MSE要優(yōu)于OMP和StOMP算法。而且隨著信噪比(Signal to Noise Ratio, SNR)的增大，性能優(yōu)勢越來越明顯，當SNR=30 dB時，EAStOMP算法重建信號MSE優(yōu)于StOMP算法10 dB左右。

圖4 不同算法信號重建MSE與稀疏度的關(guān)系(N=256, M=64, SNR=30 dB)Fig.4 The reconstruction performance MSE to SNR of different algorithms(N=256, M=64, SNR=30 dB)

從圖4可以看出，在加性高斯白噪聲條件下，N=256，M=64，SNR=30 dB時，本文的EAStOMP算法信號重建MSE優(yōu)于OMP算法和StOMP算法，且相對于StOMP算法MSE性能改善了很多，最大可達12 dB左右。

圖5、圖6是在N=256, SNR=30 dB時，K分別為20、40,得到的不同算法信號重建MSE與測量值個數(shù)的關(guān)系。從仿真結(jié)果可見，EAStOMP算法在不同測量值個數(shù)條件下的信號重建MSE都要優(yōu)于圖中OMP和StOMP算法，最高優(yōu)于StOMP算法20 dB左右。且隨著稀疏度K的增加，該算法相對于其他兩種算法的性能優(yōu)勢越來越明顯，尤其相對于StOMP算法表現(xiàn)的更突出。

4.3 無噪和有噪條件下的算法復(fù)雜度

4.1、4.2節(jié)的仿真結(jié)果都很好的說明了本文提出的EAStOMP算法無論在無噪條件下還是在有噪條件下，重建信號的質(zhì)量性能都要優(yōu)于其他算法，尤其是StOMP算法。而本節(jié)則對算法復(fù)雜度來進行比較，通過算法重建時間這一指標來衡量算法復(fù)雜度。

圖5 不同算法信號重建MSE與測量值個數(shù)的關(guān)系(N=256, K=20,SNR=30 dB)Fig.5 The reconstruction performance MSE to the number of measurements of different algorithms(N=256, K=20,SNR=30 dB)

圖6 不同算法信號重建MSE與測量值個數(shù)的關(guān)系(N=256, K=40,SNR=30 dB)Fig.6 The reconstruction performance MSE to the number of measurements of different algorithms(N=256, K=40,SNR=30 dB)

在無噪聲時，仿真中N=256,M=64,K依次取8、12、16、20。

從表1可以看出，EAStOMP算法重建信號的運行時間比OMP算法要小，且隨著稀疏度增大優(yōu)勢越明顯。雖然運行時間略高于StOMP算法，但是它的重建性能是優(yōu)于StOMP算法，所以綜合考慮EAStOMP算法重建性能還是有優(yōu)勢。

表1 無噪條件下不同算法重建信號運行時間(ms)

在有加性高斯白噪聲時，仿真中N=256，M=64，SNR=30 dB，K依次取8、12、16、20。

表2仿真結(jié)果表明，在有噪聲的條件下，EAStOMP算法重建信號的運行時間明顯低于OMP算法。雖然略高于StOMP算法，但是信號重建MSE的性能優(yōu)于StOMP算法2～12 dB左右。

表2 有噪條件下不同算法重建信號運行時間(ms)

表1、表2的仿真結(jié)果表明，在無噪和有噪條件下，EAStOMP算法在未知信號稀疏度的條件下，自適應(yīng)的重建信號的運行時間均優(yōu)于OMP算法，OMP算法運行時間長主要是因為它無法很好的自適應(yīng)估計信號的稀疏度，迭代次數(shù)過多； EAStOMP算法雖然運行時間略高于StOMP算法，為StOMP算法運行時間的2倍左右，但是信號重建質(zhì)量性能優(yōu)于StOMP算法很多。

綜合以上仿真結(jié)果，EAStOMP算法的重建性能優(yōu)于OMP算法，但會犧牲少量算法復(fù)雜度，即EAStOMP算法的重建時間略長于StOMP算法。當我們優(yōu)先考慮重建質(zhì)量時， EAStOMP算法將明顯優(yōu)于StOMP算法。

5 結(jié)論

本文在深入研究了StOMP算法以及其他傳統(tǒng)壓縮感知重建算法的基礎(chǔ)上，通過在原有的StOMP算法中引入標識參數(shù)進行變步長和回溯思想，提出了一種增強型自適應(yīng)分段正交匹配追蹤算法EAStOMP。該算法在未知信號稀疏度的條件下，通過標識參數(shù)進行變步長以及回溯思想進行原子的篩選和稀疏度的估計逼近，從而有效的完成信號重建。仿真結(jié)果表明，在未知信號稀疏度的條件下，相比于StOMP算法和OMP算法，可以更加有效的自適應(yīng)重建信號，且重建信號的質(zhì)量很高，重建信號時間較低。在不同參數(shù)條件下，與StOMP算法相比，EAStOMP算法無噪時準確重建概率平均提高30%～40%左右，有噪時MSE提高5～10 dB左右。下一步， 還需研究如何將本文提出的EAStOMP算法應(yīng)用在實際應(yīng)用中，以評估其實用性能的提升水平。