基于壓縮感知的自適應匹配追蹤算法優化

呂偉杰, 陳　霞, 劉紅珍

(天津大學電氣與自動化工程學院, 天津 300072)

?

基于壓縮感知的自適應匹配追蹤算法優化

呂偉杰, 陳霞, 劉紅珍

(天津大學電氣與自動化工程學院, 天津 300072)

摘要：針對基于壓縮感知的稀疏自適應匹配追蹤(sparsity adaptive matching pursuit, SAMP)算法運行效率低的問題,給出了一種優化的自適應匹配追蹤(modified adaptive matching pursuit, MAMP)算法。該算法在支撐集選擇過程中對稀疏度進行了初步估計,并優化了迭代停止的條件。實驗表明,該算法相比于SAMP有更快的收斂速度,并且實現更優的重建效果。

關鍵詞：壓縮感知; 自適應; 匹配追蹤

0引言

壓縮感知(compressive sensing, CS)[1-4],自提出以來,在應用數學、計算機科學和電子工程等各個領域已得到了廣泛應用。CS理論涉及3個關鍵問題[5]：稀疏表示、壓縮觀測和優化重構。重構算法影響CS理論的實用性,因此是其中較為關鍵的部分。

在重構算法中,貪婪迭代算法的應用最為廣泛,這類算法主要包括正交匹配追蹤[6]、分段正交匹配追蹤(orthogonal matching pursuit, OMP)[7]、規范正交匹配追蹤[8]、子空間追蹤(subspace pursuit, SP)[9]、壓縮采樣匹配追蹤(compressed sampling matching pursuit, CoSaMP)[10]以及迭代硬閾值法[11]等。這些算法都需要預估稀疏度,為解決這一問題,稀疏自適應匹配追蹤[12](sparsity adaptive matching pursuit, SAMP)算法被提了出來。

SAMP依據步長信息逐步擴充支撐集,自適應地完成信號重構。選取的步長越小,重構的精度越高,但同時也會導致重構過程更加繁瑣。為此,本文提出了一種優化的自適應匹配追蹤(modified adaptive matching pursuit, MAMP)算法,在支撐集選擇過程中對稀疏度進行了初步估計,并優化了迭代停止的條件,如此在信號處理過程中,縮短了運行時間,同時又能更精確地重構目標信號。

1CS模型及描述

在CS理論模型中,首先將信號進行稀疏表示,得到稀疏系數,再將其投影到一個合適的觀測矩陣上來得到觀測向量,并利用觀測向量重構原始信號。

CS可描述為：如果離散信號x(N×1),投影到基Ψ=[Ψ1,Ψ2,…,ΨN]上后可表示為

(1)

式中,s為N×1的系數向量,且有K(K?N)個系數非零,其余系數均為0或非常接近于0; Ψ是N×N的稀疏矩陣。那么,就能使用一個與Ψ不相關的觀測矩陣Φ對原信號進行觀測,得到觀測向量y(M×1)：

(2)

將式(1)與式(2)結合,得

(3)

因觀測維數M遠小于信號維數N,所以重構面臨求解欠定方程組的問題。如果信號x是稀疏的或者可壓縮的,則可以轉化為最小l0范數問題來求解：

(4)

求解式(4)所描述的優化方程中的最小l0范數優化問題,是一個NP-hard問題,數值計算結果復雜度高,而且極不穩定。文獻[13]指出,可通過求解一個更簡單的l1范數優化問題來得到同樣的解：

(5)

2MAMP算法

2.1SAMP算法

SAMP算法[14],引入步長信息,分段進行,逐步擴充支撐集。在每一段中,都經過預選、候選及剪裁3步,如果殘余范數大于上次迭代殘余范數,則增大支撐集的大小;否則繼續搜索更優支撐集。如此循環,當達到停止迭代條件時,退出循環,此時便得到與目標信號最匹配的原子構成的支撐集。流程如下：

輸入： 觀測矩陣Φ、觀測向量y和步長s

初始化：

r0=y(初始化殘余)

F0=[](初始化支撐集)

I=s(初始階段支撐集的大小)

k=1(迭代次數)

j=1(初始化段下標)

重復執行：

Sk=Max(|Φ*rk-1|,I)(預選集)

Ck=Fk-1∪Sk(候選集)

if滿足停止條件

then退出此次迭代

else if ‖r‖2≥‖rk-1‖2(更新支撐集大小)

j=j+1 (更新段標)

I=j×s(更新支撐集的大小)

else

Fk=F(更新支撐集)

rk=r(更新殘余)

k=k+1

end

end

重復以上步驟直到滿足停止條件

其中,I=|Fk|是支撐集Fk的大小;對于矩陣a,函數Max(a,I)返回a中絕對值最大的前I個下標構成的下標集。對于集合Λ∈{1,…,N},ΦΛ是矩陣Φ中位于下標集Λ中的子矩陣。在第k次迭代中,Sk,Ck,Fk,rk分別代表預選集,候選集,最終支撐集和觀測余量。

2.2MAMP算法

2.2.1初步估計稀疏度

SAMP算法根據步長信息逐步擴充支撐集,而步長s的選擇是一個重構精度與重構速度難以同時滿足的難題：如果選得較小,逐步增大支撐集大小會消耗大量的運算時間;如果選得較大,則無法準確逼近真實稀疏度,使得信號重構精度降低。

針對以上問題,MAMP利用文獻[15]中提出的稀疏度估計過量判據。

2.2.2迭代停止條件的優化

SAMP算法中,在每一階段,當搜索的支撐集原子更匹配原信號時,殘余范數‖rk‖2減小,同時更新支撐集及殘余。在不滿足停止條件情況下,當殘余范數增大時,進行段變換,同時增大支撐集的大小。如此,便增大了對停止條件‖r‖2≤opt×‖y‖2的依賴：對opt的選擇,如果較大,則影響重構精度;反之則會一直增大支撐集的大小。當支撐集的大小增加到遠大于真實稀疏度時,則會向支撐集引入大量錯誤原子,反而又降低了重構精度。因此,選擇合適的停止條件顯得尤為重要。

對于SAMP算法中opt的選擇,往往是固定的,如通常假定opt=0.001以期得到更優的重建效果,但是,由于原始信號及稀疏矩陣的不同,往往將支撐集擴充到接近觀測值也不能滿足‖r‖2≤opt×‖y‖2,反而引入了更多的錯誤原子,因此,也就達不到自適應得到稀疏度的目的。

MAMP算法中,先對稀疏度進行初步估計,得到稀疏度的較小逼近,此時的稀疏度已經比較接近真實稀疏度,搜索到的支撐集也比較接近真實支撐集。在此基礎上,繼續搜索支撐集時,如果新的支撐集更準確,會降低‖r‖2;當‖r‖2后一次與前一次相等時,則說明對于當前支撐集的大小,已經搜索到了相對最優的支撐集,因此增大支撐集的大小,進一步降低‖r‖2;而當‖r‖2后一次大于前一次時,則說明在當前支撐集的大小不變時,已經引入了錯誤原子,則認為此時得到的支撐集便是最優支撐集,退出循環。前一階段初步得到稀疏度的較小估計,后一階段則逐一增加支撐集大小,精確逼近稀疏度,并得到相對最優的支撐集,解決了由于opt的選擇不當,使支撐集被擴充至遠大于真實稀疏度的問題。

2.2.3MAMP算法流程

以下是MAMP算法的具體流程：

輸入： 觀測矩陣Φ、觀測向量y、測量值個數M

初始化：

I=M(初始化支撐集大小)

r0=y(初始化殘余)

F0=[](初始化支撐集)

k=1(迭代次數)

重復執行：

步驟 1

I=I/2(初步估計稀疏度)

Sk=Max(|Φ*rk-1|,I)(預選集)

Ck=Fk-1∪Sk(候選集)

步驟 2

當停止條件(‖r‖2

Sk=Max(|Φ*rk-1|,I)(預選集)

Ck=Fk-1∪Sk(候選集)

if ‖r‖2>‖rk-1‖2

退出循環;

else if ‖r‖2=‖rk-1‖2

I=I+1(增加支撐集大小)

else

Fk=F(更新支撐集)

rk=r(更新殘余)

k=k+1

end

end

重復以上步驟直到停止條件成立

步驟1初步完成了對稀疏度的過小估計,步驟2中,根據殘余范數‖r‖2的變化情況來決定是否退出循環、或增大支撐集大小、或繼續更新支撐集。

對于迭代停止條件的優化,避免了由于opt選擇的不當,盲目地擴充支撐集的大小。MAMP算法中,沒有完全依賴停止參數opt的選擇,而是根據具體信號自適應地得到最優支撐集,從而大大提高了重構精度。同時,第一階段的快速逼近稀疏度,也為真實稀疏度的尋找節省了大量時間。

3實驗結果及分析

為比較本文算法與SAMP算法,實驗采用Lena.bmp和Mondrian.bmp灰度位圖(像素256×256)。實驗程序是在3.19GHz、3.47GB內存、采用WindowsXP系統的計算機上運行,在MATLABR2010b環境下進行操作的。

實驗中,均以列為單位進行處理,采用離散小波變換作為正交基,生成M×N維的隨機矩陣作為測量矩陣,其中,M為觀測矩陣y的維數,N為原始信號x的維數,M/N稱為壓縮比,壓縮比越小,則重構過程中使用的觀測數目越少。

實驗的性能指標分別采用運算時間、峰值信噪比(peak signal to noise ratio, PSNR)和重構誤差err。其中,運行時間為逐列采用重構算法直至整幅圖像重構完成所需的時間,由tic oc函數完成;PSNR和重構誤差err由以下2式給出：

PSNR是評鑒畫質所廣泛使用的客觀量測法,衡量處理后的影像品質;重構誤差是重構后圖像與原始圖像差值同原始圖像之間的比值,同樣是衡量圖像處理的一個重要指標。PSNR越高,err越小,重構質量越好。

在SAMP中,當參數opt變化時,取采樣率為0.3,0.4, 0.5,對Lena圖進行重構,得到的PSNR與MAMP重構的圖像的PSNR的比較如圖1所示。

從圖中可以看出,并不是停止條件參數opt選得越小,得到的重構圖像就越精確,其最優值的選取,依不同問題而定。從本次實驗可以看出,當opt選得較小時,重構效果較差;對于Lena圖,當opt選在0.10～0.15區域內時,可達到相對最優的重建效果;而當大于該最優值時,重建PSNR會大幅降低。同時,實驗中又附加了MAMP算法在相應采樣率下的重構PSNR,解決了對opt的最優選取問題,同時,PSNR明顯高于SAMP算法。

算法運行時間則隨采樣率的增大而增加, 圖2展示了對于Lena圖,在不同采樣率下,分別利用SAMP和MAMP算法進行重構所需的運行時間的比較,可看出,MAMP算法在運行時間方面明顯優于SAMP。

圖1　SAMP算法和MAMP算法的PSNR比較

圖2　SAMP和MAMP算法的運行時間比較

表1則記錄了對于Mondrian圖在不同采樣率下,當SAMP取得最優重建PSNR時的時間t和PSNR與MAMP算法重建所需時間t和PSNR的比較。

表1　SAMP和MAMP算法對Mondrian圖重建的t和PSNR比較

對于Mondrian圖,當采樣率增大時,重建所需時間增加,PSNR也提高,但是MAMP算法運行時間明顯小于SAMP,且重建效果也有所提高。

當固定采樣率,如取M/N=0.4時,利用SAMP和MAMP算法,采用相同的正交基和測量矩陣,分別進行壓縮及重構,重建效果如圖3所示。

圖3　SAMP和MAMP算法對Lena和Mondrian圖的重構比較

取采樣率M/N=0.4,對Lena圖進行重構,以相對誤差err作為重構精度的參考,各個算法的重構精度如表2所示。

表2　不同算法對Lena圖的重構精度(相對誤差)

SAMP算法由于自適應求得真實稀疏度,步長s和停止條件參數opt無法準確得到最優值,因此相對誤差較大于其他算法。而MAMP算法在重構精度上則是最優的,進一步驗證了MAMP算法優于SAMP算法,是一種較好的重建算法。

4結論

本文算法對SAMP算法中的稀疏度的初步估計和迭代停止的條件優化2方面進行了討論。在初步估計稀疏度時,先對半減小,后逐一增加,前一階段大幅提高了搜索速度;后一階段則保證了重構精度。對于迭代停止時的條件,不再單純依賴停止條件中參數opt的選擇,而是根據當前所選支撐集的具體情況來確定是否增加支撐集大小、或搜索更精確支撐集、或停止搜索,完成了支撐集的自適應搜索及停止。實驗表明,該算法相比SAMP有更快的收斂速度,并且重建效果更優。因此,本文算法是一種較好的自適應匹配追蹤重構算法。

參考文獻：

[1] Donoho D L. Compressed sensing[J].IEEETrans.onInformationTheory, 2006, 52(4):1289-1306.

[2] Kutyniok G. Theory and applications of com-pressed sensing[J].GAMM-Mitteilungen, 2013, 36(1):79-101.

[3] Qaisar S, Bilal R M, Iqbal W, et al. Compres-sive sensing:from theory to applications, a survey[J].JournalofCommunicationsandNetworks, 2013, 15(5):443-456.

[4] Kutyniok G.Compressedsensing:theoryandapplications[M]. New York:Cambridge Uni-versity Press, 2012.

[5] Jiao L C, Yang S Y, Liu F, et al. Development and prospect of compressive sensing[J].Chi-neseJournalofElectronics, 2011, 39(7):1651-1662.(焦李成,楊淑媛,劉芳,等.壓縮感知回顧與展望[J]. 電子學報,2011,39(7):1651-1662.)

[6] Tropp J A, Gilbert A C. Signal recovery from random measurements via orthogonal match-ing pursuit[J].IEEETrans.onInformationTheory, 2007, 53(12):4655-4666.

[7] Donoho D L, Tsaig Y, Drori I, et al. Sparse s-olution of underdetermined systems of linear equations by stagewise orthogonal matching pursuit[J].IEEETrans.onInformationTheory, 2012, 58(2):1094-1121.

[8] Zhao Q, Wang J K, Han Y H, et al. Compres-sive sensing of block-sparse signals recov-ery based on sparsity adaptive regularized orthogonal matching pursuit algorithm[C]∥Proc.oftheIEEEfifthInternationalConferenceonAdvancedComputationalIntelligence,2012:1141-1144.

[9] Dai W, Milenkovic O. Subspace pursuit for compressive sensing signal reconstruction[J].IEEETrans.onInformationTheory, 2009, 55(5):2230-2249.

[10] Needell D and Tropp J A. CoSaMP:Iterative signal recovery from incomplete and inaccu-rate samples[J].AppliedandComputationalHarmonicAnalysis, 2009, 26(3):301-321.

[11] Li J, Shen Y, Wang Q. Stepwise suboptimal iterative hard thresholding algorithm for compressive Sensing[C]∥Proc.oftheInstrumentationandMeasurementTechnologyConference, 2012:1332-1336.

[12] Do T T, Gan L, Nguyen N, et al. Sparsity ad-aptive matching pursuit algorithm for practi-cal compressed sensing[C]∥Proc.ofthe42ndAsilmatConferenceonSignals,Systems,andComputers, 2008.

[13] Chen S S, Donoho D L, Saunders M A. Atomic decomposition by basis pursuit[J].SLAMJournalonScientificComputing, 2006, 20(1):33-61.

[14] Gan W, Xu L P, Luo N. Adaptive recovery algorithm for compressive sensing[J].SystemsEngineeringandElectronics, 2011,33 (9):1948-1953.(甘偉,許錄平,羅楠.一種自適應壓縮感知重構算法[J]. 系統工程與電子技術, 2011, 33(9):1948-1953.)

[15] Tian W B, Fu Z, Rui G S. Blind adaptive ma-tching pursuit algorithm for signal reconstru-ction based on sparsity trial and error[J].Journalonommunications, 2013,34 (4):180-186. (田文飚,付爭,芮國勝.基于分治試探的盲自適應匹配追蹤重構算法[J].通信學報,2013, 34(4):180-186.)

呂偉杰(1975-),女,副教授,博士,主要研究方向為網絡控制系統、小波網絡、多模型控制理論、嵌入式系統、現場總線、壓縮感知。

E-mail:weijielv@tju.edu.cn

E-mail:chenxiaqufu@163.com

劉紅珍(1988-),女,碩士研究生,主要研究方向為壓縮感知及圖像處理。

E-mail:liuhongzhen_lhzh@163.com

網絡優先出版地址：http://www.cnki.net/kcms/detail/11.2422.TN.20141120.1831.002.html

Modified adaptive matching pursuit algorithm based on compressive sensing

Lü Wei-jie, CHEN Xia, LIU Hong-zhen

(SchoolofElectricalandAutomation,TianjinUniversity,Tianjin300072,China)

Abstract:To improve the operating efficiency of sparsity adaptive matching pursuit (SAMP), a modified adaptive matching pursuit algorithm (MAMP) is presented. The new algorithm estimates the value of sparsity preliminarily in the process of the choice of the support list, meanwhile, it corrects the condition when the circulation stops. The experiments demonstrate that the new algorithm saves much more operating time than SAMP, and improves the performance of the recovery.

Keywords:compressive sensing(CS); adaptive; matching pursuit

通訊作者陳霞(1989-),,女,碩士研究生,主要研究方向為壓縮感知的重建算法。

作者簡介：

中圖分類號：TN 911.72

文獻標志碼：ADOI:10.3969/j.issn.1001-506X.2015.05.35

收稿日期：2014-04-19；修回日期：2014-10-18；網絡優先出版日期：2014-11-20。