何雪云 湯可祥 梁 彥

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

1 引言

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

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

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

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

假設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)算法，但是其計算復雜度太高。所以，便出現(xiàn)了一類計算復雜度較低并且易于實現(xiàn)的貪婪迭代類重建算法，如比較經(jīng)典的OMP算法以及一些改進算法[16-17]。

傳統(tǒng)的OMP，它在每次迭代時首先通過計算此時殘差向量與觀測矩陣的內(nèi)積，然后選取相關性最大的一個原子，放入索引集，然后更新殘差和進行迭代次數(shù)的判斷。不斷重復上述過程，當?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)的，所以需要一種具有稀疏度認知能力的自適應重建算法。雖然StOMP算法可以通過預先設定的迭代次數(shù)，實現(xiàn)在未知信號稀疏度的情況下的信號重建，但重建性能并不是很好。本文在StOMP算法的基礎上進行了相應的改進，提出了增強型自適應分段正交匹配追蹤算法，簡記為EAStOMP。

3 EAStOMP算法

3.1 算法思想

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

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)有相關算法的重建性能。本文仿真實驗中，仿真時所采用的觀測矩陣為高斯隨機矩陣，稀疏信號為一維高斯隨機信號，稀疏信號長度記為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時，得到的不同算法的準確重建概率與稀疏度的關系。

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

圖2 不同算法的準確重建概率與稀疏度的關系(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的關系(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與稀疏度的關系(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ù)的關系。從仿真結(jié)果可見，EAStOMP算法在不同測量值個數(shù)條件下的信號重建MSE都要優(yōu)于圖中OMP和StOMP算法，最高優(yōu)于StOMP算法20 dB左右。且隨著稀疏度K的增加，該算法相對于其他兩種算法的性能優(yōu)勢越來越明顯，尤其相對于StOMP算法表現(xiàn)的更突出。

4.3 無噪和有噪條件下的算法復雜度

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

圖5 不同算法信號重建MSE與測量值個數(shù)的關系(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ù)的關系(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ōu)于OMP算法，OMP算法運行時間長主要是因為它無法很好的自適應估計信號的稀疏度，迭代次數(shù)過多； EAStOMP算法雖然運行時間略高于StOMP算法，為StOMP算法運行時間的2倍左右，但是信號重建質(zhì)量性能優(yōu)于StOMP算法很多。

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

5 結(jié)論

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