GOMP改進(jìn)算法在信道估計(jì)中的應(yīng)用

任曉奎　張芷寧

(遼寧工程技術(shù)大學(xué)電子與信息工程學(xué)院　遼寧 葫蘆島 125105)

0　引　言

在信號或者圖像的處理、傳輸?shù)确矫妫慰固夭蓸佣梢恢倍际亲裱臏?zhǔn)則，但由于其在資源利用率等的方面的缺陷促進(jìn)了壓縮感知CS(Compressed sensing)這一新采樣技術(shù)的出現(xiàn)。相比于奈奎斯特采樣定律，壓縮感知技術(shù)是將壓縮和采樣合并起來，利用較少的信號投影測量數(shù)據(jù)量，根據(jù)相應(yīng)的重構(gòu)算法，最終重構(gòu)出較為完整的信號[1-2]。

壓縮感知技術(shù)在穩(wěn)定中發(fā)展，在不同的研究領(lǐng)域中都有體現(xiàn)，尤其是在信道估計(jì)領(lǐng)域中。傳統(tǒng)的信道估計(jì)方法如最小二乘(LS)法[3]和最小均方誤差(MMSE)法[4]都需要大量的導(dǎo)頻信號才能做出準(zhǔn)確的

估計(jì)，并且這些方法主要針對的是密集型信道。由于近些年的研究我們可以知道，實(shí)際條件下的信號多數(shù)都是稀疏的，如果依舊不顧效率采用大量的導(dǎo)頻信號，會造成資源的嚴(yán)重浪費(fèi)。貪婪算法[5]是壓縮感知重構(gòu)算法中極為重要的一類算法，其中匹配追蹤MP(matching pursuit)、正交匹配追蹤算法OMP(orthogonal matching pursuit )[6]、廣義正交匹配追蹤(GOMP)算法[7]均已在稀疏信道估計(jì)中得以應(yīng)用[8-10]。但是，MP與OMP算法在應(yīng)用時(shí)所需要的迭代次數(shù)過多，所需時(shí)間較長，導(dǎo)致重構(gòu)效率不高。GOMP算法雖然在重構(gòu)時(shí)間上較OMP算法有所提高，但是由于選擇原子的方法不夠完備，再加上原子數(shù)目的增加，使其最小均方誤差(MSE)和誤碼率(BER)略差。而且OMP和GOMP算法的實(shí)現(xiàn)都需要稀疏度已知為前提才可實(shí)現(xiàn)，而實(shí)際環(huán)境這一前提無法滿足，導(dǎo)致了這幾種算法在信道估計(jì)中的局限性。本文提出改進(jìn)的GOMP算法在不知曉稀疏度的情況下，通過變步長實(shí)現(xiàn)稀疏自適應(yīng)匹配，并利用傅里葉變換的共軛對稱性在原子的選擇方面加以完善，提高了算法的應(yīng)用價(jià)值。

1　壓縮感知技術(shù)

壓縮感知技術(shù)的本質(zhì)，也就是把壓縮和采樣合二為一，即采樣的過程也就是完成壓縮的過程，經(jīng)壓縮感知采樣后的數(shù)據(jù)本身也就是壓縮后呈現(xiàn)的數(shù)據(jù)。通過對原始信號的一種提取后的精煉表達(dá)，減少了原始數(shù)據(jù)在存儲空間或者傳輸帶寬方面的需求。

運(yùn)用壓縮感知技術(shù)，需要關(guān)注的重點(diǎn)有兩個。第一個是怎樣設(shè)計(jì)出一個測量矩陣Φ，使得它可以在采樣的整個過程中包含著信號中較為有效的信息[11]；第二個是怎樣通過測量矩陣y重構(gòu)原始信號x[12]。為此應(yīng)該研究測量矩陣Φ應(yīng)該具備的性質(zhì)。首先應(yīng)從確保重構(gòu)的必要條件零空間特性開始。但是論證零空間特性是確保重構(gòu)的必要條件這一過程中，并沒有考慮到噪聲的影響，所以在面向?qū)嶋H條件時(shí)，有必要在更為嚴(yán)格的情況下進(jìn)行推導(dǎo)。這一點(diǎn)上促使有限等距性質(zhì)RIP(restricted isometry property)在整個壓縮感知理論中具有了重要地位[13]，即：

若存在δk∈(0,1)，使得：

(1)

2　算　法

2.1　OMP算法

正交匹配追蹤(OMP)算法與之前的算法相比，保證了殘差和已選列正交的這一條件，從而使相同的列并不會再一次被選中，減少了迭代的次數(shù)，優(yōu)化了整個迭代的過程[15]。

OMP算法的本質(zhì)是通過貪婪策略在Φ中來挑選一列原子。OMP算法首先選擇原子φi∈Φ，然后將觀測信號投影到原子上，以獲得殘差[16]。這些可以描述為:

y=ri+<φi,y>φi

(2)

它的目的是選擇出使殘差的二范數(shù)最小的原子。其中r1和<φi,y>φi明顯是正交的，因此：

(3)

(4)

在每次迭代中，新的原子總是和殘差保持正交關(guān)系。當(dāng)?shù)Ｖ箷r(shí)，獲得重建信號。這也就是OMP算法的基本原理。雖然OMP算法對于滿足RIP性質(zhì)的信號都可以做到較高精度的重構(gòu)[17]，但是當(dāng)原始信號具有較大長度時(shí)，OMP算法仍然只在一次迭代中選擇一個原子，因此需要更多的迭代次數(shù)來進(jìn)行原子的選擇，必然會導(dǎo)致重構(gòu)時(shí)間的大幅度增長，使得重構(gòu)的效率低下。而在實(shí)際的信道估計(jì)領(lǐng)域中，其他算法整體重構(gòu)精度的提高，無疑使算法的復(fù)雜度成為其走向?qū)嶋H應(yīng)用的最大障礙。再加上OMP算法需要信號的稀疏度作為先驗(yàn)信息，也極大程度地限制了它的發(fā)展。

2.2　GOMP算法

GOMP算法在選擇原子這一方面較OMP算法進(jìn)行了改進(jìn)[18]。GOMP算法首先計(jì)算內(nèi)積。

C={ci|ci=yTφii=1,2,…,N}

(5)

OMP算法選擇最相關(guān)的原子，其對應(yīng)于C中的最大系數(shù)。但GOMP算法在每個迭代步驟中選擇n個頂部原子(ci1,ci2,…,cin)。然后使用式(4)獲得y的近似值，并使用以下公式更新殘差：

(6)

式中：ΦΛ是由選自于Φ的原子所組成的子矩陣。

GOMP算法的具體步驟如下：

已知觀測向量y，傳感矩陣Φ，原子選擇數(shù)S(S≤K)，迭代次數(shù)t。

(1) 進(jìn)行初始化：r0=0,H=φ,t=0,J=φ。

(2) 令迭代次數(shù)增加：t=t+1。

(3) 計(jì)算相關(guān)系數(shù)：Ct=ΦTrt-1。

(4) 從計(jì)算出的Ct中挑選出最大的S個原子，然后將這些原子添加到集合J中。

(5) 更新索引集：H=H∪J。

由以上可知，選擇原子數(shù)目的增加使得GOMP算法在收斂速度上比OMP算法要快得多，重建效率也有了提升，但需要提前了解稀疏度K這一不足仍沒有得到較好的改進(jìn)。對于原子選擇方面，有研究結(jié)果表明，當(dāng)時(shí)域信號將傅里葉基作為稀疏基時(shí)，重構(gòu)過程中出現(xiàn)的少量的對頻譜的估計(jì)錯誤，也將會很大程度上影響重構(gòu)的精度[19]。如果僅是利用相關(guān)性來進(jìn)行原子的選擇，會使選擇具有盲目性。并且在觀測過程中出現(xiàn)大量噪聲的情況下，容易出現(xiàn)更多的估計(jì)錯誤，從而導(dǎo)致原子匹配程度和支撐集選擇的準(zhǔn)確性降低，進(jìn)而影響信號重構(gòu)的成功率。因此，應(yīng)該從如何適應(yīng)在稀疏度K未知情況下重建信號，以及如何更準(zhǔn)確更穩(wěn)定地選擇原子這兩方面同時(shí)對GOMP算法加以改進(jìn)。

2.3　改進(jìn)的GOMP算法

原始信號x與各個原子之間的相關(guān)性在持續(xù)迭代的過程中有所下降[20]。先前幾次迭代中所選擇的原子體現(xiàn)的作用更大，選擇的不確定性導(dǎo)致的原子錯誤將會對整個結(jié)果產(chǎn)生更大的影響。因此，在早期的迭代過程中，我們將選擇原子的個數(shù)設(shè)置為一個較小的數(shù)值，以免選擇出大量的錯誤原子。而后，當(dāng)殘余量減少緩慢的時(shí)候，逐漸增大S的取值。

其次，通過把傅里葉變換的共軛對稱性與之前利用相關(guān)系數(shù)這一選擇原子的唯一依據(jù)相結(jié)合，增強(qiáng)原子選擇的準(zhǔn)確性，以增強(qiáng)整個算法的成功率。下面對傅里葉變換的共軛對稱性進(jìn)行分析。

若f(t)為實(shí)信號，則它的傅里葉變換為F(jω)[21]，可以如下表示：

(7)

考慮到r-jωt=cosωt-jsinωt，則式(7)可寫為：

R(ω)-jX(ω)=|F(jω)|ejφ(ω)

(8)

式中：頻譜函數(shù)的實(shí)部與虛部以及模量與相角均為ω的實(shí)函數(shù)，并分別為：

(9)

(10)

(11)

(12)

由式(9)-式(12)可知，頻譜函數(shù)的實(shí)部與模量是頻率ω的偶函數(shù)，虛部與相位是頻率ω的奇函數(shù)。

如果f(t)是t的偶函數(shù)，則式(10)的積分為零，其頻譜函數(shù)僅有實(shí)部，是ω的實(shí)偶函數(shù)。即:

(13)

由此可以得到:F(jω)=F*(-jω)。

如果f(t)是t的奇函數(shù)，則式(9)的積分為零，其頻譜函數(shù)僅有虛部，是ω的虛奇函數(shù)。即:

(14)

由此可以得到:F(jω)=-F*(-jω)。

研究可知，大多數(shù)的時(shí)域信號在傅里葉基中都能保持有良好的稀疏性。當(dāng)把傅里葉基作為稀疏基時(shí)，信號的各個采樣點(diǎn)都能找到以信號的采樣頻率的一半為中心與自身對稱的點(diǎn)，也就是傅里葉變換的共軛對稱性[22-23]。

改進(jìn)的算法將傅里葉基作為稀疏基，以使信號具有傅里葉共軛對稱的性質(zhì)。在選擇原子的時(shí)候，只是對相關(guān)系數(shù)的前一半進(jìn)行篩選，選擇出相關(guān)性最高的S個原子，將它們的下標(biāo)添加進(jìn)入集合J中。之后利用傅里葉變換的共軛對稱性對剩余的原子進(jìn)行選擇，也就是在剩余的相關(guān)系數(shù)中找出與添加進(jìn)入集合J的原子的對稱點(diǎn)即可，然后一并加入到集合J中。此時(shí)，集合J中有2S個原子，只需要在這里挑選出最匹配的S原子再加入新的集合中即可。

雖然OMP與GOMP算法選擇原子的數(shù)目不相同，但都是以相關(guān)性作為選擇原子的唯一標(biāo)準(zhǔn)。兩者需要將全部相關(guān)系數(shù)進(jìn)行比較，從中篩選出相關(guān)性最高的一個或幾個原子。相比較來說，改進(jìn)后的算法只需要對前一半相關(guān)系數(shù)進(jìn)行處理，另一半可以在前一半的基礎(chǔ)上得出，從而提高了原子選擇的效率。并且在利用了傅里葉變換的共軛對稱性的情況下，兩種標(biāo)準(zhǔn)相互輔助，使原子的選擇更加針對和可靠，當(dāng)觀測過程出現(xiàn)大量噪聲時(shí)候仍能有效控制原子選擇這一過程，進(jìn)而提高了原子選擇的精度。

改進(jìn)的GOMP算法的具體步驟如下：

已知觀測向量y，傳感矩陣Φ，原子選擇數(shù)S(數(shù)值較小)，迭代次數(shù)t。

(1) 進(jìn)行初始化：r0=0,H=φ,t=0,J=φ,Q=φ。

(2) 令迭代次數(shù)增加：t=t+1。

(3) 計(jì)算相關(guān)系數(shù)：Ct=ΦTrt-1。

(4) 在步驟(3)計(jì)算出的相關(guān)系數(shù)Ct的前半部分中選出最大的S個原子，然后將這些原子的下標(biāo)添加到集合J中。

(5) 對于剩余部分，利用傅里葉變換的共軛對稱性，將與添加到集合J中的原子下標(biāo)所對稱的點(diǎn)找出來，同樣加入到集合J中。最終，在集合J中選出最大的S個原子組成新的集合Q。

(6) 更新索引集：H=H∪Q。

其中,ε1就是GOMP算法中的閾值，它的取值受原始信號中噪聲的影響；而ε2是為了判斷殘差減少的程度，低于這個取值的時(shí)候，選擇原子的個數(shù)將不會再增加。在大量實(shí)驗(yàn)的驗(yàn)證下，本文將ε2的取值設(shè)置為0.7，并應(yīng)用于接下來的仿真實(shí)驗(yàn)中。

以上就是改進(jìn)的GOMP算法的具體步驟。針對上文提到的先前算法的不足之處，通過可變步長來實(shí)現(xiàn)稀疏自適應(yīng)匹配，并利用傅里葉變換的共軛對稱性增強(qiáng)選擇原子的效率和準(zhǔn)確性。

3　實(shí)驗(yàn)仿真與驗(yàn)證

在理論的基礎(chǔ)上，本文通過如下的仿真實(shí)驗(yàn)，從不同的參考角度與之前的兩種算法進(jìn)行對比，證明改進(jìn)后的GOMP算法在信道估計(jì)性能方面的優(yōu)越性。仿真硬件為Intel(R) Core(TM) i5-3230M CPU，主頻為2.6 GHz，內(nèi)存為8 GB，Microsoft Windows 7操作系統(tǒng)，仿真軟件為MATLAB。

仿真如下，假設(shè)天線方案為2根發(fā)射天線和2根接收天線，系統(tǒng)子載波個數(shù)為1 024，導(dǎo)頻數(shù)為25，信道長度為30，并且信道參數(shù)在一個OFDM符號內(nèi)保持不變。利用算法的歸一化均方誤差(MSE)和誤比特(BER)來反映幾種算法的估計(jì)性能[18]，MSE的定義為：

(10)

二者數(shù)值越小，代表估計(jì)的性能越好，反之亦然。

圖1 是不同信噪比情況下，三種算法的MSE數(shù)值大小比較。不難看出，信噪比的不斷增大，使得三種算法的MSE數(shù)值均呈現(xiàn)一種下降的趨勢。但從整體來說，改進(jìn)后的GOMP算法與另外兩種相比數(shù)值更小。而在任意相同的條件下，改進(jìn)后的GOMP算法都比另外兩種的MSE數(shù)值要低，凸顯了性能的優(yōu)越性。

圖1　不同信噪比條件下三種算法的MSE性能比較

圖2展示了三種算法在不同信噪比情況下的BER性能比較?？梢钥闯?，信噪比的不斷增大，說明了信號干擾逐漸減小。因此三種算法的BER數(shù)值都會降低。改進(jìn)的GOMP算法與另外兩種對比來說，幅度更大，趨勢更強(qiáng)，BER數(shù)值更小。由此說明，改進(jìn)的GOMP算法具有更好的性能。

圖2　不同信噪比條件下三種算法的BER性能比較

由于選擇原子數(shù)量S的不斷增大，每一次增大程度n的取值不同也對算法的性能產(chǎn)生影響。圖3是改進(jìn)的GOMP算法在S的數(shù)值大小相同而n的不同取值情況下，與OMP算法和GOMP算法在迭代次數(shù)方面的比較。從理論上來說，GOMP算法及其改進(jìn)算法在選擇原子的數(shù)目上面要多于OMP算法，所以說在這一方面上必然比OMP算法更有效率。由圖中還可以看出，改進(jìn)的GOMP算法對稀疏性具有良好的適應(yīng)性，無論K值如何，算法都能很好地進(jìn)行，而OMP算法在這一方面顯示出了不足。對于n的取值來說，迭代的次數(shù)會隨著n取值的增大而減小，但精確度并不會因此而降低。

圖3　OMP算法和GOMP算法的比較

峰值信噪比(PSNR)是一種評價(jià)圖像的客觀標(biāo)準(zhǔn)，PSNR公式如下：

(11)

式中:X和X1分別代表原始信號和重構(gòu)信號。

表1中顯示了三種算法的PSNR值和運(yùn)行時(shí)間。由表可以看出，三者的PSNR值相差不多，改進(jìn)的算法可以很好地適應(yīng)稀疏性，保證了重構(gòu)的效果。在運(yùn)行時(shí)間方面，GOMP算法及其改進(jìn)算法較OMP算法都有大幅度的提高。驗(yàn)證了改進(jìn)的算法在保證了重構(gòu)效果的同時(shí)提高了效率。

表1　各算法PSNR值和運(yùn)行時(shí)間

4　結(jié)　語

本文根據(jù)壓縮感知理論知識以及信道的特性，提出了一種基于壓縮感知改進(jìn)的廣義正交匹配追蹤算法。此算法與先前的GOMP算法相比，可以實(shí)現(xiàn)自適應(yīng)匹配，無需預(yù)先知道稀疏度，并且在原子選擇方面進(jìn)行了優(yōu)化。由仿真實(shí)驗(yàn)的結(jié)果可以看出，提出的算法可以有效地提高重構(gòu)信號的精度和效率，并在此基礎(chǔ)上降低了傳統(tǒng)算法的復(fù)雜度，使該算法可以更好地應(yīng)用在信道估計(jì)領(lǐng)域中。

[1] 焦李成，楊淑媛，劉芳,等.壓縮感知回顧與展望[J].電子學(xué)報(bào)，2011,39(7)：1651-1662.

[2] Donoho D L, Tsaig Y. Extensions of compressed sensing [J]. Signal Processing, 2006,86(3):533-548.

[3] Tropp J A, Gilbert A C. Signal Recovery from Random Measurements via Orthogonal Matching Pursuit [J]. IEEE Transactions on Information on Information Theory, 2007,53(12):4655-4666.

[4] 李然,干宗良,崔子冠,等.壓縮感知圖像重建算法的研究現(xiàn)狀及其展望[J].電視技術(shù),2013,37(19):192-196.

[5] Kim Seung-Jean, Koh K, Lustig M, et al. An Interior-Point Method for Large-Scale l1-Regularized Least Squares[J]. IEEE Journal of Selected Topics in Signal Processing, 2007, 1(4): 606-617.

[6] 何雪云，宋榮方，周克琴. 基于壓縮感知的OFDM系統(tǒng)系數(shù)信道估計(jì)新方法研究[J].南京郵電大學(xué)學(xué)報(bào)，2010,30(2)：60-65.

[7] Wang J, Kwon S, Shim B. Generalized orthogonal matching pursuit[J]. IEEE transactions on signal processing, 2012(60):6202-6216.

[8] Cotter S F, Rao B D. Sparse channel estimation via matching pursuit algorithm [J]. IEEE transactions on Communications, 2002,50(3):374-377.

[9] Karabulut G Z, Yongacoglu A. Sparse channel estimation using orthogonal matching pursuit algorithm[J]. IEEE 60th Vehicular Technology Conference, 2004. VTC2004-Fall. 2004.

[10] 甘偉，許錄平，羅楠, 等.一種自適應(yīng)壓縮感知重構(gòu)算法[J].系統(tǒng)工程及電子設(shè)計(jì)，2011,33(9)：1948-1953.

[11] 呂偉杰，陳霞，劉紅珍.基于壓縮感知的自適應(yīng)匹配追蹤優(yōu)化[J].系統(tǒng)工程與電子技術(shù)，2015,37(5)：1201-1205.

[12] Donoho D L. Compressed sensing[J]. IEEE Transactions on Information Theory, 2006, 52(4):1289-1306.

[13] Fiqueiredo M A T, Nowak R D, Wright S J. Gradient projection for sqarse reconstruction: application to compressed sensing and other inverse problems[J]. IEEE Journal of Selected Topics in Signal Processing, 2007,1(4):586-597.

[14] 甘偉，許錄平，蘇哲.一種壓縮感知重構(gòu)算法[J].電子與信息學(xué)報(bào)，2010,32(9)：2151-2155.

[15] 趙龍慧，潘樂炳，李寶清.OFDM稀疏信道估計(jì)中改進(jìn)的OMP算法[J].計(jì)算機(jī)工程與設(shè)計(jì)，2015,36(7)：1701-1705.

[16] Davenport M A, Boufounos P T, Wakin M B, et al. Signal Processing With Compressive Measurements[J]. IEEE Journal of Selected Topics in Signal Processing, 2010, 4(2):445-460.

[17] 石光明，劉丹華，高大化.壓縮感知理論及其研究進(jìn)展[J].電子學(xué)報(bào)，2009,37(5)：1070-1081.

[18] 呂方旭, 張金成, 王泉,等. 基于傅里葉基的自適應(yīng)壓縮感知重構(gòu)算法[J]. 北京航空航天大學(xué)學(xué)報(bào), 2014, 40(4)：544-550.

[19] 朱延萬，趙擁軍，孫兵.一種改進(jìn)的稀疏度自適應(yīng)匹配追蹤算法[J].信號處理，2012,28(1)：80-86.

[20] 王妮娜，桂冠，蘇冰濤，等.基于壓縮感知的MIMO-OFDM系統(tǒng)稀疏信道估計(jì)方法[J].電子科技大學(xué)學(xué)報(bào)，2013,42(1)：59-62.

[21] 趙龍慧，潘樂炳，李寶清.OFDM稀疏信道估計(jì)中改進(jìn)的OMP算法[J].計(jì)算機(jī)工程與設(shè)計(jì)，2015,36(7)：1701-1705.

[22] 高西全，丁玉美.數(shù)字信號處理[M].西安：西安電子科技大學(xué)出版社，2008：84-87.

[23] 楊盼.壓縮感知中改進(jìn)的匹配追蹤類算法研究[D].安徽：安徽大學(xué)，2015.