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

【信息科學與控制工程】

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

李強云， 武昕偉

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

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

關鍵詞：壓縮感知；子空間；OMP算法；SP算法

收稿日期：2014-12-05

作者簡介：李強云,男，碩士研究生，主要從事雷達成像技術研究;武昕偉，男，碩士生導師，副教授，主要從事雷達成像技術和信號處理技術研究。

doi:10.11809/scbgxb2015.06.028

中圖分類號：TN911

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

本文引用格式：李強云， 武昕偉.基于子空間的正交匹配追蹤算法[J].四川兵工學報，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年提出的，突破了傳統奈奎斯特采樣定理的限制，是一種全新信號處理和信息獲取理論。壓縮重構算法是壓縮感知理論的關鍵部分，目前，比較成熟的算法有：BP(Basis Pursuit)算法、OMP(orthogonal matching pursuit)算法、GP(gradient pursuit)算法等等。大多數這些算法在每次迭代時沒有更新信號支撐集，若第一次找到的信號支撐集錯誤或誤差較大，將導致信號重構失敗，重構概率低。本研究引入子空間回溯思想，在下一次迭代時，更新上一次找到的信號支撐集，最后直到殘差為零，通過偽逆運算重構出原始信號。

1壓縮感知理論

對于稀疏信號重構問題，文獻[3,4]中提出了OMP算法和SP算法，下面予以簡單介紹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算法在找到信號支撐集便不再更新，若找到的支撐集錯誤或誤差較大將導致重構效率低；② SP算法中沒有引入正交思想進行處理，且對于稀疏度為K的信號，至少需要K次迭代才能重構出原始信號，重構效率不高。

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

針對以上2種算法的缺點，本文引入文獻[3,4]中的子空間回溯思想，提出基于子空間的OMP算法，該算法在每次迭代時需要找到信號支撐集(值不為0的位置)的估計，在下一次迭代時修正上一次找到的信號支撐集，直到殘差小于指定的閾值時找到的信號支撐集，最后重構出原信號。具體算法框圖如圖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復雜度分析

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

圖2　本文算法迭代次數與稀疏度 K關系對比

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

2.3算法重構源信號的充分條件

定理：若x為K稀疏的信號，則本文算法能夠重構信號x的充分條件為

(1)

(2)

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

定義：向量x的混合l2/lp范數

(3)

若對于矩陣Φ，Φ∈Rm×N，矩陣Φ的混合范數為

(4)

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

(5)

(6)

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

定理的證明：根據前面已經介紹的內容可以看出，該算法的重點是找到正確的信號支撐集，然后通過偽逆運算重構源信號x，所以若算法能重構x，則與2.1節中第3步驟中最大相關處理時等價，即每次迭代時都能找到部分正確的信號支撐集，如式(7)所示

(7)

圖3　殘差 r l與兩空間距離對比

由于

(8)

則有

(9)

根據引理的式(5)有

(10)

(11)

最終可得

(12)

以上便完成了對定理的證明，在此還有2點補充說明：

1) 在實際的數據傳輸過程中，若原始信號x的部分先驗條件已知，如支撐集位置等，可以通過計算驗證測量矩陣Φ是否滿足本研究算法的充分條件。

(13)

2.4重構概率分析

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

3仿真實驗及分析

為通過仿真實驗驗證該算法可以有效提高重構概率和減少運算復雜度，首先對0-1的二值信號進行仿真實驗，并與傳統的OMP算法和SP算法進行性能對比。原始信號為隨機產生的0-1二值無噪信號，N=256，源信號稀疏度K=20，對每種算法運行100次，指定閾值δ=10-4，測量矩陣均采用隨機高斯矩陣[6]。當測量值M=128時，算法運行結果如圖4所示，當測量值M變化時，算法重構概率與測量值M關系如圖5所示，左邊為無噪情況下的結果，右邊為有噪聲情況下的結果，其均值為零，偏方差為0.01的高斯信號。

圖2和圖4的結果驗證了該算法可以實現0-1稀疏信號的重構，并且重構概率非常高，與傳統OMP算法和SP算法相比，不論有無噪聲，其重構概率結果都比前兩者要好。當以上算法重構概率大于0.95時，算法運行時間和測量誤差結果如表1所示。

表1　算法運行時間、測量誤差與測量值M的關系

圖4　M=128時0-1信號算法運行結果

圖5　0-1信號仿真結果對比

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

4結束語

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

參考文獻：

[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]石光明,劉丹華,高大華,等.壓縮感知理論及研究發展[J].電子學報，2009,37(5):1070-1081.

[8]付寧,曹離然,鵬喜元.基于子空間的塊稀疏信號壓縮感知重構算法[J].電子學報,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.

(責任編輯楊繼森)