稀疏度自適應的廣義正交匹配追蹤算法

張龍

（上海海事大學信息工程學院，上海201306）

1 壓縮感知理論簡介

壓縮感知理論[1-3]（Compressed Sensing，CS）最開始由Candes、Donoho和Tao等率先進行研究。只要目標信號相對于某個域是稀疏的或者是可壓縮，就可以用觀測矩陣將將高維信號投影到一個低維空間上。再求解一個優化問題就可以高概率重構出原信號。理論依據如下：

（1）設長度N的信號x在正交基ψ上是稀疏度為k;

（2）如果能找到一個與ψ不相關的觀測基φ;

（3）用觀測基Φ觀測信號得到長度為M的一維測量值M個觀測值Y，K小于M遠遠小于N;

（4）那么就可以利用最優化方法從觀測值Y中高概率恢復X。

圖1 壓縮感知理論框架

在上述的理論下，采樣速率不再取決于信號的帶寬，而在很大程度上取決于兩個基本準則：稀疏度和非相關性（也叫等距約束性RIP）。

壓縮感知理論主要包括三部分：

（1）信號的稀疏表示。稀疏性簡單點的解釋就是信號含有k個非零值，其他系數值為零或遠小于k個非零值。現實中的大多信號x往往并不是稀疏的，所以需要在某個對應的稀疏基上進行稀疏表示。一般的自然信號x本身并不是稀疏的，需要在某種稀疏基上進行稀疏表示。

x=Ψθ

Ψ為稀疏基矩陣，θ為稀疏系數（θ只有K個是非零值（K<

（2）設計測量矩陣Φ（也稱觀測矩陣），我們既要考慮到降低維數來使信號更加簡單便于應用于實際，又要考慮實際保證信號的損失最小，保證能夠從觀測值準確重構信號。目前研究表明只要觀測基矩陣與稀疏基矩陣的乘積即重構矩陣滿足RIP性質（有限等距性質）：

上述性質保證了原空間到稀疏空間的一一映射關系，保證了唯一性，只要觀測矩陣中抽取的M列向量構成的矩陣是非奇異的，我們就能從觀測信號中通過重構算法恢復原始信號。且若Ψ和Φ不相關，則其很大概率滿足RIP性質。CandeS和Tao的研究表明了測量矩陣如果是獨立同分布的高斯隨機矩陣，那么它將是良好的壓縮感知測量矩陣。因此我們用測量矩陣Φ（MxN且M<

y=Φx=ΦΨθ=Aθ。

（3）設計恢復信號的算法，利用測量所得的M個值來無失真地恢復原始信號，長度為N。當Φ滿足RIP性質，我們先求解上式中的θ，然后將稀疏度為k的信號x從M維的測量投影值y中正確地恢復出來。其中恢復信號的最直接辦法是通過l0范數（0-范數，也就是向量y?中非零元素的個數）下求解的最優化問題，從而得到稀疏系數θ的估計θ?。則原信號：

從壓縮感知理論誕生至今，國內外學者對設計信號的恢復算法即重構算法提出了多種快速有效的算法，主要包括基追蹤算法、貪婪算法、迭代閾值算法等[4,5]。由于貪婪算法相對較快，受到學者們廣泛關注。貪婪算法主要有OMP（正交匹配追蹤）算法[6]、ROMP（正則化正交匹配追蹤）[7,8]、CoSaMP[8]（壓縮采樣匹配追蹤），StOMP[8]（分段正交匹配追蹤）、SAMP[10]（稀疏度自適應匹配追蹤）、gOMP（廣義正交匹配追蹤）。前面的4種算法都要假設信號的稀疏度已知，這在實際應用中是不可能的。所以提出了RAMP，可以對稀疏度進行估計且具有較高的重構精度，但是當數據N增大時，算法運行時間過長，實際應用性降低。本文在在保證運算速度的基礎上，結合了稀疏度估計，提出了SAgOMP（稀疏度自適應的廣義正交匹配追蹤算法）。

2 稀疏度自適應的廣義正交匹配重構算法

本文提出的稀疏度自適用廣義正交匹配追蹤算法（SAgOMP）算法。在針對gOMP需要知道信號稀疏度的情況下，本算法先進行稀疏度估計對信號的稀疏度做一個預測。將獲得稀疏度代入gOMP算法當中。算法主要包括三個部分：稀疏度估計計算，確定迭代步長選取子原子，信號殘差的更新。

2.1 SAgOMP算法流程

為了便于對算法進行闡述，下面是對算法用到的符號的解釋，如表1和程序1所示。

表1 SAgOMP算法流程符號說明

程序1 SAgOMP算法流程符號說明

輸入：M×N的傳感矩陣A，N×1維的觀測向量y

輸出：信號稀疏表示系數估計θ?。

（1）初始化r0=y，Λ0=?,A0=?,t=1;

（3）如果norm( A ,u(L ) ,2)

（4）將S=K0/3求整，若K0小于3則默認S取1。

（6）令 Λt=Λt-1∪{J0}, At=At-1∪α（jfor all j ∈J0）；

（7）求 y=Atθt的最小二乘解：

（9）t=t+1，如果t≤K則返回步驟5，否則停止迭代進入第10步；

（10）重構所得θ?在Λt有非零項，其值分別為最后一次迭代所得θt。

第（1）～（3）步為稀疏度估計部分，得到初始的估計稀疏度。第（4）步設置每次選擇的原子個數，后面仿真實驗會說明。第（5）到（9）步是廣義正交匹配追蹤算法過程。第（10）步輸出。

2.2 稀疏度估計計算

在稀疏信號自適應迭代算法中，每次選擇的原子個數L直接影響到算法的重構精度和運算速度。在SAMP中通過不停的修正L的大小來提高重構精度，則導致其計算量也很大。既然得到了估計稀疏度，那我們為什么不直接選擇與重構速度快的算法相結合。在OMP中每次選取S次原子，來提高運算速度。所以本文借鑒[11]中的命題1:

命題1中符號“<>”表示計算內積；δK表示上述策略中使用到的估計參數；K0表示信號稀疏度的估計值K表示稀疏度的真實值。uK0表示與測量值y最相關的原子索引集合；

受命題1啟發，我可以直接得到信號的估計稀疏度。但是如果直接將稀疏度代入gOMP中，隨著稀疏度的增大，選擇固定的K0勢必會影響算法的迭代速度。為此本分使用了步驟（4）的方法。通過除法，稀釋稀疏度增大會選取步長產生的影響。

3 仿真結果與實驗分析

3.1 實驗設置

為了驗證gAOMP算法在不用提前知道信號稀疏度的條件下的重構概率，測量次數和算法平均運行時間等方面的性能。，在MATLAB 2015b仿真平臺上對經典的OMP算法，ROMP算法，CoSaMP算法，StOMP算法，SAMP算法，gOMP算法與本文提出的gAOMP算法進行對比實驗，硬件環境為PC：Intel Core i3-2370M CPU@2.4GHz,4G內存。仿真實驗中參數的設置如下：

測量矩陣 A：M×N（256×512）的高斯隨機矩陣作為仿真實驗的測量矩陣。

信號源：假設信號x是N×1維信號，

迭代終止條件：當殘差‖‖r2小于le-6算法停止迭代，或達到預設的迭代次數，算法重構失敗。

重構成功認定的標準：‖‖x-x?2

3.2 步長L的選取

為了在gOMP算法中選取合適的S，改良gOMP算法。本實驗對重構精度和k（S=K0/k，k是我們選擇的系數）對不同稀疏度進行了仿真。得到不同稀疏度下，k值對重構概率的影響。

圖2 不同稀疏度下，k值對重構概率的影響

由圖2可知，當取值k=3,4,5,6,7時重構概率基本一樣。這是因為當k越大，則步長越小。通過最小二乘法進行運算時，每次選取的系數匹配度更高，則結果更精確。現在為了確保精度并兼顧運算速度，每個取盡可能多的原子數進行迭代。本文選擇了k=3，因為在此基礎上提升k值，重構準確率的提升已經不明顯了，所以提高每次選擇的原子數，進一步提高運算速度。

3.3 重構成功概率分析

這一部分比較了 OMP，ROMP，StOMP，CoSaMP，SAMP，gOMP，SAgOMP算法的性能。SAMP中的步長取 5。 δK?(0 ,1)的取值影響稀疏度估計中對K0影響，過小則預測的稀疏度過低，過大則稀疏度過高。本文取極限0；在RIP中，取極限當δ=0時，RIP的不等式實際上表示的是觀測所得向量y的能量等于信號x的能量，在線性代數中所講的正交變換也具有這種性質，也稱為等距變換。當然這里的變換因為傳感矩陣A不可能是正交矩陣（不是方陣）所以得到的稀疏度肯定是小于實際的稀疏度。

圖3 不同恢復算法的不同稀疏度下的重構概率

由圖2可知，在重構精度上，重構所需的SAgOMP算法的重構精度比SAMP低比gOMP高，且gOMP需要知道信號的稀疏程度。相比其他算法在重構精度上毫不遜色。在SAMP中由于在選擇原子迭代時會做進一步修正，使得重構精度更高。我們也可以很容易得出另一個結論，如果一個算法的重構精度越高，則它在達到精確重構是所需的樣本越少，具體仿真筆者也做了，如上所言。在以后將CS運用到實際通信當中，就可以在滿足足夠的重構精度下，盡量減少樣本數據的選取。進一步提高重構速度，提高應用價值。

3.4 平均運算時間和稀疏度分析

圖3 不同稀疏度下，不同算法與所需重構時間

如圖3所示，隨著稀疏度K的增大，各算法的平均運行時間相都在呈上升趨勢。SAMP從圖可知對SAMP（S=5）而言隨著稀疏度的增加重構時間有指數增長的趨勢，而本算法的運算速度增加幅度小，而且當K值增大時，本算法的平均用時增長速度遠小于SAMP。相對其他算法，本算法可以對信號的稀疏度進行估計。進一步提高了實用價值。綜合以上實驗結果，SAgOMP即保留了SAMP中較高的重構精度，而且也保持了gOMP較快的運算速度。且稀疏度自適應。大大提高了本算法實用價值。

4 結語

為了進一步提高壓縮感知重構算法的實用性，本文在gOMP的基礎上增加了稀疏度估計，并修改了gOMP中每次選取原子S的選取。仿真結果表明，在微小的犧牲SAMP算法重構精度的條件下，大大降低了算法的平均運行時間。對基于壓縮感知使用實踐也是一種有用的重構算法。今后的目標是將本算法進一步應用到MassiveMIMO信道估計當中。