改進的正交補空間匹配追蹤算法

苗英杰，崔 琛，易仁杰

(國防科技大學電子對抗學院，安徽 合肥 230037)

0 引言

壓縮感知理論[1-3](Compressed Sensing，CS)是近些年被提出的一種信號處理理論，它突破了傳統的奈奎斯特采樣定理的限制，充分利用了信號的稀疏性來獲取和處理信號[4]。作為一種新的信號處理理論，為信號的數字化過程提供了一種新的選擇。CS理論指出：如果信號是稀疏的或可壓縮的，便可以利用特定的觀測矩陣將高維信號線性投影到一個低維空間，并且不會造成信號中的重要信息丟失，最后通過求解一個優化問題可以從低維觀測向量中高概率精確重構出原始信號。目前CS理論的研究主要集中在信號的稀疏變換、觀測矩陣設計和信號重構等方面，其中重構算法關系到信號重構精度的高低、時間開銷的大小。重構性能的好壞直接影響著壓縮感知的實用性。

目前重構算法主要分為三類[5]：凸松弛算法、貪婪算法和組合算法。凸松弛重構算法重構效果好，但是計算復雜度高，導致重構時間較長；組合算法重構時間短，但重構結果不夠準確；貪婪算法兼顧了運行效率與重構精度，因其算法結構簡單、運算量小等特點受到青睞。在近些年諸多學者的研究中逐步的發展和完善，同時衍生出了一系列的改進算法。貪婪類重構算法中的補空間匹配追蹤[6-7](Complementary Matching Pursuit，CMP)是針對匹配追蹤[8](Matching Pursuit，MP)算法信號重建誤差過大的問題提出的一種改進算法。CMP算法不同于MP算法，它是在系數空間而不是在信號空間實現的，可以獲得比MP算法更稀疏、誤差更小的逼近信號。正交補空間匹配追蹤(Orthogonal Complementary Matching Pursuit，OCMP)算法是在CMP算法基礎上的一種改進，類似于OMP[9](Orthogonal Matching Pursuit，OMP)針對MP算法的改進。本文根據上述研究，提出了改進的正交補空間匹配追蹤算法。

1 壓縮感知理論

假設離散信號x∈RN×1中至多含有K個非零值，即‖x‖0≤K，如果滿足K?N，則稱信號x為K-稀疏的。然而在實際應用中的信號x本身一般是非稀疏的，但是對x在某個變換域Ψ∈RN×N中做如下變換：

(1)

如果稀疏s∈RN×1中最多含有K個非零值，且K?N，則稱s為稀疏表示系數，與之對應的x也被稱為K-稀疏信號，Ψ被稱為稀疏基。

針對信號x，CS利用符合一定條件的觀測矩陣將高維信號投影到低維空間中，觀測過程如下式：

y=Φx=ΦΨs=Θs

(2)

式(2)中，x為原始信號，s為x在稀疏基Ψ下的稀疏表示系數，Φ∈RM×N為觀測矩陣，y∈RM×1為觀測向量，Θ=ΦΨ稱為感知矩陣。

由觀測向量y求解出稀疏表示系數s的過程稱為重構。如何從觀測向量y中求解出稀疏表示系數s，間接得到原始信號x正是本文要解決的問題，此問題的求解通常采用如下最優化問題求解：

(3)

考慮到實際中允許存在一定程度的誤差，求解式(3)的最優化問題可用一個簡單的近似求解形式替代，如式(4)，其中e是一個非常小的常量：

(4)

式(3)和式(4)的求解本質上是L0范數最小化求解問題，是NP難問題，無法直接求解，但是因為信號具有一定的稀疏性，這就為問題的求解提供了可能。當前這類問題的求解方法比較多，其中貪婪算法因算法結構簡單、運算量小而頗受關注。

2 改進的OCMP算法

2.1 OCMP算法介紹

OCMP算法是在CMP算法基礎上改進的一種算法。CMP算法類似于MP，但是與其不同的是CMP算法直接在原始信號x的行空間上進行求解。在每次迭代中，MP算法是從觀測矩陣中選擇一個最匹配的原子；而CMP算法則是刪除(N-1)個不匹配的原子并保留剩下的一個最匹配的原子。CMP算法對觀測矩陣進行了變換，此時算法求解空間不是在觀測矩陣張成的M維空間，而是位于信號x所在的N維空間，因此在原子選擇方式上CMP算法要比MP算法復雜。盡管從觀測矩陣選擇行空間上的解并不一定是最優的，殘差不一定與所選原子正交，但是文獻[10]中仿真實驗結果表明，相比于MP算法，通過CMP算法重構出的信號稀疏性更好、誤差更小。OCMP算法是針對CMP所選原子不具有正交性的特點，結合OMP算法正交化思想提出的一種改進算法，從而使算法在后續迭代中不會選擇已經選擇過的原子，保證了所選原子的最優性。

OCMP算法在原子選擇上與CMP算法一樣，然后通過選定的支撐集采用最小二乘法求解信號。假設原始信號x是稀疏的，此時稀疏變換矩陣可以看作單位陣，算法的步驟如下：

輸入：稀疏度K，感知矩陣Θ∈RM×N，觀測向量y∈RM×1。

初始化：初始化迭代次數t=1，重構殘差rt=y，支撐集Λ0=?，新感知矩陣F=Θ?Θ，新測量信號x′=Θ?y，其中Θ?=ΘT(ΘΘT)-1為Θ的偽逆。

步驟2)計算新感知矩陣各原子與當前重構殘差的相關性p=ΔΘT(ΘΘT)-1rt。

從上文可以看出，算法主要分為三部分：相關性計算、更新支撐集和計算殘差。算法在每次迭代時只找到一個原子添加到支撐集，對于稀疏度為K的信號，至少需要K次迭代才能恢復出原始信號。當稀疏度K較大時，需要的重構時間更長；如果在前期的迭代循環中有錯選的原子，在后續的過程中將一直存在，對信號的重構性能造成影響。

2.2 OCMP算法改進

2.2.1閾值設置

OCMP算法在迭代過程中每次選擇一個原子擴充到支撐集，對于K稀疏信號至少需要K次迭代才可以完成信號的重構，當信號的稀疏度較大時則需要更多的迭代次數，算法重構所需的時間也會大大增加。針對這一問題，本文算法利用模糊閾值法進行支撐集原子的篩選。在每次迭代計算得到的內積向量中，以最大值的α倍作為閾值γ0，在內積向量中找到數值大于閾值γ0的原子集即S={|p[i]|≥α·|pmax|,i=1,2，…,N}，并對該原子集中的元素求均值即γ=sum(|S|)/L(S)(sum(|S|)表示原子集S中所有元素的絕對值之和，L(S)表示原子集S的長度)，以計算結果γ作為篩選支撐集原子的閾值，選出符合條件的原子加入支撐集進行信號的重構。其中0<α≤1，α值的選擇由經驗確定，取值過大，通過閾值γ0篩選得到的原子集原子過少，導致閾值γ過大，達不到原子篩選的目的；α的取值過小，通過閾值γ0篩選得到的原子集原子較多，引入部分相關性較小的原子，使得閾值γ的值較小，導致支撐集原子的篩選中引入過多的不匹配原子，增加算法的運算量，對信號的重構精度也會造成一定的影響。

2.2.2二次篩選

OCMP算法每次篩選出一個原子加入支撐集，在后續的迭代中只是不斷的加入新的原子向真實支撐集逼近，對于錯誤匹配的原子，則將會一直存在支撐集中，對信號的重構性能造成影響。針對這一問題，改進算法引入回溯篩選[11-13]的思想：算法在每次迭代中選擇符合條件的若干個原子加入支撐集Λ0，當支撐集的原子數大于K時，說明當前支撐集中一定有錯誤選擇的原子，則選取當前的信號稀疏逼近結果x0中絕對值最大的K個分量對應的原子，將其余原子從支撐集中刪除，支撐集Λ0中只保留這K個原子。再用修正后的支撐集求取所要恢復的信號的近似解，重新計算重構殘差，若達不到迭代終止條件，則在后續的迭代過程中繼續向支撐集中加入符合條件的原子，同時進行上述支撐集修正過程，直到達到迭代終止條件或完成預設迭代次數后跳出循環并輸出重構信號。該方法保證了所選原子的準確性，從而保證了算法的重構精度，進一步提高信號的成功重構概率。

2.2.3改進算法步驟

改進的OCMP算法步驟如下：

輸入：稀疏度K，感知矩陣Θ∈RM×N，觀測向量y∈RM×1。

初始化：初始化迭代次數t=1，重構殘差rt=y，支撐集Λ0=?，新感知矩陣F=Θ?Θ，新測量信號x′=Θ?y，其中Θ?=ΘT(ΘΘT)-1為Θ的偽逆。

步驟2)計算新感知矩陣各原子與當前重構殘差的相關性p=ΔΘT(ΘΘT)-1rt。

步驟4)由最小二乘法求信號的近似解x0=(FΛ0)?x′。

3 仿真實驗及結果分析

為檢驗本文所提算法的重構性能，實驗中將OCMP算法和改進算法進行對比，算法在ThinkPad E450機器上運行，軟件版本為Matlab R2015a。實驗以重構殘差‖r‖2<10-6作為迭代終止條件，以隨機產生的、稀疏的離散高斯信號為原始信號，設信號長度N=256，以M×N維的高斯隨機矩陣作為觀測矩陣[14](此時稀疏字典可以看作是一個單位矩陣，觀測矩陣與傳感矩陣相同)。

實驗一α不同取值時算法重構性能對比

圖1 不同α值對應的算法重構時間開銷Fig.1 The algorithm reconstruction time cost for differentαvalues

圖2 不同α值對應的算法重構精度Fig.2 The accuracy of algorithm reconstruction for differentαvalues

從圖1和圖2中可以看出，當α取值較小時，算法的重構精度較差；當α取值較大時，算法的時間開銷較大。為了兼顧算法重構精度與重構速度，本文將α值取為0.7。如果在允許犧牲一定重構精度的情況下，可以通過適當減小α的取值來擴大每次迭代中支撐集增加的原子數目，加快信號的重構速度。

實驗二不同稀疏度下信號重構成功概率對比

圖3 不同稀疏度下的信號重構成功概率對比Fig.3 The probability of success in refactoring compared for different sparse degree

從圖3中可以看出，在不同的稀疏度下，改進算法的重構成功概率相比于原始算法都有所提高，特別是在稀疏度在25～35的范圍內，重構成功概率基本可以提高20%左右。其原因是在稀疏度比較低時，改進算法和原始算法基本都可以達到預設的成功重構判決條件，因此在稀疏度小于25時，兩算法的成功重構概率相差不大；在稀疏度保持一定水平時，改進算法中引入對支撐集原子的二次篩選過程，使得對支撐集的估計更加精確，重構誤差更小，可以更大程度的滿足成功重構的條件；在稀疏度較大時，原算法與改進算法的重構誤差都比較大，很難達到成功重構的條件，但是改進算法的支撐集更加接近真實支撐集，所以圖3中稀疏度大于35時，雖然改進算法與原始算法的成功重構概率相差不大，但也略有優勢。

實驗三不同觀測長度下信號重構成功概率對比

圖4 不同觀測長度下的信號重構成功概率對比Fig.4 The probability of success in refactoring compared for different measurement lengths

從圖4中可以看出，在不同的觀測長度下，改進算法的重構成功概率相比于原始算法都有較大的提升，特別是觀測長度M在40～50范圍內，重構成功概率基本可以提高20%左右。這是因為改進算法在信號重構的過程中引入了支撐集原子的二次篩選過程，使算法在迭代過程中更加精確的估計真實的支撐集，重構結果更加的接近真實信號，更大概率的達到預設的重構成功的判決條件。

實驗四算法重構時間開銷對比

圖5是在觀測長度M=80，稀疏度變化的情況下，進行1 000次蒙特卡洛實驗，OCMP算法和改進算法信號重構所用時間的平均值。

圖5 算法運行時間對比Fig.5 The contrast of algorithm run time

從圖5中可以看出在稀疏度K<30時，改進算法重構所需時間開銷相對于原始算法有所改善，這是因為改進算法在每次迭代進行支撐集原子選擇時，滿足閾值的原子數目有時會多于1，這就會使改進算法比原始算法更快的完成信號重構所需支撐集的建立，只需要更少的迭代次數便可以完成信號重構；在稀疏度K>30，改進算法重構所需時間多于原始算法，這是因為在M=80，K>30時，原始算法與改進算法的重構成功概率急劇下降，信號在重構過程中若始終無法達到迭代終止條件，則強制性使算法完成預先設置的迭代次數才會終止，但改進算法相對于原始算法多了模糊閾值計算和二次篩選過程，所以會使得重構時間開銷增大，出現改進算法重構時間長于原始算法重構時間的情況。

由以上三個仿真實驗結果分析可知，改進算法在重構時間開銷、重構成功概率等方面相對于OCMP算法都有一定的優勢。在信號的稀疏程度較低時，改進算法的成功重構概率仍要高于原算法，但是時間開銷會略有增加。

4 結論

本文提出了改進的正交補空間匹配追蹤算法。該算法相對于OCMP算法具有更高的重構成功概率，成功重構所需的運行時間有所減少。