基于壓縮感知OMP算法對稀疏信號重構的研究

戰非

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

基于壓縮感知OMP算法對稀疏信號重構的研究

戰非

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

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

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

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

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

隨著壓縮感知領域的發展，壓縮感知被越來越多的應用于稀疏多經信道估計。基于此理論的算法往往比傳統信道估計算法更加有效[4-5]。文中對基于壓縮感知的稀疏信道估計算法進行研究，和線性重構技術進行比較分析，并通過仿真實驗產生稀疏信號，利用OMP算法進行信道估計和信號重構，同時和LS算法進行性能比較。

1 系統模型

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

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

以矩陣形式表示為：

2 傳統信道估計

2.1 最小二乘（LS）問題

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

1）普通最小二乘

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

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

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

2）總體最小二乘

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

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

2.2 LS信道估計

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

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

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

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

3 壓縮感知理論

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

3.1 數學模型

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

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

3.2 實現條件

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

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

4 稀疏信道估計算法分析

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

4.1 OMP信道估計算法分析

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

4.2 OMP算法流程

OMP算法流程可歸納為：

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

2）找到滿足下述最優化問題的指標λ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維觀測矩陣。執行OMP算法y=Xh，若殘差rs在迭代s次后為0，則OMP完全復原了信號h；若殘差在迭代s次后不為0，則OMP算法失敗。

5 實驗對比分析

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

圖1 LS算法與OMP算法精確重構概率對比圖

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

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

6 結束語

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

[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，Fang 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，Feng 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）

戰 非（1981—），男，陜西西安人，碩士，講師。研究方向：軟件工程、通信工程、軟件開發、移動互聯網應用。