基于壓縮感知的雙向閾值匹配追蹤算法

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

（南通大學(xué)電子信息學(xué)院，江蘇南通226019）

基于壓縮感知的雙向閾值匹配追蹤算法

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

（南通大學(xué)電子信息學(xué)院，江蘇南通226019）

最近提出的前向后向算法（Forward-backward Pursuit，F(xiàn)BP）因為重構(gòu)精度較高受到人們更多關(guān)注。但是FBP算法沒有考慮到當(dāng)前迭代殘差信號的變化，每次迭代選取的原子和刪減原子的數(shù)目是固定的。鑒于此，提出了雙向閾值匹配追蹤算法（Ovonic Threshold Matching Pursuit，OTMP）。OTMP前向原子選擇過程通過限制等距性質(zhì)（RIP）和殘差的條件選出部分新增加原子，在回溯過程中通過當(dāng)前迭代的重構(gòu)水平剔除可能錯誤的原子。實驗表明，在一定條件下OTMP時間復(fù)雜度和正交匹配追蹤算法（Orthogonal Matching Pursuit，OMP），子空間追蹤算法（Subspace Pursuit，SP）相當(dāng)，重構(gòu)精度明顯高于SP，F(xiàn)BP算法和其他幾種貪婪算法。

壓縮感知；貪婪算法；原子；回溯；子空間追蹤算法；前向后向算法

【本文獻信息】黃宏偉，謝正光，蔣小燕，等.基于壓縮感知的雙向閾值匹配追蹤算法［J］.電視技術(shù)，2015，39（10）.

傳統(tǒng)信息論中，奈奎斯特（Nyqusit）指出信號的采樣速率必須大于等于信號最高頻率的兩倍才能從采樣信號完全恢復(fù)出原始信號。而這個過程伴隨著大量的冗余信息，浪費了不必要的硬件采集資源。

一種新的信號采集技術(shù)壓縮感知（Compressed Sensing，CS）［1］，因其高效的采集效率逐漸吸引人們的學(xué)習(xí)研究興趣。它采用邊采集邊壓縮的模式，在數(shù)據(jù)采集過程中就進行適當(dāng)?shù)膲嚎s，這樣能保證信號采樣速度低于奈奎斯特采樣速率，減少不必要的資源浪費［2-3］。CS理論主要內(nèi)容是可壓縮信號的少量線性投影包含了原始信號的主要信息，利用全局的線性測量可以精確重構(gòu)出原信號［4］。假設(shè)一個長度為N的一維信號x∈RN，x中非零原始個數(shù)K?N，或者在某個正交基ψ稀疏表示θ中有K個非零值，x=ψθ，CS理論框架下，信號測量過程表示為

式中：y是長度為M的觀測信號；Φ=［Φ1，Φ2，…，ΦN］是測量矩陣，大小為M×N；x為K階稀疏信號，長度為N，K＜M＜N。這個過程相當(dāng)于把原始信號x投影到［Φ1，Φ2，…，ΦN］張成的空間上，信號從N維降到M維。壓縮感知中重構(gòu)算法是核心內(nèi)容，是從測量矩陣Φ和觀測信號y中恢復(fù)原始稀疏信號x。從測量矩陣和原始信號維數(shù)可以看出式（1）是欠定的，求解原始信號是一個病態(tài)問題。但是當(dāng)原信號只有有限的非零元素時，可以精確求解x。Candes和Donoho指出當(dāng)測量矩陣和稀疏信號滿足一定條件可以求助于非線性凸優(yōu)化方法，如基追蹤（BP）進行求解。但是BP算法復(fù)雜度太高，極大影響了它的實際應(yīng)用。貪婪算法因為結(jié)構(gòu)簡單，運行速度快吸引了人們的廣泛關(guān)注。帶有回溯思想的貪婪算法因其重構(gòu)精度較高備受人們關(guān)注。根據(jù)前向原子選擇和后向原子刪除步長，算法可分為步長為恒定值的算法和步長可變的算法。步長恒定算法包括子空間追蹤算法（Subspace Pursuit，SP）［5］前向步長每次跟新K，后向刪除步長也為K；壓縮采樣匹配追蹤算法（Comprssive Sampling Matching Pursuit，CoSaMP）［6］前向步長每次跟新2K，后向刪減步長也為2K；FBP［7］算法每次迭代前向跟新步長為α，后向刪減步長為β，其中α＞β。步長變化算法包括：自適應(yīng)稀疏度匹配追蹤算法（Adaptive Sparse Matching Pursuit，ASMP）［8］前向步長根據(jù)信號相關(guān)閾值得出，不是一個固定值，后向刪減部分和SP類似，保留當(dāng)前估計信號幅值最大K的索引；自適應(yīng)閾值回溯正交匹配追蹤算法（Adaptive Threshold Backtracking OMP，ATBOMP）［9］前向步長和信號相關(guān)，通過相關(guān)性求出閾值，再根據(jù)閾值選出原子，步長是變化的，后向刪減步長是通過正則化完成的，步長也是變化的。

文獻［7］提出了前向后向追蹤算法（Forward-backward Pursuit），首先算法不需要稀疏度條件，其次算法重構(gòu)精度相對較高。大部分情況，原信號的稀疏度是未知的，因此FBP相對于OMP［10-11］，SP算法占有很大優(yōu)勢，其次FBP算法帶有回溯機制，可以在迭代過程中自主糾錯。雖然FBP算法相對于經(jīng)典的幾種算法占據(jù)優(yōu)勢，但是也存在缺點，首先是算法的時間復(fù)雜度，因為前向和后向步長是固定值，沒有考慮迭代過程中信號的變化，所以執(zhí)行效率比較低；其次算法重構(gòu)精度還是有待進一步提高。本文提出雙向閾值匹配追蹤算法（OTMP）。實驗證明，OTMP在一定條件下，重構(gòu)精度和時間復(fù)雜度均優(yōu)于FBP。

1　FBP

首先簡單說明本文涉及的符號。supp（x）表示向量x中非零元素的位置。K表示稀疏度。ΦT表示Φ的轉(zhuǎn)置，T0定義為初始的支撐集，r0表示初始的殘差，Tl表示第l次迭代得出的支撐集，||Tl表示Tl中元素個數(shù)。rl表示第l次迭代得出的信號殘差，xTl表示x對應(yīng)Tl位置上的元素集合。δK+1為K+1階RIP常數(shù)，hl=ΦTrl-1表示第l次迭代的代理信號，hl（i）=＜Φei，rl-1＞表示代理信號中的元素，其中＜·＞表示內(nèi)積運算，ei為單位矩陣的第i列。

算法1：FBP算法

輸入：測量矩陣Φ，測量向量y。

設(shè)置：前向步長α，后向步長β，最大迭代次數(shù)lmax，算法終止閾值ε。

初始化：T0=?，r0=y，k=0。

迭代：k=k+1。

前向更新

后向更新

投影

如果||rl||2≤ε||y||2或|Tl|≥lmax，迭代終止，否則繼續(xù)迭代。

迭代終止后令x?=0，x?Tl=w，輸出x?。

文獻［7］指出，當(dāng)稀疏信號中的非零元素不為一個常數(shù)值隨機信號（Constant Amplitude Random Signal，CARS）時，F(xiàn)BP重構(gòu)性能高于OMP，SP，BP算法。同時當(dāng)稀疏信號非零值取值范圍增大時，F(xiàn)BP重構(gòu)精度相對BP將更加精確。文獻還提出如果減小α，β的取值，將會減小算法運行時間，但是通過實驗結(jié)果可以發(fā)現(xiàn)時間復(fù)雜度降低是用信號重構(gòu)精度降低為代價換來的。

2　OTMP算法

FBP每次迭代選取原子的數(shù)量為一個固定的常數(shù)，而不考慮信號的性質(zhì)（準確為殘差信號性質(zhì)），其次在后向更新過程，F(xiàn)BP每次迭代刪減支撐集數(shù)量也為一個固定的常數(shù)，同樣沒有考慮迭代過程中信號的變化。FBP執(zhí)行效率比較低；其次算法重構(gòu)精度還是有待進一步提高。鑒于FBP缺點，本文提出OTMP。

2.1OTMP算法介紹

OTMP在支撐集選取過程充分考慮殘差信號的特點選取滿足條件的原子，隨后把選出的原子加入到候選支撐集中。在原子篩選過程，首先計算測量向量y在候選支撐集張成空間上的正交投影，然后在所有投影系數(shù)中找出當(dāng)前迭代新添加支撐集上的投影系數(shù)，并求和篩選閾值σ2，最后根據(jù)所求閾值剔除可能錯誤的原子。

算法2 OTMP算法

輸入：測量矩陣Φ，測量向量y，最大迭代次數(shù)lmax，迭代終止閾值ε；

初始化：迭代次數(shù)l=0，殘差r0=y，估計支撐集，原信號非零值估計

循環(huán)：令l=l+1，執(zhí)行步驟1）～2）直到滿足迭代終止條件。

1）支撐集選取：計算相關(guān)值Vl=（Φ'）Trl-1，選定索引集w，使，計算支撐集選取閾值，選擇Tf使令，更新Tf=w（1:λl），合并支撐集，最后利用最小二乘法求

2.2OTMP算法分析

2.2.1預(yù)備知識

1）限制等距性質(zhì)（RIP）［5］定義

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

2）引理

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

引理2［13］設(shè)那么

2.2.2σ1閾值

當(dāng)l=1，貪婪算法大部分是通過代理信號的幅值選擇原子。假設(shè)矩陣Φ∈RM×N滿足參數(shù)為（K，δ）的有限等距性質(zhì)，根據(jù)引理2有：

同理當(dāng)l＞1

?i?supp（x），

2.3.3支撐集篩選原理

由于測量矩陣不是完全正交，因此通過支撐集選取過程得出候選原子并非一定完全正確。OTMP通過當(dāng)前迭代產(chǎn)生的進行原子篩選，從物理意義上可理解為當(dāng)前迭代選出原子的重構(gòu)水平。如果本次迭代之前產(chǎn)生的正交投影系數(shù)幅值小于當(dāng)前迭代重構(gòu)水平（篩選閾值σ2需要當(dāng)前重構(gòu)水平乘以μ），那么可以認為之前選擇的原子是錯誤的。通過這個原理可以剔除部分錯誤原子。隨著迭代過程，原子不斷被選入支撐集，當(dāng)殘差rl充分小或者迭代達最大次數(shù)lmax，算法終止，輸出估計信號x?。

3　實驗

本文基于MATLAB仿真平臺，對一維信號和二維信號都進行了相關(guān)實驗。在一維信號部分，選擇了三種不同類型的稀疏信號分別為高斯信號，“0-1”信號和均勻分布信號。二維信號則是標準的256×256的Lena測試圖像。測量矩陣Φ的元素服從均值為0，方差為的高斯分布。

3.1一維信號仿真實驗

測量次數(shù)M=128，信號長度N=256。稀疏度K取值應(yīng)該滿足K≤M/2。OMP和OTMP迭代停止閾值相同，均取ε=10-6，OTMP的最大迭代次數(shù)lmax=M，δ'=0.1（δ'是δK+1所求值放縮后的取值，這里不表示RIP常數(shù)），μ=0.18。BP算法重構(gòu)是通過cvx工具箱實現(xiàn)的。FBP算法給前長步分別為α=30、20、2與之對應(yīng)的后退步長β=29，19，1。停止閾值ε=10-6，最大迭代次數(shù)lmax=M/2。重構(gòu)成功條件：，重建誤差用平均歸一化最小均方誤差（Average Normalized Mean-Squared-Error，ANMSE）來表示均方誤差，其中500表示獨立的500次實驗。

圖1表示不同稀疏度條件下，各種算法對高斯信號重構(gòu)效果。圖1的第2幅曲線表示重構(gòu)百分比和稀疏度之間關(guān)系，它可以衡量算法的穩(wěn)定性。稀疏度較小時，所有算法都能保證100%重構(gòu)出原信號。隨著稀疏度不斷增大，部分算法開始出現(xiàn)重構(gòu)失敗情況，而出現(xiàn)失敗的臨界點對算法評價具有重要意義。從曲線不難看出OMP算法在K=30之前就出現(xiàn)失敗情況（為了突出重點，截去原曲線的前面部分內(nèi)容），當(dāng)K≥35，BP開始出現(xiàn)重構(gòu)失敗情況；當(dāng)K≥43，F(xiàn)BP（2，1）開始出現(xiàn)重構(gòu)失?。籏≥45，F(xiàn)BP（20，19）和FBP（30，29）也出現(xiàn)失敗情況。但是對于OTMP，只有當(dāng)K≥56才出現(xiàn)重構(gòu)失敗情況，而且當(dāng)K=61時其他算法重構(gòu)概率幾乎都降到0，OTMP卻依然保持96%左右的水平。圖1第3幅圖表示重構(gòu)的均方誤差，它可以衡量算法重構(gòu)的精確性，從圖中可以明顯看出OTMP重構(gòu)的均方誤差低于其他任何一種算法，而且在整個稀疏度區(qū)間都保持較低的值。最后分析圖1的第1幅圖，它表示重構(gòu)時間和稀疏度之間的關(guān)系。OTMP算法在稀疏度1～51區(qū)間保持較低的運行時間，略高于OMP，SP，從K=51開始，隨著稀疏度增加算法運行時間增長很快，當(dāng)K=61，運行時間已經(jīng)超過FBP（2，1）情況。但是從另一方面來看，如果只關(guān)心開始出現(xiàn)重構(gòu)失敗的臨界點之前所有稀疏度對應(yīng)的重構(gòu)性能，OTMP時間復(fù)雜度相對于FBP還是較低的。

圖2表示不同稀疏度條件下，各種算法對“0-1”信號重構(gòu)效果。圖2中間曲線可以看出，稀疏度K取26～28左右，F(xiàn)BP出現(xiàn)重構(gòu)失敗現(xiàn)象，SP在K≥29出現(xiàn)失敗，而OTMP重構(gòu)100%重構(gòu)一直保持到K=36左右，這和BP算法十分相近。圖2右邊曲線表示重構(gòu)的均方誤差，OTMP重構(gòu)誤差僅次于BP算法，明顯優(yōu)于其他所有算法。最后在分析算法的時間復(fù)雜度，和高斯信號結(jié)果相似，在稀疏度相對較小時，OTMP保持較低的重構(gòu)時間，與SP，OMP相當(dāng)。但是當(dāng)K=35時，隨著稀疏繼續(xù)增大，OTMP運行時間增長十分迅速，到K=40時，重構(gòu)時間已經(jīng)超過所有算法（不考慮BP時間）。同樣，如果只關(guān)心開始出現(xiàn)重構(gòu)失敗的臨界點之前所有稀疏度對應(yīng)的重構(gòu)性能，OTMP重構(gòu)時間還是比較低的。最后是圖3的均勻信號重構(gòu)情況，性能分析與高斯信號相似，這里不再贅述。

圖1　高斯信號重構(gòu)結(jié)果

圖2　“0-1”信號重構(gòu)結(jié)果

圖3　均勻信號重構(gòu)結(jié)果

3.2二維圖像信號仿真實驗

為了衡量算法對圖像信號重構(gòu)性能，選擇標準的256×256Lena測試圖像。首先對圖像信號進行小波變換，選擇sym6小波基。保留小波變換后系數(shù)矩陣每列最大的q個小波系數(shù)，其余置零。計算：重構(gòu)的精度上OTMP的PSNR為34.4 dB，在其他所有算法中最大，即重構(gòu)最精確；重構(gòu)時間上OTMP的TIME是3.1 s，在其他所有算法中最小，即重構(gòu)最快。二維圖像經(jīng)過二維小波變換，得出一系列小波系數(shù)，然后取出每列中最大的q個系數(shù)，其余置零，這樣一方面可以節(jié)約重構(gòu)時間，另一方面可以降低小的小波系數(shù)對重構(gòu)的影響，即可提高重構(gòu)精度，經(jīng)過這樣處理，圖像信號每列的小波系數(shù)變?yōu)閲栏?，且稀疏度已知的一維信號。對于一維信號，仿真結(jié)果顯示，信號稀疏度在相對較小時，OTMP重構(gòu)的均方誤差很小，同時重構(gòu)時間很短，接近SP，OMP。在二維實驗中q取45對應(yīng)OTMP算法參數(shù)設(shè)置與一維信號相同。

圖4和表1反映了q=45條件下，幾種算法重構(gòu)結(jié)果。稀疏較小，所以不僅能精確重構(gòu)而且重構(gòu)所需時間很短。因此OTMP算法在二維圖像信號重構(gòu)上性能相比其他算法更加優(yōu)越。

圖4Lena圖像重構(gòu)，其中q=45

表1q=45時，算法重構(gòu)的峰值信噪比和重構(gòu)時間

4結(jié)論

本文提出一種新的貪婪重構(gòu)算法雙閾值匹配追蹤算法OTMP。OTMP算法迭代有兩個過程，支撐集選取和支撐集篩選。在支撐集選取過程，通過RIP性質(zhì)和信號殘差求出原子選擇閾值，然后根據(jù)閾值選擇滿足條件的所有原子；在支撐集篩選步驟，通過當(dāng)前迭代產(chǎn)生的或者進行原子篩選。實驗仿真結(jié)果表明，對于高斯信號，OTMP重構(gòu)精度高于包括FBP算法在內(nèi)的所有算法，在整個稀疏度取值區(qū)間，重構(gòu)誤差保持在一個非常低的水平；對于“0-1”信號，OTMP算法重構(gòu)效果明顯高于其他貪婪算法，接近BP；對于二維圖像信號，OTMP不僅重構(gòu)精度高于其他所有算法，而且重構(gòu)時間最短。

［1］CANDES E J，WAKIN M B.An introduction to compressive sampling［J］.IEEE Signal Processing Magazine，2008，25（2）：21-30.

［2］石光明，劉丹華，高大化，等.壓縮感知理論及其研究進展［J］.電子學(xué)報，2009，37（5）：1070-1081.

［3］戴瓊海，付長軍，季向陽.壓縮感知研究［J］.計算機學(xué)報，2011，34（3）425-434.

［4］方紅，楊海蓉.貪婪算法與壓縮感知理論［J］.自動化學(xué)報，2011，37（12）：1413-1421.

［5］DAI W，MILENKOVIC O.Subspace pursuit for compressive sensing signal reconstruction［J］.IEEE Trans.Information Theory，2009，55（5）：2230-2249.

［6］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.

［7］KARAHANOGLU N B，ERDOGAN H.Compressed sensing signal recovery via forward-backward pursuit［J］.Digital Signal Processing，2013，23（5）：1539-1548.

［8］WU H，WANG S.Adaptive sparsity matching pursuit algorithm for sparse reconstruction［J］.IEEE Signal Processing Letters，2012，19（8）：471-474.

［9］HAO Z，GONG Z.Adaptive threshold backtracking matching pursuit for compressive sensing［C］//Proc.Radar Conference 2013.［S. l.］：IET Press，2013：1-4.

［10］TROPP J A，GILBERT A C.Signal recovery from random measurements via orthogonal matching pursuit［J］.IEEE Trans.Information Theory，2007，53（12）：4655-4666.

［11］WU R，HUANG W，CHEN D R.The exact support recovery of sparse signals with noise via orthogonal matching pursuit［J］. IEEE Signal Processing Letters，2013，20（4）：403-406.

［12］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.

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

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

黃宏偉（1989—），碩士生，主要研究方向為數(shù)字信號處理；

謝正光（1967—），博士，教授，主要研究方向為智能信息處理、圖像視頻信號處理與傳輸；

蔣小燕（1989—），女，碩士生，主要研究方向為信號處理。

蔡旭（1990—），碩士生，主要研究方向為信號處理。

Ovonic Threshold Matching Pursuit for Sparse Signal Reconstruction Based on Compressed Sensing

HUANG Hongwei，XIE Zhengguang，JIANG Xiaoyan，CAI Xu
（School of Electronics and Information，Nantong University，Jiangsu Nantong 226019，China）

Due to high accuracy in signal reconstruction，F(xiàn)orward-backward Pursuit algorithm（FBP）has received more attention.However，the change of residual signal is not considered，and the number of atoms selected in each iteration is a constant.As a result，Ovonic Threshold Matching Pursuit（OTMP）is put up.On the one hand，OTMP tries to pick out part new atoms by Restricted Isometry Property and residual condition in the forward atom selection process.On the other hand，based on reconstruction level of current iteration，some atoms which are probably wrong are deleted.The experimental result shows that under certain condition，time complexity of OTMP is comparable with OMP，SP.Meanwhile，the reconstruction accuracy of OTMP surpasses SP，F(xiàn)BP and other greedy algorithms obviously.

compressed sensing；greedy algorithm；atom；backtracking；SP；FBP

TN911.73

A

10.16280/j.videoe.2015.10.002

時雯

2014-08-08

國家自然科學(xué)基金面上項目（61171077）