基于壓縮感知的加速前向后向匹配追蹤算法

王 鋒 孫桂玲 張健平 何靜飛

?

基于壓縮感知的加速前向后向匹配追蹤算法

王 鋒①孫桂玲*①張健平②何靜飛①

① (南開大學電子信息與光學工程學院 天津 300350)②(上海交通大學電子信息與電氣工程學院 上海 200030)

前向后向匹配追蹤(FBP)算法作為一個新穎的兩階段貪婪逼近算法，因為較高的重構精度和不需要稀疏度作為先驗信息的特點，受到了人們的廣泛關注。然而，FBP算法必須運行更多的時間才能得到更高的精度。鑒于此，該文提出加速前向后向匹配追蹤(AFBP)算法。該算法利用每次迭代中候選支撐集的信息，實現對已刪除原子的再次加入，以此減少算法迭代次數。通過不同非零項分布的稀疏信號和稀疏圖像的仿真結果表明，相對于FBP算法，該文提出的方案在不降低重構精度的同時，大幅降低了算法運行時間。

壓縮感知；貪婪算法；前向后向搜索；稀疏信號重構

1 引言

壓縮感知(Compressed Sensing, CS)[1, 2]將稀疏信號的采樣和壓縮進行結合，從而降低測量系統的采樣率和計算復雜度。這一特性使得壓縮感知在無線傳感器網絡[3]、核磁共振成像等領域[4, 5]有廣泛應用前景。壓縮感知重構算法可以分為3大類：貪婪算法，凸松弛算法和貝葉斯框架。其中，貪婪算法因為有較快的速度和簡單的框架而被廣泛應用。貪婪算法主要包括匹配追蹤(MP)算法[6]，正交匹配追蹤(OMP)算法[7]，分段正交匹配追蹤(StOMP)算法[8]，子空間追蹤(SP)算法[9]，壓縮采樣匹配追蹤(CoSaMP)算法[10]，稀疏度自適應匹配追蹤(SAMP)算法[11]，前向預測正交匹配追蹤(LAOMP)算法[12]和前向后向匹配追蹤(Forward-Backward Pursuit, FBP)算法[13]。為了進一步提高算法性能，許多迭代[14]和融合的改進策略被應用于這些貪婪算法。

由于OMP算法沒有回溯機制，而SP算法又需要稀疏度作為先驗信息，文獻[13]提出了FBP算法。在FBP算法中，每一步迭代主要包含兩個階段：前向階段和后向階段。前向階段通過前向步長擴大估計支撐集，后向階段通過后向步長減小估計支撐集。本文提出的加速前向后向匹配追蹤(Acceleration Forward-Backward Pursuit, AFBP)算法，克服了FBP算法每次迭代只能以固定步長擴大支撐集、忽視被刪除原子質量的缺點，利用前向階段支撐集中原子的信息，對后向階段被刪除原子進行再此選入，達到自適應地決定每次迭代所增加原子數目的目的。雖然文獻[13]指出通過調節參數，可以降低FBP算法運行時間，但會導致重構精度的下降。而本文提出的加速策略則有效解決這一矛盾。

本文在第2節介紹了壓縮感知模型與FBP重構算法；第3節首先提出加速策略，然后描述 AFBP算法的具體流程；第4節為性能比較試驗，通過對1維稀疏信號和2維圖像下 AFBP 算法與 FBP 算法的仿真結果進行分析比較，說明改進算法的有效性；第5節對該加速策略進行總結。

2 壓縮感知和重構算法

2.1壓縮感知理論

標準壓縮感知測量過程可表示成式(1)形式：

2.2 傳統的前向后向匹配追蹤算法

FBP算法是一個兩階段迭代算法。該算法在不知道稀疏度的情況下，通過迭代以固定步長逐步擴大估計支撐集，最后實現對稀疏信號的逼近。表1給出了FBP算法的偽代碼。

表1 FBP算法

3 加速前向后向匹配追蹤算法

3.1加速策略

FBP算法對原子的操作主要集中在兩個階段：第一，利用相關性將原子選入支撐集；第二，依據投影系數將原子移除支撐集。本文算法在移除原子后，并不直接進入下一迭代，而是參考被移除原子在之前迭代過程中與殘差的相關性情況，從而進一步判斷該原子是否具有再次加入支撐集的資格。基于此，本文提出的算法可以實現每次迭代自適應地改變選入估計支撐集的原子個數，克服FBP算法每次迭代只能以固定步長增加估計支撐集的弊端。如果在歷次迭代中，某原子與歷次殘差的相關程度一直很高，則該原子為正確原子的概率就會很大。此時如果僅僅依據刪除階段的投影系數大小來決定原子是否應保留在支撐集，則會延緩算法的運行，甚至導致算法迭代失敗。然而，如果開辟一條選擇原子的新渠道，及時將此原子加入支撐集，則會加速算法的運行。

3.2 加速前向后向匹配追蹤算法

表2 AFBP算法

4 實驗結果及分析

4.1 1維稀疏信號重構

為了展示加速策略的優勢，本文參照文獻[13]，從準確重構概率，平均重構誤差和運行時間3方面對AFBP算法和FBP算法進行比較。測試信號的非零項分別服從高斯，均勻和常數幅度隨機符號(Constant Amplitude Random Sign, CARS)分布。其中，高斯稀疏信號非零項來自標準高斯分布。均勻稀疏信號非零項為之間的均勻分布。CARS稀疏信號非零項由單位幅度隨機符號的元素組成。在實驗中，每一稀疏信號均對應一個不同的觀測矩陣。其中觀測矩陣的元素服從均值為0，標準差為1/的高斯分布，且每一列均進行歸一化處理。為比較AFBP和FBP的運行時間，本文采用文獻[14]的設定。即通過MATLAB自帶的‘cputime’函數計算平均運行時間。為避免MATLAB采用多線程計算，本文使用MATLAB中‘singleCompThread’的選項。該選項將限制MATLAB使用單線程工作。以下為運行仿真的計算機信息。Matlab 版本：R2010b (32-bit)，操作系統：Windows (32-bit)，處理器：Intel(R) Core(TM) i5-3210M CPU @ 2.50 GHz，內存：4 GB。

圖 1 高斯稀疏信號的重構結果比較()

圖2 均勻稀疏信號的重構結果比較()

圖3 CARS稀疏信號的重構結果比較()

圖4 高斯稀疏信號的重構結果比較()

圖5 均勻稀疏信號的重構結果比較()

圖6 CARS稀疏信號的重構結果比較()

4.2參數選擇

圖7給出了高斯稀疏信號下，不同參數AFBP算法的性能比較。其中AFBP和FBP的步長參數均為。AFBP前兩類參數與上面實驗設定一致，而第3類參數設定如下：AFBP1,,,; AFBP2,,,; AFBP3,,,。由圖7可知，對于準確重構概率，AFBP算法和FBP算法均高于OMP, SP和BP。AFBP算法準確重構概率基本隨閾值增大而提升。其中，AFBP1準確重構概率在稀疏度比較大時，略低于FBP。而AFBP2和AFBP3準確重構概率一直優于FBP。對于平均歸一化最小均方誤差，不同參數AFBP均優于FBP, OMP和SP。其中，不同參數AFBP雖性能差距不明顯，但依然是AFBP3最優，AFBP1最差。BP僅是在稀疏度較大時優于AFBP。其他情況下，AFBP算法均優于其他算法。對于平均運行時間，不同參數AFBP均優于FBP。而隨著閾值降低，AFBP運行時間也相應變短。其中，AFBP1的運行時間基本與OMP和SP相當。由于BP算法運行時間過長，所以并未在圖中列出。

圖7 不同參數AFBP在高斯稀疏信號下的重構結果比較()

為保證AFBP算法準確重構概率和均方誤差均不低于FBP算法，本文推薦AFBP2的閾值參數，即閾值參數基本為左右，且。其它分布信號的參數規律與此情況類似，由于篇幅有限，不再贅述。

為進一步分析所提出加速策略，本文在圖8中展示了經加速渠道選入支撐集的原子的具體信息。由圖8可知，閾值越低，經加速渠道選入原子越多。雖然隨著閾值降低，經加速渠道選入的正確原子有所增加，但原子正確率卻有一定程度降低。此外，隨著稀疏度增加，經加速渠道選入的原子增多。可見，隨著稀疏度增大，加速效果愈加明顯。但是正確原子的數目卻在稀疏度超過39之后有所下降。由圖8(c)可知，經加速渠道選入原子的正確率在稀疏度大于30后開始下降。此稀疏度恰為FBP算法開始失敗的稀疏度。可見，加速策略性能與FBP算法性能緊密相關。雖然，稀疏度超過30后，加速策略正確率開始降低，但是由圖7可知，AFBP依然優于FBP。這是由于此時FBP算法準確率也在降低，所以總體上如果參數選擇恰當AFBP依然可以優于FBP。值得注意的是，對于AFBP1，雖然在稀疏度較低時經加速渠道選入原子的正確率偏低，但是并不影響算法的整體性能。這是因為AFBP算法繼承了FBP算法在稀疏度較低時的強大糾錯能力。由圖8可知，雖然AFBP1加速效果明顯，但是經加速渠道選入原子的正確率一直低于AFBP2和AFBP3。而AFBP3又用時過長，故推薦AFBP2的閾值參數。

圖8 不同參數AFBP在高斯稀疏信號下經加速渠道選入原子的具體信息比較()

4.32維圖像重構

為驗證AFBP對實際非零系數分布信號的重構性能，本文使用256×256的圖像‘Lena’進行實驗。實驗參數與文獻[13]類似。為將恢復問題分解一系列簡單子問題，本文首先把圖像分割為8 × 8的小塊。分割處理保證每個8×8小塊在2D的Haar小波基上是稀疏的，其中為12。即每個分塊僅保留12個最大幅度的小波系數。對于每一分塊，信號長度為64，測量值設定為32。觀測矩陣從均值為0標準差為1/的高斯分布中隨機得到，并歸一化每一列。,。AFBP與FBP的前向和后向步長均設置為：,。AFBP其他參數設置如下，，其中閾值參數遵循大小為左右且的原則。

圖9 各算法對圖像“Lena”的重構效果

5 結論

本文提出了基于壓縮感知的加速前向后向匹配追蹤重構算法，即AFBP算法。AFBP算法繼承FBP算法不需要稀疏度作為先驗信息的優點，同時引入分段思想和加速策略。在前向階段，AFBP算法利用不同權重記錄估計支撐集中新加入原子的相關性信息。在后向刪除階段，通過比較被淘汰原子的權重和相應的預設閾值，AFBP算法建立了一條原子加入估計支撐集的新渠道。前向階段的相關性權重累加和后向階段的閾值比較，確保了經該渠道加入估計支撐集的原子的準確性，從而達到在保證精度的同時加快算法運行速度目的。

參考文獻

[1] Donoho D L. Compressed sensing[J]., 2006, 52 (4): 1289-1306.doi: 10.1109/TIT.2006.871582.

[2] Candès E J, Romberg J, and Tao T. Robust uncertainty principles: Exact signal reconstruction from highly incomplete frequency information[J]., 2006, 52(2): 489-509. doi: 10.1109/TIT.2005.862083.

[3] 李鵬,王建新,曹建農. 無線傳感器網絡中基于壓縮感知和GM(1,1)的異常檢測方案[J]. 電子與信息學報, 2015, 37(7): 1586-1590. doi: 10.11999/JEIT141219.

LI Peng, WANG Jianxin, and CAO Jiannong. Abnormal event detection scheme based on compressive sensing and GM (1,1) in wireless sensor networks[J].&, 2015, 37(7): 1586-1590. doi: 10.11999/JEIT141219.

[4] 蔣明峰, 劉淵, 徐文龍, 等. 基于全變分擴展方法的壓縮感知磁共振成像算法研究[J]. 電子與信息學報, 2015, 37(11): 2608-2612. doi:10.11999/JEIT150179.

JIANG Mingfeng, LIU Yuan, XU Wenlong,. The study of compressed sensing MR image reconstruction algorithm based on the extension of total variation method[J].&, 2015, 37(11): 2608-2612. doi:10.11999/JEIT150179.

[5] QU X, HOU Y, FAN L,. Magnetic resonance image reconstruction from undersampled measurements using a patch-based nonlocal operator[J]., 2014, 18(6): 843-856. doi:10.1016/j.media.2013.09.007.

[6] Mallat S G and ZHANG Z. Matching pursuits with time-frequency dictionaries[J]., 1994, 41(12): 3397-3415. doi:10.1109/78.258082.

[7] Tropp J and Gilbert A C. Signal recovery from random measurements via orthogonal matching pursuit[J].2007, 53(12): 4655-4666. doi:10.1109/TIT.2007.909108.

[8] Donoho D L, Tsaig Y, Drori I,. Sparse solution of underdetermined systems of linear equations by stagewise orthogonal matching pursuit[J].2012,58(2): 1094-1121. doi:10.1109/ TIT.2011.2173241.

[9] DAI W and Milenkovic O. Subspace pursuit for compressive sensing signal reconstruction[J].2009, 55(5): 2230-2249. doi:10.1109/TIT.2009.2016006.

[10] Needell D and Tropp J A. CoSaMP: Iterative signal recovery from incomplete and inaccurate samples[J]., 2009, 26(3): 301-321. doi:10.1016/j.acha.2008.07.002.

[11] Do T T, Gan L, Nguyen N,. Sparsity adaptive matching pursuit algorithm for practical compressed sensing[C]. 42nd IEEE Asilomar Conference on Signals, Systems and Computers, Pacific Grove, CA, 2008: 581-587. doi:10.1109/ACSSC.2008.5074472.

[12] Chatterjee S, Sundman D, and Skoglund M. Look ahead orthogonal matching pursuit[C]. 2011 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP), Prague, Czech Republic, 2011: 4024-4027. doi:10.1109/ICASSP.2011.5947235.

[13] Karahanoglu N B and Erdogan H. Compressed sensing signal recovery via forward-backward pursuit[J]., 2013, 23(5): 1539-1548. doi:10.1016/j.dsp.2013.05.007.

[14] Ambat S K and Hari K V S. An iterative framework for sparse signal reconstruction algorithms[J]., 2015, 108: 351-364. doi:10.1016/j.sigpro.2014.09.023.

[15] Ambat S K, Chatterjee S, and Hari K V S. Progressive fusion of reconstruction algorithms for low latency applications in compressed sensing[J]., 2014, 97(7): 146-151. doi:10.1016/j.sigpro.2013. 10.019.

[16] Ambat S K, Chatterjee S, and Hari K V S. A committee machine approach for compressed sensing signal reconstruction[J]., 2014, 62(7): 1705-1717. doi:10.1109/TSP.2014.2303941.

[17] Deepa K G, Ambat S K, and Hari K V S. Modified greedy pursuits for improving sparse recovery[C]. Twentieth IEEENational Conference on Communications (NCC), Kanpur, 2014: 1-5. doi:10.1109/NCC.2014.6811370.

Acceleration Forward-backward Pursuit Algorithm Based on Compressed Sensing

WANG Feng①SUN Guiling①ZHANG Jianping②HE Jingfei①

① (,,300350,)②(,,200030,)

The Forward-Backward Pursuit (FBP) algorithm, a novel two stage greedy approach, receives wide attention due to the high reconstruction accuracy and the feature without prior information of the sparsity. However, FBP has to run more time to get a higher precision. To alleviate this drawback, this paper proposes the Acceleration Forward-Backward Pursuit (AFBP) algorithm based on Compressed Sensing (CS). In order to reduce the number of iterations, the algorithm exploits the information available in the support estimate to add the deleted atoms again. The run time of AFBP is sharply shorter than that of FBP, while the precision of AFBP is not lower than FBP. The efficacy of the proposed scheme is demonstrated by simulations using random sparse signals with different nonzero coefficient distributions and a sparse image.

Compressed Sensing (CS); Greedy algorithms; Forward-backward search; Sparse signal reconstruction

TN911.72

A

1009-5896(2016)10-2538-08

10.11999/JEIT151422

2015-12-14；改回日期：2016-05-05；網絡出版：2016-07-04

孫桂玲sungl@nankai.edu.cn

國家自然科學基金(61171140)，高等學校博士學科點專項科研基金(20130031110032)

The National Natural Science Foundation of China (61171140), The Doctoral Program of Higher Education (20130031110032)

王 鋒： 男，1990年生，博士生，研究方向為壓縮感知、無線傳感器網絡等.

孫桂玲： 女，1964年生，教授，研究方向為壓縮感知、無線傳感器網絡、信號與信息處理、信息檢測與智能控制系統等.

張健平： 男，1996年生，本科生，研究方向為無線通信.