王軍,孔令斌,趙潔

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

?

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

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

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

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

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

0　引 言

近年來,一種新型的采樣理論——壓縮感知[1]在信號(hào)處理領(lǐng)域誕生。該理論的突出優(yōu)點(diǎn)是將傳統(tǒng)的數(shù)據(jù)壓縮與數(shù)據(jù)采集結(jié)合起來。重構(gòu)算法是信號(hào)處理領(lǐng)域和應(yīng)用數(shù)學(xué)中一個(gè)新的研究方向,是壓縮感知理論的一個(gè)關(guān)鍵部分,它涉及到壓縮信號(hào)的精確重構(gòu)和采樣過程中的準(zhǔn)確性驗(yàn)證。我們?cè)趯?shí)踐中使用了不同的優(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]算法是常用的一種信號(hào)重構(gòu)算法,但是當(dāng)信號(hào)長度很長時(shí),信號(hào)重構(gòu)過程耗時(shí)會(huì)更長,頻譜感測(cè)的實(shí)時(shí)性會(huì)受到影響。

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

1　壓縮感知理論

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

1.1壓縮感知的基本框架

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

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

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

圖1　壓縮感知理論框架

1.2壓縮感知采樣過程

1.2.1信號(hào)的稀疏性定義

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

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

1.2.2壓縮感知的線性測(cè)量過程

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

3.1算法步驟

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

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

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

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

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

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

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

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

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

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

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

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

圖3　不同信號(hào)長度下兩種算法耗時(shí)比較

4　結(jié)束語

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

參考文獻(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

中圖分類號(hào):TN911.23

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

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

收稿日期:2015-06-29

作者簡(jiǎn)介:王軍(1989-),男,甘肅平?jīng)鋈?。碩士研究生,主要研究方向?yàn)樾盘?hào)與信息處理。

doi:10.13756/j.gtxyj.2016.01.022