基于限制等距性質閾值機制的匹配追蹤算法

黃宏偉，謝正光，蔣小燕，蔡 旭

（南通大學 電子信息學院，江蘇 南通226019）

0 引 言

近幾年一種高效的信號采集技術壓縮感知 （compressed sensing，CS）［1］逐漸被人們學習了解。它的模式是邊采集邊壓縮，即在數(shù)據(jù)采集過程中就進行適當?shù)膲嚎s，這樣信號采集速度能低于奈奎斯特采樣速度，節(jié)省大量資源［2，3］。

壓縮感知測量過程可以用方程描述為y ＝Φx，其中y是長度為M 的觀測信號，Φ ＝［，…］是測量矩陣，大小為M×N ，x為K 階稀疏信號，長度為N，K ＜M ＜N，這個過程相當于把原始信號投影到［，…］張成的空間上［4］。

壓縮感知中重構算法是核心內容，是從測量矩陣Φ和觀測信號y中恢復原始稀疏信號x。這個過程可以當作l0最小化問題來求解：x＝argmin x0subject to y＝Φx，理論上，沒有噪聲的前提下，K 階稀疏信號僅需M ≥2 K 次測量就可以恢復。但是l0最小化問題是NP－h(huán)ard問題。Donoho和Candes指出不必求助于l0解稀疏解，而是通過一個更簡單的l1最優(yōu)化方法：x ＝argmax x1subject to y ＝Φx，但是要求Φ滿足RIP［5］。雖然線性規(guī)劃方法重構效果很好，但是它的高復雜度限制了其實際應用，這就要求我們設計一種快速的求解方法。

貪婪算法因為其較低的復雜度而受到越來越多人的關注。包括匹配追蹤 （matching pursuit，MP），OMP［6－8］、正則化正交匹配追蹤 （regularized OMP，ROMP）［9］、分段式正交匹配追蹤 （stagewise OMP，StOMP）、壓縮采樣匹配追蹤算法 （compressive sampling matching pursuit，Co－SaMP）［10］、SP［11］等等。這些方法的基本思想是通過相關性從不相關的原子中尋找正確的支撐集，每一個迭代過程都是從原子序列中找出認為足夠相關的原子索引并添加到支撐集中。MP算法每次尋求的是局部的最優(yōu)解，雖然執(zhí)行速度快，但是最終不一定收斂到全局最優(yōu)，所以重構精度不是很高。帶有回溯思想的SP算法有兩個特征，一是當信號非常稀疏時，SP 算法比OMP 算法計算復雜度低；二是SP算法的重構精確度與LP 方法相當［11］。但是，SP 算法沒有考慮代理信號和殘差關系，每次迭代都選擇K 個原子，這可能導致迭代過程中選擇錯誤支撐集數(shù)目增多。經(jīng)典的OMP算法有兩個缺點：第一是每次選擇的最大相關原子不一定是正確原子；第二是每次迭代添加的支撐集原子索引都是不會被移除的，即無自主糾錯能力。針對OMP這兩個缺點，我們提出RIPTMP 算法的原子選擇方案。RIPTMP首先根據(jù)RIP和殘差條件一次選出多個原子，其次算法能夠根據(jù)信號特點剔除可能錯誤的原子。在該方案下，算法提高了尋找支撐集的精度。

1 RIPTMP算法

1.1 符號標注

首先簡單說明本文涉及的符號。supp（x）表示向量x 中非零元素的位置，即向量x 的支撐集。K 表示稀疏度。ΦT表示Φ的轉置，T0定義為初始的支撐集，表示初始的殘差，Tl表示第l次迭代得出的支撐集，表示Tl的補集。表示第l次迭代得出的信號殘差，表示x 對應Tl位置上的元素集合。ΦI表示I 中所有索引對應原子的集合，如果ΦI可逆，那么yp表示y 在ΦI上的投影yp＝＜y，，其中，代表ΦI的偽逆。δK＋1為K＋1階RIP常數(shù)，表示第l次迭代的代理信號表示代理信號中的元素，其中＜·＞表示內積運算，ei為單位矩陣的第i列。

1.2 RIPTMP算法流程

RIPTMP算法在原子選擇上帶有回溯思想，經(jīng)典的SP算法也具有同樣思想。SP算法需要待重構稀疏信號的稀疏度K。算法在每次迭代過程中，原子添加的和刪減的數(shù)量都為K。具體算法見表1。

表1 子空間追蹤算法

SP有兩個缺點，一方面在原子選擇數(shù)量上沒有考慮殘差變化，每次選取的數(shù)量為固定值K，這就可能導致當前選擇多個錯誤的原子，從而引起重構精度下降；另一方面算法需要待重構稀疏信號的稀疏度。

RIPTMP算法除了需要測量矩陣Φ和觀測信號y，還需要算法停止參數(shù)ε，支撐集添加閾值E，支撐集保持閾值P，和最大迭代次數(shù)imax。算法具體流程見表2。

表2 基于RIP閾值機制的匹配追蹤算法

1.3 RIPTMP算法分析

RIPTMP算法中有兩個參數(shù)，E 和P。下面我們給出這兩個參數(shù)選擇依據(jù)：

1.3.1 預備知識

（1）有限等距性質 （RIP）定義［11］

如果矩陣Φ ∈RM×N滿足參數(shù)為 （K，δ）的有限等距性質，K ≤M ，0≤δ＜1。對于任意的k 階稀疏信號x ∈

（2）最大相關選擇原理

假設Φ的所有列向量都是完全正交的，即Φ為正交矩陣，那么所求代理信號系數(shù)＜，y＞中非零值對應的位置就是原信號的支撐集。但是大部分Φ中列向量都不是完全正交的，（1）說明滿足RIP條件的Φ近似為正交矩陣，這時候最大相關系數(shù)對應的位置索引不一定在原信號支撐集中。但是，正確原子和觀測信號的相關系數(shù)和非正確原子和觀測信號的相關系數(shù)是有界的。因此我們可以根據(jù)相關系數(shù)的界尋找支撐集。

（3）引理

引理1［9］對于任意的兩個正整數(shù)m≤n，有δm≤δn。

引理2［5］設supp（x），supp（y）｛1，2，…N｝，｜supp（x）｜≤m，｜supp（y）｜≤n，supp（x）∩supp（y）＝，那么｜＜Φx，

引理3 設向量x∈RN，｜supp（x）｜≤m，那么

1.3.2 E，P參數(shù)估計

第一次迭代：

假設矩陣Φ∈RM×N滿足參數(shù)為 （K ＋1，δ）的有限等距性質，根據(jù)引理2 有：isupp（x），｜h1（i）｜＝｜＜

同理對于第l次迭代

結合第一次迭代和第l次迭代，我們把i∈supp（x）的｜hl（i）｜和jsupp（x）的｜hl（j）｜的界進行估計。即對于任意jsupp（x），有

通過上面推導過程可以發(fā)現(xiàn)E 和P 的邊界條件經(jīng)過了放縮，E估計的界是在實際的界基礎上進行了放大，P 估計的界是在實際界的基礎上進行了縮小，因此在實驗仿真階段可以在估計出來的界基礎上適當?shù)姆趴s。

雖然RIPTMP算法是鑒于SP算法兩個缺點提出來的，但是它的理論基礎卻來源于OMP 算法。OMP 算法每次迭代只選擇最相關的原子，同時選擇的原子不會被移除，而實際上，最相關原子不一定是正確原子，當算法引入了錯誤原子時應該通過回溯過程進行剔除。因此，我們先把所有可能正確的原子都選出來，然后再剔除可能錯誤的原子。通過理論分析，添加和刪減原子的數(shù)量和殘差，RIP 常數(shù)密切相關，所以我們通過殘差和RIP 常數(shù)條件求出相應閾值來篩選原子。

2 實驗

為了全面測試算法重構性能，對一維信號和二維信號都進行了相關實驗。在一維信號部分，選擇了3種不同類型的稀疏信號分別為高斯信號， “0－1”信號和均勻分布信號。二維信號則是標準的Lena，Boat測試圖像。

2.1 一維信號仿真實驗

令測量矩陣為標準正態(tài)分布矩陣，測量次數(shù)M＝128，信號長度N＝256。OMP 和RIPTMP 迭代停止閾值相同，均取ε＝10－6，RIPTMP 的最大迭代次數(shù)imax＝0.5 M，BP算法重構通過cvx工具箱實現(xiàn)。FBP 算法給前長步長α＝0.3 M，后退步長β＝α－1，停止閾值ε＝10－6，最大迭代次數(shù)imax＝0.5 M。實驗中RIPTMP 算法有3種不同的設置，分別是（E＝0.2，P＝0.7）、（E＝0.1，P＝0.6）、（E＝0.1，P＝0.4）。重構成功條件：均方誤差，實驗次數(shù)times取500。

實驗結果如圖1所示。

2.2 二維信號仿真實驗

為了衡量算法對稀疏圖像信號重構性能，選擇標準的256×256的Lena，Boat作為測試圖像。隨機產生大小為M×N 的測量矩陣Φ，Φ為歸一化的準高斯矩陣，對圖像信號進行小波變換選擇sym6小波基。保留小波變換后系數(shù)矩陣每列最大的q個小波系數(shù)，其余置零。峰值信噪比計算

圖1 一維信號仿真實驗

分別用SP，BP，RIPTMP，F(xiàn)BP這4種重構算法重構圖像信號，其中SP稀疏度設置為q，RIPTMP參數(shù)設置為（E＝0.1，P＝0.6），F(xiàn)BP停止參數(shù)和最大迭代次數(shù)相同。重構結果如圖2所示。

圖2 二維信號仿真實驗

2.3 實驗結果分析

（1）一維信號重構實驗

在圖1 （a）高斯信號仿真實驗中，E＝0.2，P＝0.7的RIPTMP算法的重構誤差比OMP，SP 低，成功重構概率明顯高于OMP，SP算法。SP成功重構概率從K＝40開始下降，而RIPTMP從K＝43才開始下降。當我們把前面推導并估計出的界E 適當收縮到0.1，同時P 放大到0.6，RIPTMP效果明顯提升。一方面重構均方誤差低于包括BP在內的其它所有算法，當K＝50才由0逐步上升，而且在稀疏度取值區(qū)間［1，2，3...56］內都保持較低的值；另一方面成功重構概率在相同稀疏度條件下比其它算法都要高，當稀疏度達到52 以上時，才出現(xiàn)重構失敗情況。參數(shù)為（E＝0.1，P＝0.4）的RIPTMP 重構情況和參數(shù)為 （E＝0.1，P＝0.6）RIPTMP重構情況相當。

在圖1 （b）“0－1”信號實驗中，OMP效果最差，從仿真數(shù)據(jù)可以看出 （為了方便顯示，曲線前面部分經(jīng)過適當省略），當稀疏度到10左右誤差就開始從0開始上升，而其它算法依然保持0的水平。當K 增加到25左右SP算法和參數(shù)為 （E＝0.2，P＝0.7）的RIPTMP 和StOMP 重構誤差開始從0增加，到K 增加到28左右，SP和FBP算法誤差開始從0上升。當K 增加到31左右參數(shù)為 （E＝0.1，P＝0.4）和 （E＝0.1，P＝0.6）的RIPTMP算法重構誤差開始從0上升。對應的重構百分，OMP從K＝8處重構開始出現(xiàn)失敗。參數(shù)為 （E＝0.2，P＝0.7）和StOMP 算法從K＝28處重構開始出現(xiàn)失敗。當K 增加到29 時，F(xiàn)BP和SP出現(xiàn)重構失敗情況。當K 達32左右，參數(shù)為 （E＝0.1，P＝0.4）和 （E＝0.1，P＝0.6）的RIPTMP 算法出現(xiàn)重構失敗。BP算法重構結果最好。

在圖1 （c）均勻信號實驗中，RIPTMP 算法重構誤差明顯小于OMP，接近BP 算法。參數(shù)為 （E＝0.1，P＝0.4）和 （E＝0.1，P＝0.6）的RIPTMP 算法在稀疏度［1，2，3…52］區(qū)間內重構的均方誤差和BP 算法相差不大，緊接著是SP算法，參數(shù)為 （E＝0.2，P＝0.7）RIPTMP算法等等。重構百分比曲線上可以得出參數(shù)為 （E＝0.1，P＝0.6）和 （E＝0.1，P＝0.4）的RIPTMP 算法在稀疏度達到46 才開始下降，緊接著是FBP 算法、參數(shù)為（E＝0.2，P＝0.7）RIPTMP算法、SP算法等等。

實驗說明，RIPTMP 算法在一定條件下，相比OMP，StOMP，SP，F(xiàn)BP算法有更高的重構精度和重構成功概率。雖然E，P參數(shù)推導過程得出相同的閾值條件，但是E＝P≈0.4的閾值條件并不是準確的。E推導的界比真實的界大，P推導的界比真實的界小，因此適當改變E，P可以得出精度更高的支撐集估計效果，實驗部分正好證明了這一點。

（2）二維信號重構實驗

圖2中，我們列出了SP，BP，F(xiàn)BP 和RIPTMP 算法重構效果。Lena圖像重構實驗中，SP算法重構信號的峰值信噪比為32.3dB，BP為33.4dB，F(xiàn)BP為33.2dB，參數(shù)為 （E＝0.1，P＝0.6）的RIPTMP 為33.4dB。Boat圖像重構實驗中，SP 算法重構信號的峰值信噪比為31.7dB，BP為32.0dB，F(xiàn)BP 為31.8dB，參數(shù)為 （E＝0.1，P＝0.6）為32.0dB。可以看出RIPTMP算法的峰值信噪比高于SP算法，當E＝0.1，P＝0.6時，達到了BP算法水平。FBP 算法峰值信噪比也接近BP 算法，略低于RIPTMP算法。

二維圖像信號重構中，雖然用小波變化對圖像進行稀疏化處理，但是得到的并不是嚴格的稀疏矩陣。因此我們對小波變化后的矩陣進行了處理，即保留小波變換后系數(shù)矩陣每列最大的q 個小波系數(shù)，其余置零。因為測量矩陣的列向量不是完全正交的，所以可能導致數(shù)值較小的小波系數(shù)所在列的索引被當成重要的原子來重構，而真正大的小波系數(shù)被忽略，這就會影響重構的精度。在信號重構部分，經(jīng)典的SP算法需要稀疏度條件，而圖像稀疏化過程中如果不進行特定的處理不能獲取稀疏度的條件，因而不能確定每次迭代選取原子個數(shù)。RIPTMP 算法是通過最大迭代次數(shù)控制迭代過程，在稀疏度較小的時候，經(jīng)過很少的迭代就可以找出所有的原子，因此我們并不需要待重構稀疏信號的稀疏度。所以，二維圖像信號重構上RIPTMP 算法比SP算法更加合理。FBP算法雖然不需要稀疏度條件，但是每次更新原子的步長是不變的，前長步長α＝0.3 M ，后退步長β＝α－1。這種選擇原子同樣沒有考慮信號殘差的變化因素，且前向步長的確定條件并沒有給出理論依據(jù)，而RIPTMP 給出原子選擇的依據(jù)，而且仿真效果好于FBP，因此更合理。

3 結束語

本文基于SP算法重構精度低，需要已知稀疏度的缺點提出RIPTMP算法。首先算法在尋找支撐集上和SP不同，RIPTMP算法是根據(jù)RIP條件估計正確支撐集代理信號的幅值范圍，選出所有滿足的原子，而不是僅僅只選擇代理信號的最大值對應的原子。其次，算法不需要稀疏度作為算法輸入條件。實驗結果表明，在一定條件下RIPTMP 算法重構精度高于OMP，SP，F(xiàn)BP 等經(jīng)典算法，達到了BP算法水平，而且算法不需要待重構信號稀疏度。

［1］Candès E J，Wakin M B.An introduction to compressive sampling ［J］.Signal Processing Magazine，IEEE，2008，25（2）：21－30.

［2］SHI Guangming，LIU Danhua，GAO Dahua，et al.Advances in theory and application of compressed sensing ［J］.Acta Electronica Sinica，2009，37 （5）：1070－1081 （in Chinese）. ［石光明，劉丹華，高大化，等.壓縮感知理論及其研究進展［J］.電子學報，2009，37 （5）：1070－1081.］

［3］DAI Qionghai，F(xiàn)U Changjun，JI Xiangyang.Research on compressed sensing ［J］.Journal of Computers，2011，34（3）：425－434 （in Chinese）.［戴瓊海，付長軍，季向陽.壓縮感知研究 ［J］.計算機學報，2011，34 （3）：425－434.］

［4］FANG Hong，YANG Hairong.Greedy algorithms and compressed sensing ［J］.Acta Automatica Sinica，2011，37 （12）：1413－1421 （in Chinese）.［方紅，楊海蓉.貪婪算法與壓縮感知理論 ［J］.自動化學報，2011，37 （12）：1413－1421.］

［5］Candes E J.The restricted isometry property and its implications for compressed sensing ［J］.Comptes Rendus Mathematique，2008，346 （9）：589－592.

［6］Wu R，Huang W，Chen D R.The exact support recovery of sparse signals with noise via orthogonal matching pursuit［J］.Signal Processing Letters，IEEE，2013，20 （4）：403－406.

［7］SHEN Y，LI S.Sparse signals recovery from noisy measurements by orthogonal matching pursuit ［J］.arXiv Preprint arXiv：1105.6177，2011.

［8］Ding J，Chen L，Gu Y.Perturbation analysis of orthogonal matching pursuit ［J］.IEEE Transactions on Signal Processing，2013，61 （2）：398－410.

［9］Needell D，Vershynin R.Uniform uncertainty principle and signal recovery via regularized orthogonal matching pursuit［J］.Foundations of Computational Mathematics，2009，9 （3）：317－334.

［10］Needell D，Tropp J A.CoSaMP：Iterative signal recovery from incomplete and inaccurate samples ［J］.Applied and Computational Harmonic Analysis，2009，26 （3）：301－321.

［11］Dai W，Milenkovic O.Subspace pursuit for compressive sensing signal reconstruction ［J］.IEEE Transactions on Information Theory，2009，55 （5）：2230－2249.

［12］MO Q，SHEN Y.A remark on the restricted isometry property in orthogonal matching pursuit［J］.IEEE Transactions on Information Theory，2012，58 （6）：3654－3656.