步長自適應的前向后向匹配追蹤算法

張松江 周 密 張傳林

(暨南大學信息科學技術學院 廣東 廣州 510000)

?

步長自適應的前向后向匹配追蹤算法

張松江 周 密 張傳林

(暨南大學信息科學技術學院 廣東 廣州 510000)

稀疏度自適應的匹配追蹤算法(SAMP)是基于壓縮感知理論的信號重建經典算法。針對稀疏度未知的信號重建，提出步長自適應的前向后向匹配追蹤(AFBMP)算法，AFBMP算法在稀疏度自適應匹配追蹤算法的框架下，前向搜索過程中采用對數型自適應變化的步長選擇匹配原子，然后通過后向策略修正前向階段造成的錯誤，刪除支撐集中的部分錯誤原子，最終實現信號的精確逼近。實驗表明AFBMP算法比SAMP算法能夠更加高效地重建稀疏度未知的信號。

壓縮感知 重構 前向后向 稀疏度自適應 匹配追蹤算法

0 引 言

隨著科學技術的飛速發展，在信號的采樣和處理過程中，利用信號的帶寬來表示信號已不能滿足現實的需要，因為隨著信號攜帶的信息量逐漸增加，采樣速度和處理速度就會變得越來越慢，同時這些數據的存儲問題也是不容忽視的。雖然人們采用一種壓縮的方式來表示信號，但是這種方式會導致大量的信息資源被拋棄，所以采用帶寬來表示信號的信息是不合理的。而信號的稀疏性是近幾年信號處理領域的新寵，它可以更加本質地表示信號，因此基于信號的稀疏性提出的壓縮感知理論得到了廣泛的認可。

壓縮感知理論(CS)[1,2]作為一種全新的采樣理論，利用隨機采樣獲取信號的離散樣本，然后通過非線性重建算法對信號進行重建。該理論指出：如果信號在某個變換域上是稀疏的或者認為是可以壓縮的，那就可以通過一個新的觀測矩陣將高維的信號映射到一個低維空間中，這樣就可以將問題轉化為最優化問題，進而重構出原始信號。該理論通過稀疏性以及等距約束準則來完成高速率的采樣，又包含了大量的重要信息。壓縮感知理論因為可以同時完成數據的采集和壓縮，大大節約了時間和資源，所以得到了廣泛的應用。

雖然壓縮感知理論可以大大降低采樣和計算的成本，但是如何設計出一種快速的魯棒的重建算法是該理論的核心問題。隨著對CS理論研究的不斷深入，為了通過低維數據來實現對原始信號的重構，近年來越來越多的重構算法被提出。目前貪婪迭代算法是學者們研究最多的算法，這種算法重構精度高、計算量小并且易于實現。比如Mallat等人采用正交策略提出了正交匹配追蹤算法(OMP)[4,5]、Needell又在正交匹配追蹤算法放入基礎上加入正則化思想，提出正則化正交匹配追蹤算法(ROMP)[6]、Tropp根據隨機測量矩陣思提出了壓縮采樣匹配追蹤算法(CoSaMP)[7]、Dai借鑒回溯序貫編碼理論，提出了子空間追蹤算法(SP)[8]以及Donoho等人考慮稀疏度未知的情況，打破傳統局限，提出了一種稀疏度自適應的匹配追蹤算法(SAMP)[9,10]。貪婪迭代算法因其重建速度快和精度高而得到廣泛應用，然而大部分貪婪算法都是通過已知稀疏度來控制算法重建的迭代次數，而在實際問題中，稀疏度不一定是已知的，并且當稀疏度固定時也可能會對重構精度造成影響。

SAMP算法突破了傳統的匹配算法要以稀疏度已知為前提的限制，解決了在稀疏度未知的條件下的重建問題。SAMP算法的重建速度主要取決于固定步長的選擇，雖然在重構精度上有了一定的提高，但是依然不能得到滿意的效果。另外根據該算法的迭代機制，每次迭代過程中都會增加支撐集中的原子個數，這樣就會有越來越多的原子被加入到支撐集中，而又無法刪除支撐集中部分錯誤原子，所以該算法有一定的局限性。為了解決這一問題，有學者提出了MSAMP算法[11]，該算法在SAMP算法的框架下通過原子匹配估計稀疏度，然后利用階段步長來實現對原始信號的估計，但這種算法在同一階段的步長依然是一個固定值，因此重構精度很大程度上依賴于每個階段步長的選擇。而LSAMP算法[12]則是在不同的階段采用了對數型變化的步長，該算法在采樣率較低時重構效果依然很好。但是這些算法本質上都屬于前向貪婪算法，前向算法最大的缺點就是不能修改前一步迭代造成的錯誤，原子一旦被選入支撐集便無法刪除。例如圖1所示，假設特征向量x是由觀測矩陣中的向量α1、α2構成，然而觀測矩陣中另外一個向量α3比其他兩個向量更接近特征向量x，這樣當采用像OMP、SAMP這類前向貪婪算法時首先會選擇α3，之后才會選擇α1、α2，并且這類算法還不能刪除α3，這樣的結果并不是我們想要的。事實上，只有在觀測矩陣中的向量不相關時前向貪婪算法才比較適用。

圖1 特征向量圖示

考慮到前向貪婪算法的缺點，很容易想到利用后向貪婪算法來進行改善。后向貪婪算法首先選擇全部原子，然后逐一刪除使重建誤差最小的原子。這種算法雖然不會陷入局部最優問題，但是其計算代價非常高，因為一般情況下觀測矩陣中M<

目前壓縮感知理論在很多方面得到了應用，比如：吳延海提出了基于改進SP算法的壓縮感知圖像重構[13]，廖斌提出了一種基于壓縮感知的盲數字水印算法[14]，李秀霞提出了基于壓縮感知的合成孔徑雷達圖像目標識別[15]等。越來越多的學者們將壓縮感知利用到人臉識別、醫學CT圖像重建、語音識別、衛星遙感圖像融合、無線傳感器網絡、探地雷達成像中。因此對壓縮感知理論的進一步研究就變得十分有意義。

1 壓縮感知理論以及重構算法

假設x為長度為N的原始稀疏信號，即x的稀疏度為K，K<

通常采用求解以下最優化問題來從測量信號y中重建出信號x：

min‖x‖0s.t. y=Φx

(1)

對于式(1)求最優解問題是NP難題[16-18]，而最小化l2范數問題又不能保證解的稀疏性。但是Candes等人指出，如果x足夠稀疏，Φ滿足約束等距條件RIP(Restricted Isometry Property)[19]時：

(2)

其中， δK∈(0,1)表示K稀疏度下的約束等距常數，此時就可以將問題轉化為求解l1范數最小化：

min‖x‖1s.t. y=Φx

(3)

通過利用匹配追蹤算法就可以進行對式(3)的近似求解。OMP算法、ROMP算法等都是在給定稀疏度的基礎上進行的重構，然而在實際應用中，信號的稀疏度K往往是未知的，這在一定程度上給信號的重構帶來了挑戰，于是Thong T.Do等人為了解決這一問題，提出了稀疏度自適應的匹配追蹤算法，將信號重構問題轉化為分階段處理的過程，打破了傳統的稀疏度已知的限制。之后更多學者專注于對SAMP算法的改進，比如變步長的MSAMP算法和對數型變步長的LSAMP算法。這些算法很好地解決了步長固定問題，重構效果也得到了很大的改善。

2 SAMP算法及其改進

SAMP算法實現了在稀疏度未知的情況下對信號的重構。該算法首先選取步長step，然后計算余量r和觀測矩陣Φi的內積，其中Φi表示觀測矩陣的每一列，根據內積值，選取size個最大的相關系數，將這些系數所對應的原子加入到索引集中。接著合并上一階段產生的支撐集得到候選集，再進行一次余量與候選集的內積，同樣選取size個相關系數最大的原子作為支撐集F。此時更新余量r，如果當前余量小于迭代前的余量，則繼續迭代，否則進入下一階段，根據步長更新支撐集容量size=size×step，重復上述步驟，直到余量r小于某個閾值停止迭代。

具體算法如下：

(1) 余量r=y，支撐集長度size=step，階段stage=1，支撐集F=?；

(2) 計算余量r和Φi內積的絕對值，從中選取size個最大值對應的索引值得到索引集S；

(3) 將索引集與上一階段的支撐集進行合并，得到候選集C=F∪S，再計算候選集與余量的內積，并提取size個最大值，將其相對應的原子加入到支撐集Fnew；

(5) 若‖rnew‖2≥‖r‖2，則進行下一迭代階段，stage=stage+1，利用初始步長更新支撐集容量size=stage×step，返回步驟(2)繼續迭代；否則更新支撐集和余量F=Fnew，r=rnew，此時迭代次數k=k+1，返回步驟(2)繼續迭代。

從上述算法中可以看到各個迭代階段步長step的取值是一個常數，步長的選擇關系到支撐集的容量，因此該算法的重構精度與該步長選擇有很大的關系。但是該算法的最大缺點就是不能后向刪除部分錯誤原子，在原子的原子過程中很有可能會產生一些錯誤的、冗余的原子，如果沒有辦法進行二次修正，不僅會影響算法的時間，也會影響算法的精度。因此本文結合以上算法的優點，針對不能后向刪除錯誤原子提出了利用對數型自適應變化步長的前向后向算法來實現信號的重建。

3 步長自適應的前向后向匹配追蹤算法

SAMP算法雖然突破了在傳統匹配算法中對稀疏度的限制，但是通過相關實驗表明，為了加快重構速度，初始步長step取較大值時，算法只需要很少的迭代次數，但是算法的效率就會很低。如果想保證算法的重構精度，step取很小的值時，迭代次數就會大大增加。另外傳統的算法在選擇原子過程中支撐集的容量是不斷增加的，但是又無法刪除那些錯誤的或者冗余的原子。因此選取合適的步長和利用后向策略來對算法進行修正是提高算法性能的關鍵。根據文獻[12]結合對數函數的性質，在SAMP算法的框架下，提出了步長自適應變化的前向后向匹配算法。該算法首先進行前向選擇匹配原子，然后進行向后剔除部分錯誤原子[20]，在確保重建精度的情況下，彌補了前向貪婪算法自身的缺點。接下來將從兩個方面對新算法進行具體描述：步長選擇和算法描述。

3.1 步長選擇

根據相鄰迭代階段重建信號差的變化規律，設置兩個閾值ε1、ε2(ε1>ε2)，當‖xt-xt-1‖>ε1時，選取一個較大的步長，實現快速逼近；當ε2<‖xt-xt-1‖<ε1時，選取較小的步長，以實現逐漸逼近，此時步長變為上階段步長的一半；當‖xt-xt-1‖<ε2時說明相鄰階段的能量差變化趨于平穩，則停止迭代。

設步長step為：

step(s)=alog2s+b

(4)

(5)

而當采取緩慢逼近策略時就選取前一階段步長的一半，即：

(6)

這里的步長均向上取為正整數，c≥1的正整數，M、N分別表示觀測信號和待估信號的長度。

3.2 算法描述

(1) 初始化稀疏度：余量r=y，支撐集F，支撐集長度size=step，階段stage=1，迭代次數t=1，索引值集合S=?，候選集C=?；

(2) 計算相關系數，從中提取size個最大值對應的索引值放入到集合S中；

(3) 合并索引集S與支撐集F，得到候選集C=F∪S，再計算候選集中索引值對應的原子與余量的內積，并提取size個最大值對應的索引值得到新的支撐集F；

(4) 由最小二乘得到xt=argmin‖y-ΦFxt-1‖2，更新余量rt=y-Φtxt-1；

(5) 如果‖xt-xt-1‖>ε1則轉步驟(6)，否則轉步驟(8)；

(6) 如果‖rt‖≥‖rt-1‖則轉入步驟(7)，否則轉入步驟(9)；

(7) 進入下一階段，stage=stage+1，利用式(5)求出新步長step，擴大支撐集大小size=size+step，t=t+1,返回步驟(2)；

(8) 如果‖xt-xt-1‖<ε2則停止迭代，否則轉入步驟(10)；

(9) 更新支撐集和余量返回步驟(2)繼續迭代；

(10) 進入小步長階段，stage=stage+1，利用式(6)求出新步長step，擴大支撐集大小size=size+step，t=t+1，返回步驟(2)；

(12) j=argmini∈Fq(F/i)；

(13) d-=q(F/j)-q(F)；

(14) d+=ε3；

(15) 如果d-d+；

4 實驗與分析

實驗一

為了驗證本文算法的有效性，通過MATLAB處理平臺對該算法進行了驗證。實驗一中采用長度為N=256的一維高斯稀疏信號，觀測矩陣為部分快速傅里葉變換矩陣(FFT)。閾值設置為ε1=e-6，迭代停止條件閾值ε2=e-12，ε3=e-14。在實驗一中比較了SAMP算法、MSAMP算法、LSAMP算法和AFBMP算法在不同采樣率下的重構效果。實驗中除本文算法以外其他算法的參數均按照原參考文獻中設置。實驗表明該算法的重構效果很好，相對誤差非常小，能夠很好地對原始信號進行重建，在理論上說明了新算法的有效性。

圖2是SAMP、MSAMP算法、LSAMP算法與AFBMP算法在不同采樣率下重構信號信噪比的比較。其中橫坐標表示采樣率，縱坐標為信噪比，實驗結果顯示，該算法在前向階段通過采用對數型變化的步長選取匹配原子，后向階段刪除錯誤原子，使得該算法的性能得到了明顯的提升，AFBMP算法提高了對原始信號的重構精度。

圖2 不同采樣率下重構信號的信噪比

圖3比較了四種算法在不同采樣率下的重構相對誤差。實驗發現，SAMP算法在不同采樣率下的重構誤差相對很高，而MSAMP算法和LSAMP算法是對原來算法的改進在一定程度上均降低了重構的相對誤差，而AFBMP算法結合了前面幾種算法的優點，使得重構相對誤差變得更低。我們發現，在相同采樣率下，AFBMP算法比其他三種算法的相對誤差低很多，因此該算法充分保證了對稀疏信號的重構精度，同時也證明了該算法的有效性。

圖3 不同采樣率下幾種算法的相對誤差

實驗二

為了更為充分地說明新算法在實際問題中的應用，本文實驗二對大小為256×256的圖像進行實驗。閾值設置為ε1=e-6，迭代停止條件閾值ε2=e-12，ε3=e-14。將本文算法和經典SAMP算法、MSAMP算法對三組測試圖像進行比較。圖4表明，改進的SAMP算法重構效果均好于經典SAMP算法，而AFBMP算法的重構效果也明顯好于其他算法，同時也證實了本文算法的實用價值。

圖4 二維圖像重建效果

表1是這三組測試圖進行重構的運行時間，從上節的實驗可知不同的采樣率下對算法性能的影響很大，因此采樣率為0.5的情況下重構時間如表1所示。

表1 不同圖像不同算法的重構時間

通過表1可以看出在相同的采樣率下，對于不同的圖像，各種算法的重構時間也有所不同，而AFBMP算法的重構時間略低于傳統的SAMP算法，進一步說明了本文算法在運行時間上有一定的優勢。

5 結 語

本文深入研究了壓縮感知理論的經典算法，在稀疏度未知的情況下結合SAMP算法，提出了一種對數型自適應步長的前向后向匹配算法。SAMP算法在迭代過程中固定步長可能會導致過估計或者欠估計的問題，并且迭代結束之后不能刪除某些冗余原子和錯誤原子。針對這兩個問題，在SAMP算法框架基礎上，前向迭代過程中采用改進的對數型可變化的步長選取匹配原子，而向后階段逐一測試支撐集中的每一個原子，刪除前向階段所產生的錯誤原子，通過設置雙閾值來控制步長選擇和停止準則，分段逐步實現對稀疏度的逼近，最終實現信號的精確重構。實驗結果表明，新算法可以較好地實現未知稀疏度信號的重建，且重建性能明顯優于SAMP算法。

[1] Candes E J,Wakin M B.An introduction to compressive sampling[J].IEEE Signal Proc Mag,2008,25(2):21-30.

[2] Donoho D L.Compressed sensing[J].IEEE Transactions on Information Theroy,2006,52(4):1289-1306.

[3] Chen S B,Donoho D L,Saunders M A.Atomic decomposition by basis pursuit[J].SiamJ.Sci.comput,2001,20(1):129-159.

[4] Mallat S,Zhang Z.Matching Pursuit with time-frequency dictionaries[J].IEEE Trans.Sig.Proc,1993,41(12):3397-3415.

[5] Tropp J,Gilbert A.Signal recovery form random measurements via orthogonal matching pursuit[J].IEEE Transactions on Information theory,2007,53(12):4655-4666.

[6] Needell D,Vershynin R.Signal recovery from incomplete and inaccurate measurements via regularized orthogonal matching pursuit[J].IEEEJournal of Selected Topics in SignalProcessing,2010,4(2):310-316.

[7] Needell D,Tropp J A.Iterative signal recovery from incomplete and inaccurate samples[J].Applied and Computational Harmonic Analysis,2009,26(3):301-321.

[8] Dai W,Milenkovic O.Subspace pursuit for compressive sensing signal reconstruction[J].IEEE Transactions on information theory,2009,55(5):2230-2249.

[9] 郭永紅,楊毅彬.一種稀疏自適應的正交互補匹配追蹤算法[J].計算機工程與應用,2013,49(7):144-146.

[10] Donoho D L,Tsaig Y,Drori I,et al.Sparse solution of underdetermined linear equations by stage wise orthogonal matching pursuit[J].IEEE Transaction on Information Theroy,2012,58(2):1094-1121.

[11] 朱延年,趙擁軍,孫兵.一種改進的稀疏度自適應匹配追蹤算法[J].信號處理,2012,28(1):80-86.

[12] 畢學霞,尚振宏.一種基于變步長的稀疏度自適應匹配追蹤算法[J].系統仿真學報,2014,26(9):2116-2125.

[13] 吳延海,閆迪.基于改進SP算法的壓縮感知圖像重構[J].計算機應用與軟件,2013,30(7):200-203,216.

[14] 廖斌,任美玲,徐俊剛.一種基于壓縮感知的盲數字水印算法[J].計算機應用與軟件,2014,31(2):307-311.

[15] 季秀霞,卞曉曉.基于壓縮感知的合成孔徑雷達圖像目標識別[J].計算機應用與軟件,2013,30(12):120-123.

[16] 李然,干宗良,朱秀昌.基于最佳線性估計的快速壓縮感知圖像重建算法[J].電子與信息學報,2012,34(12):3006-3012.

[17] Baraniukr R.Compressive sensing[J].IEEE Signal Processing Magazine,2007,24(4):118-126.

[18] Candes E,Romberg J,Tao T.Robust uncertainty principles:exact signal reconstruction from highly incomeplete frequency information[J].IEEE Transactions on Information Theory,2006,52(2):489-509.

[19] Do T T,Gan L,Nguyen N,et al.Sparisity adaptive matching pursuit algorithm for practical compressed sensing[J].IEEE Asilomar Conference on Signals,Systems and Computers,2008,10(7):581-587.

[20] Wei Tang,Zhenwei Shi.Regularized simultaneouss forward-backward greedy algorithm for sparse unmixing of hyperspectral data[J].IEEE Transactions on geoscience and remote sensing,2014,52(9):5271-5288.

ADAPTIVE STEPSIZE FORWARD-BACKWARD MATCHING PURSUIT ALGORITHM

Zhang Songjiang Zhou Mi Zhang Chuanlin

(School of Information and Science Technology,Jinan University,Guangzhou 510000,Guangdong,China)

Sparsity adaptive matching pursuit algorithm (SAMP) is a classical algorithm of signal reconstruction based on compressed sensing theory. Aiming at reconstructing signals with unknown sparsity, we presented an adaptive stepsize forward-backward matching pursuit algorithm (AFBMP). In the framework of SAMP, AFBMP selects matching atoms in its forward search process by using logarithmic adaptive changing steps, and then amends the mistakes caused in forward stage by backward strategy to delete part of the false atoms in support set, and finally realises accurate signal approaching. Experiments show that the AFBMP algorithm can reconstruct the signals with unknown sparsity more efficiently than SAMP algorithm.

Compressed sensing Reconstruction Forward-backward Sparsity adaptive Matching pursuit algorithm

2015-09-15。張松江，碩士，主研領域：圖像處理。周密，碩士。張傳林，教授。

TP391.9

A

10.3969/j.issn.1000-386x.2016.11.057