張龍

（上海海事大學(xué)信息工程學(xué)院，上海201306）

1 壓縮感知理論簡介

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

（1）設(shè)長度N的信號(hào)x在正交基ψ上是稀疏度為k;

（2）如果能找到一個(gè)與ψ不相關(guān)的觀測基φ;

（3）用觀測基Φ觀測信號(hào)得到長度為M的一維測量值M個(gè)觀測值Y，K小于M遠(yuǎn)遠(yuǎn)小于N;

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

圖1 壓縮感知理論框架

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

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

（1）信號(hào)的稀疏表示。稀疏性簡單點(diǎn)的解釋就是信號(hào)含有k個(gè)非零值，其他系數(shù)值為零或遠(yuǎn)小于k個(gè)非零值。現(xiàn)實(shí)中的大多信號(hào)x往往并不是稀疏的，所以需要在某個(gè)對(duì)應(yīng)的稀疏基上進(jìn)行稀疏表示。一般的自然信號(hào)x本身并不是稀疏的，需要在某種稀疏基上進(jìn)行稀疏表示。

x=Ψθ

Ψ為稀疏基矩陣，θ為稀疏系數(shù)（θ只有K個(gè)是非零值（K<

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

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

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

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

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

2 稀疏度自適應(yīng)的廣義正交匹配重構(gòu)算法

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

2.1 SAgOMP算法流程

為了便于對(duì)算法進(jìn)行闡述，下面是對(duì)算法用到的符號(hào)的解釋，如表1和程序1所示。

表1 SAgOMP算法流程符號(hào)說明

程序1 SAgOMP算法流程符號(hào)說明

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

輸出：信號(hào)稀疏表示系數(shù)估計(jì)θ?。

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

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

（4）將S=K0/3求整，若K0小于3則默認(rèn)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，否則停止迭代進(jìn)入第10步；

（10）重構(gòu)所得θ?在Λt有非零項(xiàng)，其值分別為最后一次迭代所得θt。

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

2.2 稀疏度估計(jì)計(jì)算

在稀疏信號(hào)自適應(yīng)迭代算法中，每次選擇的原子個(gè)數(shù)L直接影響到算法的重構(gòu)精度和運(yùn)算速度。在SAMP中通過不停的修正L的大小來提高重構(gòu)精度，則導(dǎo)致其計(jì)算量也很大。既然得到了估計(jì)稀疏度，那我們?yōu)槭裁床恢苯舆x擇與重構(gòu)速度快的算法相結(jié)合。在OMP中每次選取S次原子，來提高運(yùn)算速度。所以本文借鑒[11]中的命題1:

命題1中符號(hào)“<>”表示計(jì)算內(nèi)積；δK表示上述策略中使用到的估計(jì)參數(shù)；K0表示信號(hào)稀疏度的估計(jì)值K表示稀疏度的真實(shí)值。uK0表示與測量值y最相關(guān)的原子索引集合；

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

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

3.1 實(shí)驗(yàn)設(shè)置

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

測量矩陣 A：M×N（256×512）的高斯隨機(jī)矩陣作為仿真實(shí)驗(yàn)的測量矩陣。

信號(hào)源：假設(shè)信號(hào)x是N×1維信號(hào)，

迭代終止條件：當(dāng)殘差‖‖r2小于le-6算法停止迭代，或達(dá)到預(yù)設(shè)的迭代次數(shù)，算法重構(gòu)失敗。

重構(gòu)成功認(rèn)定的標(biāo)準(zhǔn)：‖‖x-x?2

3.2 步長L的選取

為了在gOMP算法中選取合適的S，改良gOMP算法。本實(shí)驗(yàn)對(duì)重構(gòu)精度和k（S=K0/k，k是我們選擇的系數(shù)）對(duì)不同稀疏度進(jìn)行了仿真。得到不同稀疏度下，k值對(duì)重構(gòu)概率的影響。

圖2 不同稀疏度下，k值對(duì)重構(gòu)概率的影響

由圖2可知，當(dāng)取值k=3,4,5,6,7時(shí)重構(gòu)概率基本一樣。這是因?yàn)楫?dāng)k越大，則步長越小。通過最小二乘法進(jìn)行運(yùn)算時(shí)，每次選取的系數(shù)匹配度更高，則結(jié)果更精確?，F(xiàn)在為了確保精度并兼顧運(yùn)算速度，每個(gè)取盡可能多的原子數(shù)進(jìn)行迭代。本文選擇了k=3，因?yàn)樵诖嘶A(chǔ)上提升k值，重構(gòu)準(zhǔn)確率的提升已經(jīng)不明顯了，所以提高每次選擇的原子數(shù)，進(jìn)一步提高運(yùn)算速度。

3.3 重構(gòu)成功概率分析

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

圖3 不同恢復(fù)算法的不同稀疏度下的重構(gòu)概率

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

3.4 平均運(yùn)算時(shí)間和稀疏度分析

圖3 不同稀疏度下，不同算法與所需重構(gòu)時(shí)間

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

4 結(jié)語

為了進(jìn)一步提高壓縮感知重構(gòu)算法的實(shí)用性，本文在gOMP的基礎(chǔ)上增加了稀疏度估計(jì)，并修改了gOMP中每次選取原子S的選取。仿真結(jié)果表明，在微小的犧牲SAMP算法重構(gòu)精度的條件下，大大降低了算法的平均運(yùn)行時(shí)間。對(duì)基于壓縮感知使用實(shí)踐也是一種有用的重構(gòu)算法。今后的目標(biāo)是將本算法進(jìn)一步應(yīng)用到MassiveMIMO信道估計(jì)當(dāng)中。