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

戰(zhàn)非

（西安航空學院 計算機學院 ，陜西 西安 710077）

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

戰(zhàn)非

（西安航空學院 計算機學院 ，陜西 西安 710077）

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

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

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

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

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

1 系統(tǒng)模型

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

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

以矩陣形式表示為：

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

2.1 最小二乘（LS）問題

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

1）普通最小二乘

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

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

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

2）總體最小二乘

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

進一步分析解向量x應滿足

2.2 LS信道估計

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

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

其中y是接收端接收的訓練序列向量；hLS是信道響應h的最小二乘估計值。

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

3 壓縮感知理論

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

3.1 數(shù)學模型

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

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

3.2 實現(xiàn)條件

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

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

4 稀疏信道估計算法分析

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

4.1 OMP信道估計算法分析

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

4.2 OMP算法流程

OMP算法流程可歸納為：

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

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

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

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

5）計算新的信號估計和殘差：

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

7）恢復信號h*的非零值指標為Λt中的元素，h*中第λt個元素的值等于ht的第j個元素；

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

5 實驗對比分析

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

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

圖2 LS算法與OMP算法信噪比對比圖

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

6 結(jié)束語

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

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

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

[3]汪璞，安瑋，鄧新蒲，等.使用壓縮感知的遙感圖像振蕩畸變幾何校正方法 [J].光學學報，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稿件編號：201605024

國家自然科學基金項目（71373203）

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