一種改進的快速匹配追蹤算法

袁 靜，吳 潔，張亞姣

（宿遷學院，江蘇 宿遷223800）

0 引 言

壓縮感知的重構算法是壓縮感知理論的核心問題，貪婪算法因其算法思路簡單、算法收斂速度快、重構效果較好成為壓縮感知重構過程中應用較普遍的算法。Tropp和Gilbert在文獻［1］中證明了稀疏分解中的匹配追蹤（MP）算法和正交匹配追蹤（OMP）算法可以用來求解壓縮感知的重構問題。這種基于貪婪思想的算法不僅易于實現而且可以極大地提高計算的速度。MP算法和OMP算法一次只選擇一個原子，速度較慢，因此Donoho等［2］提出了分段正交匹配追蹤（StOMP，Stagewise OMP）算法，該算法根據一定的標準，一步選擇多個原子，在保證算法重構精度的基礎上進一步提高了算法的計算速度。Needell等［3］提出了正則正交匹配追蹤（Regularized orthogonal matching pursuit，ROMP）算法，一次選擇一組原子后再根據標準進行再次篩選，保證了算法的重構精度。國內也有多位學者對壓縮感知的重構算法進行了研究［4，5，6］。但 是 ROMP 算 法 篩 選 原 子 的 方 法比 較 麻煩、計算量較大，本文針對ROMP算法的缺點，將硬閥值思想引入OMP算法中，提出一種改進的正交匹配追蹤算法。

1 改進的快速匹配追蹤算法

1.1 ROMP

Needell等［3］在StOMP算法的基礎上提出了正則正交匹配追蹤（ROMP，Regularied OMP）算法，該算法首先進行第一步原子篩選：依照相關性的大小選擇一組原子對應的索引加入到候選原子索引集合J中；然后對第一步選擇的原子進行第二步篩選：將候選原子正則化后選擇能量最大的一組原子加入到選定原子索引集合∧中。由于正則化的引入，使得算法能夠對觀測信號進行精確重構。

信號的逼近使用最小二乘法：

式中，Φ∧表示由選定原子索引所對應的觀測矩陣的相應的列向量所構成的矩陣。

二次篩選中的正則化方法為：根據式（1）將J中索引所對應的原子的相關系數兩兩分組：

然后將其中能量最大的一組相關系數所對應的原子索引加入到選定原子索引集合∧中。由于ROMP算法能夠保證沒有被選入原子的相關系數的能量一定小于被選定的原子相關系數的能量，所以算法的重構精度得到了保證。

ROMP算法的基本步驟為：

（1）初始信號殘余量r0=y，信號稀疏度的估計值K，n=1，選定原子索引集合∧=?，候選原子索引集合J=?；

（2）根據μ=｛μi|μi=|（r，φi）|，i=1，2，……，N｝計算感知矩陣中各列原子φi和殘余量rn-1的內積，將最大的K個值對應的索引加入候選原子索引集合J中；

（3）對J中索引值所對應原子的相關系數按|μ（i）|＜2|μ（j）|，i，j∈J進行正則化，將正則化所得到的原子對應的索引加入到選定原子索引集合∧中；

（4）根據x=argmin‖y-Φ∧x‖2和r=y-Φ∧＾x對信號的殘余量rn進行更新；

（5）若|∧|≥2K，算法停止；否則r=rn，n=n+1，轉向步驟（2）。

從ROMP算法的詳細步驟中可以看到，首先要對信號的稀疏度進行適當的估記，對信號稀疏度的估計過大或過小都會影響信號的重構精度。盡管不少研究人員提出了不同的信號稀疏度的估計算法，但是效果都不理想，目前還沒有一種公認的具有普適性的信號稀疏度的估計算法。由迭代過程可以看出，ROMP算法每次迭代可以選擇多個原子加入候選集，最多經過K次迭代，候選集原子數目就可以大于2K，有效提高了收斂速度，降低了重構時間。

但此算法也有不足之處，篩選原子的方法比較麻煩，計算量較大，對于處理的原子個數較多的情況，耗時也成倍增加。而且，對于已選入候選集的原子，重復選入和計算，這個缺點也增加了計算量和時間消耗。如何在提升速度的同時不明顯降低算法性能，這是本文研究的目標。

1.2 匹配追蹤算法的改進

為了克服ROMP算法的不足，同時保留分組匹配追蹤算法批量選擇原子的優點，本文提出了一個基于硬閾值的快速匹配追蹤算法。該算法采用了一種新的批量篩選原子的方法，同時在每次迭代過程中從原子候選集中剔除已選入選定原子索引集的原子，以避免重復選入原子和增加計算量。

OMP算法每次只選擇內積向量中絕對值最大的元素對應的原子，實際上，內積值向量中存在一部分元素和最大值接近，數值也很大，如果將這部分原子一起加入候選集，可以有效提高原子的篩選效率。本文利用硬閾值思想，對內積向量中的元素進行篩選：

式中，J=｛1，2，…，N｝，μmax是內積向量中絕對值最大的元素，α∈（0，1］是閾值參數。

另外，為了避免已加入選定原子索引集的原子在后續迭代過程中被重復選入，本文改進的算法將每次迭代過程中已選入選定原子索引集的原子從感知矩陣Φ中剔除，利用得到的殘余感知矩陣Φc與殘余量做內積，以降低計算量。

本文算法首先計算殘余感知矩陣Φc中每列原子Φi與殘余量r之間的內積，選出內積絕對值最大的前K個元素，根據式（4）利用硬閾值的方法對K個元素進行二次篩選，將選擇一組元素對應的原子集合的索引值加入候選原子索引集中，并更新選定原子索引集。然后，從感知矩陣Φ中剔除已加入選定原子索引集的原子，更新殘余感知矩陣Φc。其他的迭代步驟仍沿用OMP算法思路。本文算法具體步驟如下：

（1）初始信號殘余量r0=y，信號稀疏度的估計值K，n=1，選定原子索引集合∧=?，候選原子索引集合J=?，殘余感知矩陣Φc=Φ；

（2）根據μ=｛μi|μi=|（r，φi）|，i=1，2，……，N｝計算殘余感知矩陣Φc中各列原子φi和殘余量rn-1的內積，找出內積向量中最大的K個值；

（3）根據|μi|≥α|μmax| i∈J對K個元素進行篩選，選出一組元素，將其在感知矩陣中對應的原子集合的索引值記為I中索引值所對應原子的相關系數按進行正則化，將正則化所得到的原子對應的索引加入到選定原子索引集合∧中；

（4）更新候選原子索引集J=J∪I，更新選定原子索引集∧=∧∪J

（5）從感知矩陣Φ中剔除已加入選定原子索引集的原子，更新殘余感知矩陣Φc=Φ-Φ∧

（6）根據＾x=argmin‖y-Φ∧x‖2和r=y-Φ∧＾x對信號的殘余量rn進行更新；

（7）若‖rn-rn-1‖≥ε，r=rn，n=n+1，轉向步驟（2）；否則算法停止。

由上述迭代過程可以看出，本文算法每次可以選擇多個原子加入選定原子索引集，最多經過K次迭代，選定原子索引集原子數目就可以t＞K，終止迭代，可以有效提高重構速度，降低重構時間。不足的是，本文算法重構速度的提高是以降低重構質量為代價的，對重構精度要求高的場景不適用。

2 實驗仿真

為了驗證本文算法的重構性能，本文選取標準圖像Lena（512×512）進行實驗，使用matlab仿真軟件。首先對圖像做離散小波變換，然后利用高斯隨機矩陣作為測量矩陣，進行測量壓縮，最后用本文算法重構原圖像。選取采樣率為0.1～0.5，閾值參數a=0.7，0.75，0.8，0.9進行實驗，分別計算了重構質量（PSNR值）和重構時間結果，給出了a=0.7時重構圖像的視覺效果圖，如圖1和表1所示。

圖1 α=0.7時,本文算法對二維圖像的重構視覺效果圖

表1 在不同采樣率時,本文算法(proposed)和其他重構算法的重構質量比較(PSNR/dB)

表2 在不同采樣率時,本文算法(proposed)和其他重構算法的重構時間比較(t/s)

由圖1和表1可以看出，本文算法重構圖像的質量和視覺效果較好。α=0.7時，本文算法的PSNR值略低于ROMP，隨著閾值參數α變大，PSNR值也逐漸升高，基本和ROMP的PSNR值齊平，比SP算法的重構質量略差。由表2可以看出，本文算法的重構時間要明顯小于其他的算法，相比于OMP和SP算法，重構速度大大提升，也快于ROMP算法。閾值參數α越大，重構時間越長，原因是閾值參數α變大，會導致每次迭代選出的原子個數變少，從而收斂速度變慢，重構速度有所下降，但和其他算法比，仍具有優勢。

實驗證明，本文算法在保證重構質量的基礎上，通過閾值化方法批量選擇原子，有效地提高了原子的篩選效率，同時在每次迭代中剔除已選入支撐集的原子，使重構時間明顯改善，對重構速度要求高的場合有很強的適用性。同時，閾值參數較小時，重構時間較短，閾值參數較大時，重構質量較好，因此可以通過調節閾值參數來調整重構質量或重構時間，具有靈活性。

3 結 語

本文提出了一個基于硬閾值的快速匹配追蹤算法，采用了一種新的批量篩選原子的方法，同時在每次迭代過程中從原子候選集中剔除已選入選定原子索引集的原子，并針對所改進算法的原理、實現步驟和適用場景進行分析和說明，實驗證明，該算法簡單有效，可以在較小幅度降低算法性能的情況下提升收斂速度，有效地降低了重構時間。

［1］J TROPP，A GILBERT.Signal Recovery from Random Measurements Via Orthogonal Matching Pursuit ［J］.IEEE Transactions on Information Theory，2007，53（12）：4655-4666.

［2］D L DONOHO，Y TSAIG，I DRORI，J L Starck.Sparse Solution of Underdetermined Linear Equations by Stagewise Orthogonal Mathing Pursuit［D］.Tech.Rep.2006-2，Department of Statistics，Stanford University，2006.

［3］D NEEDELL，D VERSHYNIN.Uniform Uncertainty Principle and Signal Recovery Via Regularized Orthogonal Mathing Pursuit ［J］.Foundations of Computational Ma1Lhematies，2009，9（3）：317-334.

［4］余慧敏，方廣有.壓縮感知理論在探地雷達三維成像中的應用［J］.電子與信息學報，2010，32（1）：12-16.

［5］陳善雄，何中市，熊海靈，等.一種基于壓縮感知的無線傳感信號重構算法［J］.計算機學報，2015，38（3）：614-624.

［6］劉盼盼，李雷，王浩宇.壓縮感知中基于變尺度法的貪婪重構算法的研究［J］.通信學報，2014，35（12）：98-105.

［7］翟雪含.壓縮感知的分類稀疏表示及重構算法研究［D］.南京：南京郵電大學，2014.