王 鋒 孫桂玲 張健平 何靜飛

?

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

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

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

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

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

1 引言

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

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

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

2 壓縮感知和重構(gòu)算法

2.1壓縮感知理論

標(biāo)準(zhǔn)壓縮感知測量過程可表示成式(1)形式：

2.2 傳統(tǒng)的前向后向匹配追蹤算法

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

表1 FBP算法

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

3.1加速策略

FBP算法對原子的操作主要集中在兩個階段：第一，利用相關(guān)性將原子選入支撐集；第二，依據(jù)投影系數(shù)將原子移除支撐集。本文算法在移除原子后，并不直接進入下一迭代，而是參考被移除原子在之前迭代過程中與殘差的相關(guān)性情況，從而進一步判斷該原子是否具有再次加入支撐集的資格?；诖耍疚奶岢龅乃惴梢詫崿F(xiàn)每次迭代自適應(yīng)地改變選入估計支撐集的原子個數(shù)，克服FBP算法每次迭代只能以固定步長增加估計支撐集的弊端。如果在歷次迭代中，某原子與歷次殘差的相關(guān)程度一直很高，則該原子為正確原子的概率就會很大。此時如果僅僅依據(jù)刪除階段的投影系數(shù)大小來決定原子是否應(yīng)保留在支撐集，則會延緩算法的運行，甚至導(dǎo)致算法迭代失敗。然而，如果開辟一條選擇原子的新渠道，及時將此原子加入支撐集，則會加速算法的運行。

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

表2 AFBP算法

4 實驗結(jié)果及分析

4.1 1維稀疏信號重構(gòu)

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

圖 1 高斯稀疏信號的重構(gòu)結(jié)果比較()

圖2 均勻稀疏信號的重構(gòu)結(jié)果比較()

圖3 CARS稀疏信號的重構(gòu)結(jié)果比較()

圖4 高斯稀疏信號的重構(gòu)結(jié)果比較()

圖5 均勻稀疏信號的重構(gòu)結(jié)果比較()

圖6 CARS稀疏信號的重構(gòu)結(jié)果比較()

4.2參數(shù)選擇

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

圖7 不同參數(shù)AFBP在高斯稀疏信號下的重構(gòu)結(jié)果比較()

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

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

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

4.32維圖像重構(gòu)

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

圖9 各算法對圖像“Lena”的重構(gòu)效果

5 結(jié)論

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

參考文獻

[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] 李鵬,王建新,曹建農(nóng). 無線傳感器網(wǎng)絡(luò)中基于壓縮感知和GM(1,1)的異常檢測方案[J]. 電子與信息學(xué)報, 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ǐn)U展方法的壓縮感知磁共振成像算法研究[J]. 電子與信息學(xué)報, 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；網(wǎng)絡(luò)出版：2016-07-04

孫桂玲sungl@nankai.edu.cn

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

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

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

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

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