戰(zhàn)非

（西安航空學(xué)院 計(jì)算機(jī)學(xué)院 ，陜西 西安 710077）

基于壓縮感知OMP算法對(duì)稀疏信號(hào)重構(gòu)的研究

戰(zhàn)非

（西安航空學(xué)院 計(jì)算機(jī)學(xué)院 ，陜西 西安 710077）

文中針對(duì)無線通信系統(tǒng)中稀疏信道估計(jì)算法進(jìn)行研究，通過對(duì)比傳統(tǒng)的基于訓(xùn)練序列的信道估計(jì)算法LS，對(duì)基于壓縮感知的稀疏信道估計(jì)算法OMP進(jìn)行分析。討論了訓(xùn)練信號(hào)長度、信道稀疏度及噪聲強(qiáng)度對(duì)整個(gè)估計(jì)性能的影響。在相同的實(shí)驗(yàn)條件下生成二維稀疏信號(hào)，從精確重構(gòu)概率和信噪比方面對(duì)比了兩種算法的性能。證明壓縮感知方法可以有效的利用稀疏特性，在較短的訓(xùn)練序列情況下實(shí)現(xiàn)信道脈沖響應(yīng)的精確估計(jì)。

信道估計(jì)；壓縮感知；最小二乘算法；正交匹配追蹤算法

無線通信系統(tǒng)中，多徑傳播指由于電磁波的傳播存在反射、散射、繞射等現(xiàn)象，到達(dá)接收端的信號(hào)存在眾多不同路徑，不同的路徑具有不同的衰落和延時(shí)。信道狀態(tài)信息（CSI）是否準(zhǔn)確對(duì)接收端恢復(fù)信號(hào)至關(guān)重要。為了追求更高容量和可靠性，滿足實(shí)際應(yīng)用的需求，多入多出技術(shù)（MIMO）被廣泛的應(yīng)用。精確高效的信道估計(jì)是CSI獲取的重要條件。

信道估計(jì)方案可分為兩類：第一類是基于訓(xùn)練的信道估計(jì)方法，發(fā)射機(jī)端在時(shí)域、頻域、碼域發(fā)送訓(xùn)練符號(hào)，接收機(jī)端完成信道估計(jì)；第二類是信道盲檢測(cè)而不使用訓(xùn)練序列。接收機(jī)進(jìn)行信道估計(jì)僅通過數(shù)據(jù)載波信號(hào)的統(tǒng)計(jì)特性。傳統(tǒng)的基于訓(xùn)練的信道估計(jì)方案，主要基于線性重構(gòu)技術(shù)，以最小二乘為代表被廣泛應(yīng)用[1]。但隨著天線數(shù)量增多，寬帶傳輸?shù)惹闆r，出現(xiàn)了稀疏的多經(jīng)信道，傳統(tǒng)的線性重構(gòu)方法忽略了此稀疏性[2-3]。針對(duì)此情況，我們需進(jìn)行更優(yōu)的信道估計(jì)。

隨著壓縮感知領(lǐng)域的發(fā)展，壓縮感知被越來越多的應(yīng)用于稀疏多經(jīng)信道估計(jì)?；诖死碚摰乃惴ㄍ葌鹘y(tǒng)信道估計(jì)算法更加有效[4-5]。文中對(duì)基于壓縮感知的稀疏信道估計(jì)算法進(jìn)行研究，和線性重構(gòu)技術(shù)進(jìn)行比較分析，并通過仿真實(shí)驗(yàn)產(chǎn)生稀疏信號(hào)，利用OMP算法進(jìn)行信道估計(jì)和信號(hào)重構(gòu)，同時(shí)和LS算法進(jìn)行性能比較。

1 系統(tǒng)模型

離散信號(hào)模型中，我們定義多經(jīng)無線傳輸信道模型為一個(gè)有限沖擊響應(yīng)（FIR）濾波器h=[h0，h1，…，hL-1]T，其中L為信道長度。發(fā)送信號(hào)表示為x（n），則接收信號(hào)表示為：

其中ω（n）是方差為σ2的零均值加性高斯白噪聲。設(shè)訓(xùn)練序列的長度為N，則接收信號(hào)矢量可表示為：

以矩陣形式表示為：

2 傳統(tǒng)信道估計(jì)

2.1 最小二乘（LS）問題

線性方程Ax=b的求解問題可以解決很多工程應(yīng)用問題。其中A和b為已知，但其中一個(gè)或者兩者可能存在誤差，獨(dú)立方程的個(gè)數(shù)可能少于、等于或多于未知向量x的維數(shù)，分別對(duì)應(yīng)欠定、適定和超定方程[6]。

1）普通最小二乘

假設(shè)數(shù)據(jù)矩陣A沒有誤差，僅僅向量b存在誤差向量e，并且每一個(gè)誤差元素服從于零均值、等方差的獨(dú)立高斯分布。代價(jià)函數(shù)為：

使方程兩邊的誤差平方和最小。如果數(shù)據(jù)矩陣A列滿秩，方程有唯一解

在參數(shù)估計(jì)理論中，這種唯一確定的位置參數(shù)x是唯一可辨識(shí)。

2）總體最小二乘

假設(shè)數(shù)據(jù)矩陣A和向量b分別有誤差矩陣E和誤差向量e，并且每一個(gè)誤差元素服從零均值、等方差的獨(dú)立高斯分布，則x的解由如下優(yōu)化問題確定：

進(jìn)一步分析解向量x應(yīng)滿足

2.2 LS信道估計(jì)

最小二乘LS（Least-Square）是一種傳統(tǒng)的線性信道估計(jì)算法，其優(yōu)化問題可以表示為：

LS算法就是對(duì)上式中的參數(shù)h進(jìn)行估計(jì)，估計(jì)表達(dá)式為：

其中y是接收端接收的訓(xùn)練序列向量；hLS是信道響應(yīng)h的最小二乘估計(jì)值。

LS算法基于信道為密集多經(jīng)的假設(shè)，對(duì)于稀疏多經(jīng)信道，信道估計(jì)誤差較大。同時(shí)，性能受噪聲的影響也比較大。

3 壓縮感知理論

以Nyquist采樣定理為代表的信號(hào)采樣理論指導(dǎo)下，在將信號(hào)進(jìn)行模數(shù)轉(zhuǎn)換的過程中，不可避免的產(chǎn)生大量數(shù)據(jù)造成存儲(chǔ)空間的浪費(fèi)。基于壓縮感知（CS）理論所提出的新的采樣理論，對(duì)比Nyquist理論能以更低的采樣速率采樣信號(hào)[7]。其提出只要信號(hào)在某個(gè)變換域是稀疏的，則通過某個(gè)與變換基不相關(guān)的觀測(cè)矩陣，在低維空間上投影變換獲得的高維信號(hào)，再轉(zhuǎn)而進(jìn)行優(yōu)化問題的求解，進(jìn)而通過少量的投影高概率重構(gòu)原信號(hào)[8-9]。在該理論的框架下采樣速率取決于稀疏性和等距約束性而非帶寬。降低采樣速率，以高概率重構(gòu)信號(hào)，這種特性決定了壓縮感在數(shù)據(jù)壓縮、信道編碼及信號(hào)感知等方面具有廣泛的應(yīng)用型。

3.1 數(shù)學(xué)模型

壓縮感知是一個(gè)新的范式，其中信號(hào)在某個(gè)傳輸域中是稀疏的，從而可以通過比較少的采樣恢復(fù)信號(hào)。方程y=xh對(duì)于y而言是稀疏的，找到最有可能的解可以用優(yōu)化問題表示如下：

考慮具體的信道模型，通過利用矢量的稀疏性我們進(jìn)行優(yōu)化問題的求解找到稀疏解。

3.2 實(shí)現(xiàn)條件

式9中的優(yōu)化問題是一個(gè)NP難的組合優(yōu)化問題，具有指數(shù)復(fù)雜性。近年相關(guān)專家證明當(dāng)其數(shù)據(jù)模型滿足限制等距屬性 （RIP-restricted isometry property）條件時(shí)，上述非凸優(yōu)化問題可以轉(zhuǎn)化為如下凸問題：

定義RIP準(zhǔn)則為：其中0＜δs＜1，h∈Rn有不多于s個(gè)非零元素。最小范數(shù)下最優(yōu)化問題實(shí)現(xiàn)算法有內(nèi)點(diǎn)法和梯度投影法。內(nèi)點(diǎn)法速度慢但結(jié)果準(zhǔn)確，梯度投影法速度快但準(zhǔn)確度不如內(nèi)點(diǎn)法[10-11]。因?yàn)樽钚》稊?shù)下的算法較慢，所以文中將詳細(xì)討論的正交匹配追蹤算法（OMP），以及相關(guān)的一些較快速的貪婪算法被越來越多的使用。

4 稀疏信道估計(jì)算法分析

目前稀疏信道估計(jì)算法包括基追蹤BP（Basis Pursuit）算法、Lasso算法、正交匹配追蹤（OMP）算法等[12]，文中以O(shè)MP算法為例，分析器算法模型及流程，并通過仿真數(shù)據(jù)和傳統(tǒng)信道算法進(jìn)行對(duì)比。

4.1 OMP信道估計(jì)算法分析

正交匹配追蹤（OMP）算法是典型的貪婪算法。設(shè)h為長度為n的真實(shí)信號(hào)，它的稀疏度為s，即含有s個(gè)非零元素；X為m×n的測(cè)量矩陣，y=Xh為長度為m的測(cè)量值，其中m＜n。我們求解問題為在已知測(cè)量值y和測(cè)量矩陣X，恢復(fù)出真實(shí)信號(hào)h。由于測(cè)量值維數(shù)m小于真實(shí)信號(hào)維數(shù)n，該方程組沒有確定解，需要利用h的稀疏特性尋找出最優(yōu)解。OMP算法基本思想是貪婪迭代，在對(duì)問題求解時(shí)，總是做出在當(dāng)前看來最好的選擇，即不一定是整體最優(yōu)解，可能是局部最優(yōu)解[13]。

4.2 OMP算法流程

OMP算法流程可歸納為：

1）初始化殘差r0=y，指標(biāo)集Λ0=X，迭代技術(shù)y=1；

2）找到滿足下述最優(yōu)化問題的指標(biāo)λt

3）擴(kuò)充指標(biāo)集和矩陣Λt=Λt-1∪{λt}及Φt=[Φt-1，φλt]，Φ0為空矩陣；

4）求解如下最小二乘問題

5）計(jì)算新的信號(hào)估計(jì)和殘差：

6）t=t+1，若t＜s則返回步驟2）；

7）恢復(fù)信號(hào)h*的非零值指標(biāo)為Λt中的元素，h*中第λt個(gè)元素的值等于ht的第j個(gè)元素；

從Rn中任意選取稀疏度為s的信號(hào)h，X為m× n維觀測(cè)矩陣。執(zhí)行OMP算法y=Xh，若殘差rs在迭代s次后為0，則OMP完全復(fù)原了信號(hào)h；若殘差在迭代s次后不為0，則OMP算法失敗。

5 實(shí)驗(yàn)對(duì)比分析

實(shí)驗(yàn)中生成二維稀疏信號(hào)，通過Matlab仿真對(duì)比分析LS算法和OMP算法。編寫函數(shù)生成稀疏度K=16，大小為128×128的稀疏信號(hào)，然后進(jìn)行二維分離測(cè)量，設(shè)壓縮比為4，測(cè)量矩陣Φ為高斯采樣矩陣。通過LS算法和OMP算法在解碼端重構(gòu)稀疏信號(hào)，算法迭代執(zhí)行100次，實(shí)驗(yàn)結(jié)果從峰值信噪比和精確重構(gòu)概率兩方面來對(duì)比傳統(tǒng)信道估計(jì)算法和稀疏信道估計(jì)算法的差別。其中精確重構(gòu)概率的依據(jù)為重構(gòu)二維信號(hào)的估計(jì)值?滿足‖z-?‖2≤10-5。實(shí)驗(yàn)結(jié)果如圖1和圖2所示。

圖1 LS算法與OMP算法精確重構(gòu)概率對(duì)比圖

圖2 LS算法與OMP算法信噪比對(duì)比圖

通過對(duì)以上實(shí)驗(yàn)結(jié)果分析，在相同實(shí)驗(yàn)參數(shù)及二維稀疏信號(hào)的情況下，基于壓縮感知的稀疏信道估計(jì)OMP算法較傳統(tǒng)LS算法而言，精確重構(gòu)概率更高性能更優(yōu)越，在接收端能更好的重構(gòu)信號(hào)。

6 結(jié)束語

文中主要討論了無線通信系統(tǒng)中信道估計(jì)算法的應(yīng)用，簡要分析了壓縮感知理論及重點(diǎn)討論了基于壓縮感知理論的OMP算法。壓縮感知理論在針對(duì)多經(jīng)傳輸稀疏信號(hào)的重構(gòu)中發(fā)揮著越來越重要的作用。文中對(duì)比分析了傳統(tǒng)信道估計(jì)算法LS和稀疏信道估計(jì)算法OMP，通過仿真實(shí)驗(yàn)，生成二維稀疏信號(hào)，用兩種算法模擬信號(hào)重構(gòu)，從精確重構(gòu)概率和信噪比方面證明OMP算法性能更加優(yōu)越。

[1]王妮娜.基于壓縮感知理論的無線多徑信道估計(jì)方法研究[D].北京：北京郵電大學(xué)，2012.

[2]牛玉剛，甘峰浩，胡源.基于壓縮感知的擁塞控制機(jī)制[J].控制與決策，2015，30（2）:246-250.

[3]汪璞，安瑋，鄧新蒲，等.使用壓縮感知的遙感圖像振蕩畸變幾何校正方法 [J].光學(xué)學(xué)報(bào)，2015，35（1）:01100041-011000413.

[4]August Y，Vachman C，Rivenson Y，et al.Compressive hyperspectral imaging by random separable projections in both the spatial and the spectral domains[J].Applied Optics，2013，52（10）:D46-D54.

[5]Lee J H，Kim Y H.Compressed channel sen-sing using designated null subcarriers in full duplex wirelessOFDM systems [J].WirelessPers-onal Communications，2014，79（3）:1635-1645.

[6]Li Y.Pilot-symbol-aided channel estimation for OFDM in wirelesssystems[J].IEEE Trans.Veh. Technol，2000，49（4）:1207-1215.

[7]Schreiber W F.Advanced television systems for terrestrial broadcasting:Some problems and some proposed solutions[J].IEEE Proc，1995，83:958-981.

[8]Dai Y，He D，F(xiàn)ang Y，et al.Accelerating 2D ortho-gonal matching pursuit algorithm on GPU[J].The Jou-rnal of Supercomputing，2014，69（3）:1363-1381.

[9]Chakroun I，Melab N，Mezmaz M，et al.Com-bining multicore and GPU computing for solving combinatorial optimization problems[J].Journal of Parallel and Distributed Computing，2013，73 （12）:1563-1577.

[10]Candes E J，Romberg J，Tao T.Robust uncertainty principles:exact signal reconstruction from highly incomplete frequency information[J].IEEE Transactions on Information Theory，2006，52（2）:489-509.

[11]Donoho D L，Tsaig Y，Drori I，et al.Sparse solution of underdetermined systems of linear equations by stagewise orthogonal matching pursuit[J].IEEE Transactions on Information Theory，2012，58（2）:1094-1121.

[12]CadesE，RombergJ，Tao T.Robustuncertainty principles.Exact signal reconstruction from highly incomplete frequency information[J].IEEE Transactions on Information Theory.2006,52(2):489-509.

[13]Jia Y B，F(xiàn)eng Y，Wang Z L.Reconstructing hyperspectral images from compressive sensors via exploiting multiple priors[J].Spectroscopy Letters，2015，48（1）:22-26.

[14]Giacobello D，Christensen M G，Murthi M N etal. Retrieving sparse patterns using a compressed sensing framework:applications to speech coding based on sparse linear predicton[J].Signal Processing Letters，IEEE Jan.2010，17(1):103-106.

[15]Chen S，Donoho D，Saunders M.Atomic decomposition by basis pursuit[J].Siam Review.2001，43(1): 129-159.

A research on sparse signal reconstruction based on compressed sensing OMP algorithm

ZHAN Fei
（School of Computer Science，Xi’an Aeronautical Universities，Xi’an 710077，China）

In this paper，for wireless communication system in sparse channel estimation algorithm is studied.By comparing with the LS algorithm based on traditional training-based channel estimation and the OMP algorithm based on Compressed sensing.The effects of training signal length，channel sparsity and noise intensity on the performance of the estimation are discussed.Under the same experimental conditions，the two dimensional sparse signals are generated，and the performance of the two algorithms are compared in terms of the exact reconstruction probability and the signal to noise ratio.It is proved that the compressed sensing method can effectively utilize the sparse characteristics and realize the accurate estimation of the channel impulse response in the short training sequence.

channel estimation；compressed sensing；LS；OMP

TN91

：A

：1674－6236（2017）01-0071-04

2016-05-03稿件編號(hào)：201605024

國家自然科學(xué)基金項(xiàng)目（71373203）

戰(zhàn) 非（1981—），男，陜西西安人，碩士，講師。研究方向：軟件工程、通信工程、軟件開發(fā)、移動(dòng)互聯(lián)網(wǎng)應(yīng)用。