呂偉杰, 陳　霞, 劉紅珍

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

?

基于壓縮感知的自適應(yīng)匹配追蹤算法優(yōu)化

呂偉杰, 陳霞, 劉紅珍

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

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

關(guān)鍵詞：壓縮感知; 自適應(yīng); 匹配追蹤

0引言

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

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

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

1CS模型及描述

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

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

(1)

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

(2)

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

(3)

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

(4)

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

(5)

2MAMP算法

2.1SAMP算法

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

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

初始化：

r0=y(初始化殘余)

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

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

k=1(迭代次數(shù))

j=1(初始化段下標(biāo))

重復(fù)執(zhí)行：

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

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

if滿足停止條件

then退出此次迭代

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

j=j+1 (更新段標(biāo))

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

else

Fk=F(更新支撐集)

rk=r(更新殘余)

k=k+1

end

end

重復(fù)以上步驟直到滿足停止條件

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

2.2MAMP算法

2.2.1初步估計稀疏度

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

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

2.2.2迭代停止條件的優(yōu)化

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

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

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

2.2.3MAMP算法流程

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

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

初始化：

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

r0=y(初始化殘余)

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

k=1(迭代次數(shù))

重復(fù)執(zhí)行：

步驟 1

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

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

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

步驟 2

當(dāng)停止條件(‖r‖2

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

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

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

退出循環(huán);

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

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

else

Fk=F(更新支撐集)

rk=r(更新殘余)

k=k+1

end

end

重復(fù)以上步驟直到停止條件成立

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

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

3實(shí)驗(yàn)結(jié)果及分析

為比較本文算法與SAMP算法,實(shí)驗(yàn)采用Lena.bmp和Mondrian.bmp灰度位圖(像素256×256)。實(shí)驗(yàn)程序是在3.19GHz、3.47GB內(nèi)存、采用WindowsXP系統(tǒng)的計算機(jī)上運(yùn)行,在MATLABR2010b環(huán)境下進(jìn)行操作的。

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

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

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

在SAMP中,當(dāng)參數(shù)opt變化時,取采樣率為0.3,0.4, 0.5,對Lena圖進(jìn)行重構(gòu),得到的PSNR與MAMP重構(gòu)的圖像的PSNR的比較如圖1所示。

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

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

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

圖2　SAMP和MAMP算法的運(yùn)行時間比較

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

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

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

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

圖3　SAMP和MAMP算法對Lena和Mondrian圖的重構(gòu)比較

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

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

SAMP算法由于自適應(yīng)求得真實(shí)稀疏度,步長s和停止條件參數(shù)opt無法準(zhǔn)確得到最優(yōu)值,因此相對誤差較大于其他算法。而MAMP算法在重構(gòu)精度上則是最優(yōu)的,進(jìn)一步驗(yàn)證了MAMP算法優(yōu)于SAMP算法,是一種較好的重建算法。

4結(jié)論

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

參考文獻(xiàn)：

[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]. 電子學(xué)報,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.(甘偉,許錄平,羅楠.一種自適應(yīng)壓縮感知重構(gòu)算法[J]. 系統(tǒng)工程與電子技術(shù), 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. (田文飚,付爭,芮國勝.基于分治試探的盲自適應(yīng)匹配追蹤重構(gòu)算法[J].通信學(xué)報,2013, 34(4):180-186.)

呂偉杰(1975-),女,副教授,博士,主要研究方向?yàn)榫W(wǎng)絡(luò)控制系統(tǒng)、小波網(wǎng)絡(luò)、多模型控制理論、嵌入式系統(tǒng)、現(xiàn)場總線、壓縮感知。

E-mail:weijielv@tju.edu.cn

E-mail:chenxiaqufu@163.com

劉紅珍(1988-),女,碩士研究生,主要研究方向?yàn)閴嚎s感知及圖像處理。

E-mail:liuhongzhen_lhzh@163.com

網(wǎng)絡(luò)優(yōu)先出版地址：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-),,女,碩士研究生,主要研究方向?yàn)閴嚎s感知的重建算法。

作者簡介：

中圖分類號：TN 911.72

文獻(xiàn)標(biāo)志碼：ADOI:10.3969/j.issn.1001-506X.2015.05.35

收稿日期：2014-04-19；修回日期：2014-10-18；網(wǎng)絡(luò)優(yōu)先出版日期：2014-11-20。