基于壓縮感知的OMP改進(jìn)重構(gòu)算法

王軍,孔令斌,趙潔

(西安郵電大學(xué)a.通信與信息工程學(xué)院; b.電子工程學(xué)院,西安 710121)

?

基于壓縮感知的OMP改進(jìn)重構(gòu)算法

王軍a,孔令斌a,趙潔b

(西安郵電大學(xué)a.通信與信息工程學(xué)院; b.電子工程學(xué)院,西安 710121)

摘要:針對無線通信網(wǎng)絡(luò)近些年出現(xiàn)的大數(shù)據(jù)量信號的情況,在對信號采樣的同時進(jìn)行適當(dāng)壓縮,利用合適的重構(gòu)算法實現(xiàn)了用少量的采樣值或觀測值對信號進(jìn)行重構(gòu)。在原有基于OMP(正交匹配追蹤)的壓縮感知重構(gòu)算法的基礎(chǔ)上引入AS(交替步長),提出一種新的改進(jìn)算法——GP-OMP(梯度正交匹配追蹤)算法。實驗結(jié)果表明,該改進(jìn)算法利用前一感知時刻獲得的頻譜信息,不僅能有效地降低重構(gòu)算法的計算量,還能有效地減少重構(gòu)耗時,并得到與原有方法基本一致的重構(gòu)效果。

關(guān)鍵詞:重構(gòu)算法;壓縮感知;交替步長;頻譜感知

0　引 言

近年來,一種新型的采樣理論——壓縮感知[1]在信號處理領(lǐng)域誕生。該理論的突出優(yōu)點是將傳統(tǒng)的數(shù)據(jù)壓縮與數(shù)據(jù)采集結(jié)合起來。重構(gòu)算法是信號處理領(lǐng)域和應(yīng)用數(shù)學(xué)中一個新的研究方向,是壓縮感知理論的一個關(guān)鍵部分,它涉及到壓縮信號的精確重構(gòu)和采樣過程中的準(zhǔn)確性驗證。我們在實踐中使用了不同的優(yōu)化算法,其中凸優(yōu)化算法中使用了BP(基追蹤)、LARS(最小角度回歸)[2]和GPRS(梯度投影的稀疏重構(gòu))[3]。近年來,貪婪策略已被廣泛使用,在某些情況下它比推算的方法具有更好的性能。在MP(匹配追蹤)中,OMP[4](正交匹配追蹤)、正則OMP[5]和稀疏自適應(yīng)MP[6]均為貪婪算法。通過將MP與優(yōu)化算法相結(jié)合,從而推導(dǎo)出新的算法——DP(定向追蹤)[7]算法。OMP[8]算法是常用的一種信號重構(gòu)算法,但是當(dāng)信號長度很長時,信號重構(gòu)過程耗時會更長,頻譜感測的實時性會受到影響。

本文首先分析了壓縮感知的基本理論和現(xiàn)有的重構(gòu)算法,然后通過使用AS(交替步長)法,即基于所述優(yōu)化理論改變步長來改善GP(梯度追蹤)算法,以克服最速下降步長大小的鋸齒現(xiàn)象,最后與OMP算法組成新的改進(jìn)算法。結(jié)果表明,該方法不僅可以大大減少信號重構(gòu)算法的耗時,還可以達(dá)到與現(xiàn)有OMP算法基本一致的重構(gòu)效果。

1　壓縮感知理論

目前,對壓縮感知理論的研究已有了很大的進(jìn)展,其中針對重構(gòu)算法的研究,一些學(xué)者提出了貪婪算法,但這類算法重構(gòu)精度比較低,且耗時較多;而另一些學(xué)者則提出了基于貝葉斯的壓縮感知方法。此外,還有很多需要解決的問題。

1.1壓縮感知的基本框架

壓縮感知理論是新的信號采樣、編碼和解碼理論。信號的采樣速率不僅與帶寬有關(guān),還與信號的結(jié)構(gòu)和位置密切相關(guān)。編碼過程是一種優(yōu)化的算法,是圍繞觀測矩陣展開的。該理論已經(jīng)被證實,即以一個相對較低的采樣速率對信號進(jìn)行正確采樣,能以很高的概率重構(gòu)出原始信號。

壓縮感知理論框架如圖1所示,主要包括稀疏信號的3個步驟:首先,如果信號x∈RN(R為實數(shù),N為維數(shù))在某個正交基或緊框架Ψ上是可壓縮的,則計算變換系數(shù)Θ=ΨTx,Θ為Ψ的等價或近似稀疏表示;然后,設(shè)計一個平穩(wěn)變換基Ψ和不相關(guān)的M×N觀測矩陣Φ,對Θ進(jìn)行觀測,得到觀測集合=ΦΘ=ΦΨTx;最后,使用0-范數(shù)意義下的優(yōu)化問題求解x的精確或近似逼近:min‖ΨTx‖0s.t ACSx=ΦΨTx=,

式中,s.t表示條件,ACS為信息算子,求得向量x在稀疏基上的最佳表示。

圖1　壓縮感知理論框架

1.2壓縮感知采樣過程

1.2.1信號的稀疏性定義

信號的稀疏性或可壓縮性是壓縮感知理論的一個重要前提和基礎(chǔ)。但在現(xiàn)實中,信號通常是不稀疏的,需要在某個變換域下逼近稀疏,常用的方法是對信號進(jìn)行正交變換使其稀疏或可壓縮。為了簡化模型,通?？紤]離散信號x的長度為N,即x=[x1, x2,…,xN]T,由信號理論可知,x可以用一組基ΨT={Ψ1,Ψ2,…,ΨN}線性表示,即

式中,S是對x進(jìn)行稀疏后的N×1維向量,其中大多數(shù)元素的值為0。稀疏表示的原理是通過線性空間的映射將信號在稀疏的空間進(jìn)行表示。Ψ是N× N維信號x的稀疏基矩陣。

1.2.2壓縮感知的線性測量過程

壓縮感知的核心是線性測量過程。記x為采樣得到的長度為N的信號,可以通過壓縮感知直接獲得長度為M(M< N)的重構(gòu)信號∶=Φx。對原始N維信號x進(jìn)行觀測,獲得M維向量信號,然后利用優(yōu)化方法從觀測值中高概率地恢復(fù)出原始信號x。如果信號x是不稀疏的,則可以在正交稀疏交換下用系數(shù)向量S表示為x=ΨS,其中S為K稀疏,即只有K個非零元素,因此測量過程可以表示為

式中,Θ=ΦΨ為M×N維矩陣。由于信號是K稀疏的,因此用K個系數(shù)就能夠從M個測量值中準(zhǔn)確地重構(gòu)出原始信號x(得到一個最優(yōu)方案)。

為了保證算法的收斂性,使K個系數(shù)可以通過M個測量值精確恢復(fù),感知矩陣Θ必須滿足RIP(限制等距性)[9],即對任何具有K稀疏的矢量v,矩陣Θ都能保證如下不等式成立:

式中,0<δ<1。RIP的等效情況是測量矩陣Φ和稀疏基Ψ不滿足相關(guān)要求,保證觀測矩陣不會把兩個不同的K稀疏信號映射到同一個集合。

1.2.3壓縮感知稀疏重構(gòu)過程

由于最優(yōu)化問題與信號稀疏分解中的優(yōu)化問題非常相似,11范數(shù)最小問題在一定條件下與l0范數(shù)最小問題是等價的。為了得到相同的解決方案,上式可轉(zhuǎn)化為11范數(shù)的最小優(yōu)化問題,即min‖S‖l1s.t.=ΦΨS,也被稱為BP。貪婪算法

2　壓縮感知重構(gòu)算法研究

如何設(shè)計出復(fù)雜度更低、更精確、更穩(wěn)定且所需觀察數(shù)目較少的重構(gòu)算法,始終是壓縮感知理論信號重構(gòu)問題的主要研究方向。在現(xiàn)階段,我們所知道的壓縮感知重構(gòu)算法大致可以分為以下幾類:貪婪迭代算法、凸優(yōu)化算法或最優(yōu)化逼近方法、基于貝葉斯的重構(gòu)算法和其他重構(gòu)算法。

2.1最速下降法的相關(guān)理論

最速下降法基于最優(yōu)化理論。針對無約束極小值問題min f(x)=(xTAx)/2-bTx,式中,A為對稱正定矩陣,假設(shè)函數(shù)f(x)是連續(xù)可微的,且其在點xk的梯度為gk=?f(xk),考慮函數(shù)的泰勒展開式為記x-xk=akdk,其中,ak為一數(shù)值,dk是n維列向量,則滿足(dk)Tgk<0的方向是dk下降方向。當(dāng)且僅當(dāng)dk=-gk時,(dk)Tgk最小,從而-gk是最速下降方向。以這個方向為搜索方向,搜索找到迭代函數(shù)的最小值,這就是已知的最速下降法。

最速下降法的迭代模式為xk+1=xk-akgk,且其步長ak滿足,解決最優(yōu)化問題必須滿足,由此可得為最速下降步長。由于在求解過程中當(dāng)前負(fù)梯度方向相互垂直,導(dǎo)致搜索路徑呈鋸齒形,因此采用這種方法來搜索最優(yōu)解時會走很多彎路,影響了算法的收斂速度。

2.2GP算法的改進(jìn)

由于GP算法是基于最速下降法的,在進(jìn)行迭代求解時步驟最快,導(dǎo)致相鄰的兩個搜索方向互相垂直,搜索路徑呈鋸齒形,因此影響了算法的收斂速度。針對GP算法的這一缺點,本文提出了使用AS法對原步長進(jìn)行改善。

基于最優(yōu)化理論中的最速下降法,每次迭代都致力于使重構(gòu)誤差最小化,n次迭代的誤差函數(shù)可表示如下:

本文采取改變或縮短步長的策略來提高收斂速率,即AS法。AS法是將BB(兩點步長梯度法)步長aBB和最速下降步長aSD交替使用,交替方式如下:

3　改進(jìn)的GP-OMP算法

改進(jìn)算法不使用計算量巨大的最小二乘法求解,而是沿著負(fù)梯度方向搜索得到最優(yōu)解,該算法是OMP算法和最速下降法的完美結(jié)合。在本文中,我們采用縮短搜索步長的方法,不用在每次迭代過程中都追求目標(biāo)函數(shù)值,從而避免了搜索路徑呈鋸齒形。實驗結(jié)果表明,改進(jìn)的算法可以在一定程度上縮短信號重構(gòu)的耗時,提高重構(gòu)效率。

3.1算法步驟

用于信號稀疏重構(gòu)的改進(jìn)后的GP-OMP算法步驟可總結(jié)如下:

輸入:感知矩陣Φ,測量向量z,稀疏度K;

初始化:余量r°=z,重構(gòu)信號x°=0,索引集Γ°=φ,迭代次數(shù)n=0;

步驟1:計算余量和感知矩陣Φ的每一列的內(nèi)積gn=ΦTrn-1;

步驟7:更新余量rn=rn-1-ancn;

3.2仿真與結(jié)果分析

為了驗證GP-OMP算法的性能,本文基于windows下的MATLAB仿真環(huán)境實現(xiàn)了改進(jìn)的算法,并與原有的OMP算法做了性能比較。

仿真實驗采用一維信號,信號長度N=512,稀疏度K=10,觀測信號長度為80,并采用相同的感知矩陣。定義信號如下:x=0.3sin(100πt)+ 0.6sin(200πt)+0.1sin(400πt)+0.9sin(800πt);壓縮矩陣為高斯隨機采樣矩陣,采樣點數(shù)由公式M≥K*log(N/K)確定。

OMP算法與改進(jìn)的GP-OMP算法重構(gòu)結(jié)果的對比如表1所示。由表1可知,改進(jìn)后的GP-OMP算法的重構(gòu)時間較長,這是因為PSNR越高,信號重構(gòu)效果越好,所需重構(gòu)時間也就越長。改進(jìn)后的算法與原有的OMP算法相比,重構(gòu)質(zhì)量更好,并具有相似的重構(gòu)時間成本。

表1　OMP算法與改進(jìn)的GP-OMP算法重構(gòu)結(jié)果的對比

為了更充分地測試GP-OMP算法的實時性,對GP-OMP和OMP算法在不同稀疏度和不同信號長度下的耗時進(jìn)行了比較,結(jié)果分別如圖2和圖3所示。從圖2可以看出,信號稀疏度較低時,OMP算法耗時比GP-OMP算法高;隨著信號稀疏度的增大,兩種算法的耗時都增大,且耗時的差距越來越大。這是因為在決定重構(gòu)頻譜相位時,隨著稀疏度K的增大,在步驟流程中OMP算法的計算量越來越大。從圖3可以看出,隨著信號長度N的增大,兩種算法的耗時都有所增加,但GP-OMP算法的耗時遠(yuǎn)低于OMP算法。這是因為隨著N的增大,重構(gòu)矩陣和相對誤差的每一列長度也會相應(yīng)增加,導(dǎo)致重構(gòu)算法的耗時也相應(yīng)增加。

圖2　不同稀疏度下兩種算法耗時比較

圖3　不同信號長度下兩種算法耗時比較

4　結(jié)束語

對于稀疏或可壓縮的信號而言,壓縮感知作為一種新的信號采樣方法,比傳統(tǒng)的采樣方法更為有效。在壓縮感知理論中,采用最小二乘法優(yōu)化算法的信號重構(gòu)不再適用,而采用不同的凸優(yōu)化和貪婪算法對信號進(jìn)行重構(gòu)成為壓縮感知的研究重點。本文針對梯度法在搜索步長上的缺陷,引入了AS法,并通過實驗仿真驗證了該方案的可行性。仿真結(jié)果表明,改進(jìn)后的算法在不同程度上改善了信號的重構(gòu)耗時和重構(gòu)質(zhì)量,雖改進(jìn)不多,但是一種新的嘗試和探索。GP-OMP算法在前一感知時刻獲得信道信息,不僅大大減少了計算量,還能有效地減少耗時,達(dá)到與OMP算法基本一致的重構(gòu)效果,提高了壓縮感知的實效性。

參考文獻(xiàn):

[1] Tuuk P B,Marple S L.Compressed sensing radar amid noise and clutter using interference covariance information[J].IEEE Transactions on Aerospace& E-lectronic Systems,2014,50(2):887-897.

[2] Candès E,Romberg J,Tao T.Stable signal recovery fromincomplete and inaccurate measurements[J]. Comm Pure Appl Math,2006,59(8):1207-1223.

[3] Figueiredo M,Nowak R,Wright S.Gradient projection for sparsereconstruction:Application to compressed sensing and other inverseproblems[J].IEEE Journal of Selected Topics in Signal Processing,2007, 1(4):586-597.

[4] Tropp J,Gilbert A .Signal recovery from randommeasurementsvia orthogonal matching pursuit[J]. IEEE Trans Inform Theory,2008,53(12):4655-4666.

[5] Needell D,Vershynin R.Signal recovery from incomplete and inaccurate measurements via Regularized Orthogonal Matching Pursuit.Submitted for publication [J].Selected Topics in Signal Processing,2007,4 (2):310-316.

[6] Thong T Do,Lu Gan,Nam Nguyen,et al.Sparsity adaptive matching pursuit algorithm for practical compressed sensing[C]//Asilomar Conference on Signals, Systems,and Computers 2008.Pacific Grove,California:IEEE,2008:581-587.

[7] Blumensath T,Davies M E.Stagewise Weak Gradient Pursuits[J].IEEE Trans on Signal Processing,2009, 57(11):4333-4346.

[8] Aguilera E,Nannini M,Reigber A.A Data-Adaptive Compressed Sensing Approach to Polarimetric SAR Tomography of Forested Areas[J].Geoscience& Remote Sensing Letters IEEE,2013,10(3):543-547.

[9] Blumensath T,Davies M E.Gradient pursuits[J]. IEEE Trans on Signal Processing,2008,56(6): 2370-2382.

An Improved Reconstruction Algorithm for Compressed Sensing-Based OMP

WANG Juna,KONG Ling-bina,ZHAO Jieb
(a.School of Communication and Information Engineering;
b.School of Electronic Engineering,Xi’an University of Posts and Telecommunications,Xi’an 710121,China)

Abstract:In view of the emergence of mega data signals in wireless communication networks in recent years,this paper properly compresses these signals while performing signal sampling and realizes their reconstruction with small amount sampling value or observed value by using an appropriate reconstruction algorithm.On the basis of the original Orthogonal Matching Pursuit(OMP)-based compressed sensing reconstruction algorithm,the Alternating Step-size(AS)is introduced and an improved algorithm,i.e.GP-OMP algorithm proposed.Experimental results show that the spectrum information this algorithm obtained by using the previous sensing moment can not only effectively reduce the amount of computations by the reconstruction algorithm,but also the reconstruction time,with almostthe same results as those by using the original method.

Key words:reconstruction algorithm;compressed sensing;alternately step;spectrum sensing

中圖分類號:TN911.23

文獻(xiàn)標(biāo)志碼:A

文章編號:1005-8788(2016)01-0074-05

收稿日期:2015-06-29

作者簡介:王軍(1989-),男,甘肅平?jīng)鋈?。碩士研究生,主要研究方向為信號與信息處理。

doi:10.13756/j.gtxyj.2016.01.022