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

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

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

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

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

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

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

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

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

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

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

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

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

1　FBP

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

算法1：FBP算法

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

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

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

迭代：k=k+1。

前向更新

后向更新

投影

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

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

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

2　OTMP算法

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

2.1OTMP算法介紹

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

算法2 OTMP算法

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

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

循環：令l=l+1，執行步驟1）～2）直到滿足迭代終止條件。

1）支撐集選?。河嬎阆嚓P值Vl=（Φ'）Trl-1，選定索引集w，使，計算支撐集選取閾值，選擇Tf使令，更新Tf=w（1:λl），合并支撐集，最后利用最小二乘法求

2.2OTMP算法分析

2.2.1預備知識

1）限制等距性質（RIP）［5］定義

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

2）引理

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

引理2［13］設那么

2.2.2σ1閾值

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

同理當l＞1

?i?supp（x），

2.3.3支撐集篩選原理

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

3　實驗

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

3.1一維信號仿真實驗

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

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

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

圖1　高斯信號重構結果

圖2　“0-1”信號重構結果

圖3　均勻信號重構結果

3.2二維圖像信號仿真實驗

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

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

圖4Lena圖像重構，其中q=45

表1q=45時，算法重構的峰值信噪比和重構時間

4結論

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

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

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

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

［4］方紅，楊海蓉.貪婪算法與壓縮感知理論［J］.自動化學報，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—），碩士生，主要研究方向為數字信號處理；

謝正光（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，Forward-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，FBP 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

國家自然科學基金面上項目（61171077）