【信息科學(xué)與控制工程】

基于子空間的正交匹配追蹤算法

李強(qiáng)云， 武昕偉

(陸軍軍官學(xué)院，合肥230031)

摘要：壓縮感知理論的提出，給信號(hào)處理和信息獲取領(lǐng)域帶來(lái)了劃時(shí)代的發(fā)展。傳統(tǒng)重構(gòu)壓縮算法大多都有迭代次數(shù)多、運(yùn)算效率不高且重構(gòu)效率低等問題。針對(duì)該問題，提出了一種根據(jù)子空間回溯思想重構(gòu)出原始信號(hào)，并證明了該算法的有效性和重要2個(gè)特點(diǎn)：引入回溯思想，重構(gòu)概率高；計(jì)算復(fù)雜度低。通過(guò)仿真實(shí)驗(yàn)與傳統(tǒng)的正交跟蹤(OMP)算法和子空間(SP)算法進(jìn)行相關(guān)參數(shù)比較，驗(yàn)證了該算法在稀疏信號(hào)重構(gòu)研究中具有重要意義。

關(guān)鍵詞：壓縮感知；子空間；OMP算法；SP算法

收稿日期：2014-12-05

作者簡(jiǎn)介：李強(qiáng)云,男，碩士研究生，主要從事雷達(dá)成像技術(shù)研究;武昕偉，男，碩士生導(dǎo)師，副教授，主要從事雷達(dá)成像技術(shù)和信號(hào)處理技術(shù)研究。

doi:10.11809/scbgxb2015.06.028

中圖分類號(hào)：TN911

文章編號(hào)：1006-0707(2015)06-0113-05

本文引用格式：李強(qiáng)云， 武昕偉.基于子空間的正交匹配追蹤算法[J].四川兵工學(xué)報(bào)，2015(6):113-116.

Citation format:LI Qiang-yun, WU Xin-wei.Research of Orthogonal Matching Pursuit Algorithm on the Base of Subspace[J].Journal of Sichuan Ordnance,2015(6):113-116.

Research of Orthogonal Matching Pursuit Algorithm

on the Base of Subspace

LI Qiang-yun, WU Xin-wei

(Academy of Army Officer of PLA, Hefei 230031, China)

Abstract:As the theory of compressed sensing was proposed, it had brought a landmark to the development of signal processing and obtaining information domains. Most traditional compressed reconstruction algorithms had some problems, such as the high iterations, low efficiency of operation and low recovery probability and so on. This paper had proposed backtracking idea to recovery original signal on the base of subspace, which also proved its availability and two important characteristics: firstly, high recovery probability because of drawing into backtracking idea, and secondly, the low computational complexity. This paper had compared parameters with traditional Orthogonal Matching Pursuit algorithm and Subspace Pursuit algorithm, and proved its significant importance in the sparse signal recovery domain.

Key words: compressed sensing; subspace; OMP algorithm; SP algorithm

壓縮感知(compressed sensing,CS)，又叫壓縮傳感，由Candes、Donho等[1,2]在2006年提出的，突破了傳統(tǒng)奈奎斯特采樣定理的限制，是一種全新信號(hào)處理和信息獲取理論。壓縮重構(gòu)算法是壓縮感知理論的關(guān)鍵部分，目前，比較成熟的算法有：BP(Basis Pursuit)算法、OMP(orthogonal matching pursuit)算法、GP(gradient pursuit)算法等等。大多數(shù)這些算法在每次迭代時(shí)沒有更新信號(hào)支撐集，若第一次找到的信號(hào)支撐集錯(cuò)誤或誤差較大，將導(dǎo)致信號(hào)重構(gòu)失敗，重構(gòu)概率低。本研究引入子空間回溯思想，在下一次迭代時(shí)，更新上一次找到的信號(hào)支撐集，最后直到殘差為零，通過(guò)偽逆運(yùn)算重構(gòu)出原始信號(hào)。

1壓縮感知理論

對(duì)于稀疏信號(hào)重構(gòu)問題，文獻(xiàn)[3,4]中提出了OMP算法和SP算法，下面予以簡(jiǎn)單介紹2種算法的主要步驟。

1.1OMP算法的主要步驟

1) Input parameters:Φ,y,K

2) Initialize:ro=y,Λ0=?，t=1

3) Find:λt=argmax|〈rt-1,φj〉|, (j=1,2,…,N)

Update support:Λt=Λt-1∪{λt}

Judge whethert>K, if satisfied then end,if not back to findλt

1.2SP算法的主要步驟

1) Input parameters:Φ,y,K

2) Initialize:T0={corresponding to the largest magnitude entries in the vectorΦ*y}

3) forl iteration，

Update:Tl=max(xp)

從以上2種算法主要步驟可以看出：① OMP算法在找到信號(hào)支撐集便不再更新，若找到的支撐集錯(cuò)誤或誤差較大將導(dǎo)致重構(gòu)效率低；② SP算法中沒有引入正交思想進(jìn)行處理，且對(duì)于稀疏度為K的信號(hào)，至少需要K次迭代才能重構(gòu)出原始信號(hào)，重構(gòu)效率不高。

2基于子空間的OMP算法描述

針對(duì)以上2種算法的缺點(diǎn)，本文引入文獻(xiàn)[3,4]中的子空間回溯思想，提出基于子空間的OMP算法，該算法在每次迭代時(shí)需要找到信號(hào)支撐集(值不為0的位置)的估計(jì)，在下一次迭代時(shí)修正上一次找到的信號(hào)支撐集，直到殘差小于指定的閾值時(shí)找到的信號(hào)支撐集，最后重構(gòu)出原信號(hào)。具體算法框圖如圖1所示。

圖1　OMP算法框圖

2.1算法步驟

基于子空間的OMP算法主要步驟如下：

1) Input parameters Phi,y,K.

2) Initializero=y,T0=?，l=1

3) forliteration，choose the bestIltorl-1

Il=argmax(mean(|ΦT[I]rl-1|))

ComputeTl=Tl-1∪Il

Judge whetherrl<δ, if satisfied then end,if notl=l+1

2.2復(fù)雜度分析

本研究算法的計(jì)算復(fù)雜度主要集中在相關(guān)最大化(Correlation Maximization，EM)運(yùn)算(上述步驟求Il)中，即測(cè)量矩陣與殘差之間的乘積。因此為確定該算法的復(fù)雜度，只需確定精確重構(gòu)需要的迭代次數(shù)。現(xiàn)對(duì)0-1二值無(wú)噪信號(hào)進(jìn)行本算法仿真實(shí)驗(yàn)，N=256，算法運(yùn)行100次，指定閾值δ=10-4，算法平均迭代次數(shù)與稀疏度K之間的關(guān)系如圖2所示。實(shí)驗(yàn)在Matlab R2010a環(huán)境下完成，CPU為G640，2.80 GHz，內(nèi)存為1.90 GB，后面仿真實(shí)驗(yàn)均在以上條件下進(jìn)行，不再重復(fù)說(shuō)明。

圖2　本文算法迭代次數(shù)與稀疏度 K關(guān)系對(duì)比

從圖2可以看出：本研究算法迭代次數(shù)與稀疏度K之間的關(guān)系近似表示為O(NlogK)(實(shí)際上是小于O(NlogK))。算法在每次迭代時(shí)需進(jìn)行CM運(yùn)算需要m*N次乘積，則本研究算法的復(fù)雜度可以控制在O(mNlogK)以內(nèi)。文獻(xiàn)[3,4]中已證明OMP算法、SP算法的運(yùn)算復(fù)雜度均在O(mNK)左右。所以在復(fù)雜度方面，算法運(yùn)算復(fù)雜度均低于上面2種算法，從理論分析上驗(yàn)證了本文算法運(yùn)算復(fù)雜度低特點(diǎn)。

2.3算法重構(gòu)源信號(hào)的充分條件

定理：若x為K稀疏的信號(hào)，則本文算法能夠重構(gòu)信號(hào)x的充分條件為

(1)

(2)

式中：ρ為矩陣Φ的譜半徑；Φ[l,r]為矩陣Φ中第(l,r)個(gè)元素。在證明本定理之前，先給出以下必要的定義及引理。

定義：向量x的混合l2/lp范數(shù)

(3)

若對(duì)于矩陣Φ，Φ∈Rm×N，矩陣Φ的混合范數(shù)為

(4)

引理：若矩陣Φ為m×N大小，Φ[l,r]為矩陣Φ中第(l,r)個(gè)元素，則有下式成立[5]：

(5)

(6)

特別地，ρr(Φ)=ρc(ΦT)。

定理的證明：根據(jù)前面已經(jīng)介紹的內(nèi)容可以看出，該算法的重點(diǎn)是找到正確的信號(hào)支撐集，然后通過(guò)偽逆運(yùn)算重構(gòu)源信號(hào)x，所以若算法能重構(gòu)x，則與2.1節(jié)中第3步驟中最大相關(guān)處理時(shí)等價(jià)，即每次迭代時(shí)都能找到部分正確的信號(hào)支撐集，如式(7)所示

(7)

圖3　殘差 r l與兩空間距離對(duì)比

由于

(8)

則有

(9)

根據(jù)引理的式(5)有

(10)

(11)

最終可得

(12)

以上便完成了對(duì)定理的證明，在此還有2點(diǎn)補(bǔ)充說(shuō)明：

1) 在實(shí)際的數(shù)據(jù)傳輸過(guò)程中，若原始信號(hào)x的部分先驗(yàn)條件已知，如支撐集位置等，可以通過(guò)計(jì)算驗(yàn)證測(cè)量矩陣Φ是否滿足本研究算法的充分條件。

(13)

2.4重構(gòu)概率分析

本研究算法在OMP算法的基礎(chǔ)上利用子空間的回溯思想，即在每次進(jìn)行第l+1迭代時(shí)，都要更新第l次迭代信號(hào)支撐集的估計(jì)值，而OMP算法找到信號(hào)支撐集后便不再更新，若找到的支撐集誤差較大或錯(cuò)誤將導(dǎo)致重構(gòu)信號(hào)失敗[8-10]；相比SP算法，又利用了OMP正交的優(yōu)點(diǎn)，可以很好地重構(gòu)出原始信號(hào)，綜上所述可看出該算法較其他2種算法均有一定的改進(jìn)，重構(gòu)概率也相應(yīng)得到提高[11-13]。

3仿真實(shí)驗(yàn)及分析

為通過(guò)仿真實(shí)驗(yàn)驗(yàn)證該算法可以有效提高重構(gòu)概率和減少運(yùn)算復(fù)雜度，首先對(duì)0-1的二值信號(hào)進(jìn)行仿真實(shí)驗(yàn)，并與傳統(tǒng)的OMP算法和SP算法進(jìn)行性能對(duì)比。原始信號(hào)為隨機(jī)產(chǎn)生的0-1二值無(wú)噪信號(hào)，N=256，源信號(hào)稀疏度K=20，對(duì)每種算法運(yùn)行100次，指定閾值δ=10-4，測(cè)量矩陣均采用隨機(jī)高斯矩陣[6]。當(dāng)測(cè)量值M=128時(shí)，算法運(yùn)行結(jié)果如圖4所示，當(dāng)測(cè)量值M變化時(shí)，算法重構(gòu)概率與測(cè)量值M關(guān)系如圖5所示，左邊為無(wú)噪情況下的結(jié)果，右邊為有噪聲情況下的結(jié)果，其均值為零，偏方差為0.01的高斯信號(hào)。

圖2和圖4的結(jié)果驗(yàn)證了該算法可以實(shí)現(xiàn)0-1稀疏信號(hào)的重構(gòu)，并且重構(gòu)概率非常高，與傳統(tǒng)OMP算法和SP算法相比，不論有無(wú)噪聲，其重構(gòu)概率結(jié)果都比前兩者要好。當(dāng)以上算法重構(gòu)概率大于0.95時(shí)，算法運(yùn)行時(shí)間和測(cè)量誤差結(jié)果如表1所示。

表1　算法運(yùn)行時(shí)間、測(cè)量誤差與測(cè)量值M的關(guān)系

圖4　M=128時(shí)0-1信號(hào)算法運(yùn)行結(jié)果

圖5　0-1信號(hào)仿真結(jié)果對(duì)比

表1可以看出：本算法與OMP算法、SP算法相比，在測(cè)量值M相同情況下，算法運(yùn)行時(shí)間和測(cè)量誤差均小于后兩者測(cè)量值，可見該算法在OMP算法引入回溯思想、在SP算法上利用正交的思想可以有效減少在尋找信號(hào)支撐集錯(cuò)誤的概率，從而提高信號(hào)重構(gòu)概率，驗(yàn)證了該算法優(yōu)于OMP算法和SP算法。

4結(jié)束語(yǔ)

提出了在子空間回溯思想的基礎(chǔ)上運(yùn)用OMP信號(hào)重構(gòu)算法，在下一次迭代時(shí)，更新上一次找到的信號(hào)支撐集，最后直到殘差小于指定閾值，通過(guò)偽逆運(yùn)算重構(gòu)出原始信號(hào)。也證明了該算法重構(gòu)信號(hào)的充分條件，說(shuō)明了該算法的普遍性。通過(guò)理論和實(shí)驗(yàn)分析了本算法運(yùn)算復(fù)雜度可以控制在O(mNlogK)以內(nèi)。通過(guò)將0-1信號(hào)在無(wú)噪、有噪情況下分別進(jìn)行仿真和二維lena圖像信號(hào)仿真實(shí)驗(yàn)，驗(yàn)證了本算法的有效性，可以很好地降低信號(hào)重構(gòu)時(shí)間、減少誤差和提高信號(hào)重構(gòu)概率，對(duì)于信號(hào)處理有深遠(yuǎn)意義。

參考文獻(xiàn)：

[1]DonohoD.Compressedsensing[J].IEEETrans.Inf.Theory,2006,52(4):1289-1306.

[2]CandèsE,RombergJ,TaoT.Robustuncertaintyprinciples:Exactsignalreconstructionfromhighlyincompletefrequencyinformation[J].IEEETrans.Inf.Theory,2006,52(2):489-509.

[3]TroppJA，GilbertAC.Signalrecoveryfromrandommeasurementsviaorthogonalmatchingpursuit[J].IEEETrans.Inf.Theory,2007,53(12):4655-4666.

[4]DaiW,MilenkovicO.Subspacepursuitforcompressivesensingsignalreconstruction[J].IEEETransonInformationTheory,2009,55(5):2230-2249.

[5]BarniukRG,CevherV,DuarteMF,etal.Model-basedcompressivesensing[J].IEEETransonInformationTheory,2010,56(4):1982-2001.

[6]RudelsonM,VershyninR.OnsparsereconstructionfromFourierandGaussianmeasurements[J].Commun.PureAppl.Math.,2008,61(8):1025-1045.

[7]石光明,劉丹華,高大華,等.壓縮感知理論及研究發(fā)展[J].電子學(xué)報(bào)，2009,37(5):1070-1081.

[8]付寧,曹離然,鵬喜元.基于子空間的塊稀疏信號(hào)壓縮感知重構(gòu)算法[J].電子學(xué)報(bào),2011,39(11):2338-2342.

[9]EldarYC,KuppingerP,BolcskeiH.Compressedsensingofblock-sparsesignals:uncertaintyrelationsandefficientrecovery[J].IEEETransonSignalProcessing,2010,58(6):3042-3054.

[10]KezhiLi,LuGan,CongLing.ConvolutionalCompressedSensingUsingDeterministicSequences[J].IEEETransonSignalProcessing,2013,61(3):740-752.

[11]WenbiaoTian,GuoshengRui.BlindSparsityWeakSubspacePursuitforCompressedSensing[J].TheInstitutionofEngineeringandTechnology,2013,49(6):369 - 370.

[12]HansenTL,JohansenDH,JorgensenPB,etal.CompressedSensingwithRankDeficientDictionaries[J].Globecom2012SignalProcessingforCommunicationsSympium,2012:3594-3599.

[13]AmbatSK,SaikatChatterjee,HariKVS.FurionofAlgorithemforCompressedSensing[J].IEEETransonSignalProcessing,2013,61(14):3699-3704.

(責(zé)任編輯楊繼森)