苗英杰，崔 琛，易仁杰

(國(guó)防科技大學(xué)電子對(duì)抗學(xué)院，安徽 合肥 230037)

0 引言

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

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

1 壓縮感知理論

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

(1)

如果稀疏s∈RN×1中最多含有K個(gè)非零值，且K?N，則稱s為稀疏表示系數(shù)，與之對(duì)應(yīng)的x也被稱為K-稀疏信號(hào)，Ψ被稱為稀疏基。

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

y=Φx=ΦΨs=Θs

(2)

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

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

(3)

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

(4)

式(3)和式(4)的求解本質(zhì)上是L0范數(shù)最小化求解問題，是NP難問題，無(wú)法直接求解，但是因?yàn)樾盘?hào)具有一定的稀疏性，這就為問題的求解提供了可能。當(dāng)前這類問題的求解方法比較多，其中貪婪算法因算法結(jié)構(gòu)簡(jiǎn)單、運(yùn)算量小而頗受關(guān)注。

2 改進(jìn)的OCMP算法

2.1 OCMP算法介紹

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

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

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

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

步驟2)計(jì)算新感知矩陣各原子與當(dāng)前重構(gòu)殘差的相關(guān)性p=ΔΘT(ΘΘT)-1rt。

從上文可以看出，算法主要分為三部分：相關(guān)性計(jì)算、更新支撐集和計(jì)算殘差。算法在每次迭代時(shí)只找到一個(gè)原子添加到支撐集，對(duì)于稀疏度為K的信號(hào)，至少需要K次迭代才能恢復(fù)出原始信號(hào)。當(dāng)稀疏度K較大時(shí)，需要的重構(gòu)時(shí)間更長(zhǎng)；如果在前期的迭代循環(huán)中有錯(cuò)選的原子，在后續(xù)的過程中將一直存在，對(duì)信號(hào)的重構(gòu)性能造成影響。

2.2 OCMP算法改進(jìn)

2.2.1閾值設(shè)置

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

2.2.2二次篩選

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

2.2.3改進(jìn)算法步驟

改進(jìn)的OCMP算法步驟如下：

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

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

步驟2)計(jì)算新感知矩陣各原子與當(dāng)前重構(gòu)殘差的相關(guān)性p=ΔΘT(ΘΘT)-1rt。

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

3 仿真實(shí)驗(yàn)及結(jié)果分析

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

實(shí)驗(yàn)一α不同取值時(shí)算法重構(gòu)性能對(duì)比

圖1 不同α值對(duì)應(yīng)的算法重構(gòu)時(shí)間開銷Fig.1 The algorithm reconstruction time cost for differentαvalues

圖2 不同α值對(duì)應(yīng)的算法重構(gòu)精度Fig.2 The accuracy of algorithm reconstruction for differentαvalues

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

實(shí)驗(yàn)二不同稀疏度下信號(hào)重構(gòu)成功概率對(duì)比

圖3 不同稀疏度下的信號(hào)重構(gòu)成功概率對(duì)比Fig.3 The probability of success in refactoring compared for different sparse degree

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

實(shí)驗(yàn)三不同觀測(cè)長(zhǎng)度下信號(hào)重構(gòu)成功概率對(duì)比

圖4 不同觀測(cè)長(zhǎng)度下的信號(hào)重構(gòu)成功概率對(duì)比Fig.4 The probability of success in refactoring compared for different measurement lengths

從圖4中可以看出，在不同的觀測(cè)長(zhǎng)度下，改進(jìn)算法的重構(gòu)成功概率相比于原始算法都有較大的提升，特別是觀測(cè)長(zhǎng)度M在40～50范圍內(nèi)，重構(gòu)成功概率基本可以提高20%左右。這是因?yàn)楦倪M(jìn)算法在信號(hào)重構(gòu)的過程中引入了支撐集原子的二次篩選過程，使算法在迭代過程中更加精確的估計(jì)真實(shí)的支撐集，重構(gòu)結(jié)果更加的接近真實(shí)信號(hào)，更大概率的達(dá)到預(yù)設(shè)的重構(gòu)成功的判決條件。

實(shí)驗(yàn)四算法重構(gòu)時(shí)間開銷對(duì)比

圖5是在觀測(cè)長(zhǎng)度M=80，稀疏度變化的情況下，進(jìn)行1 000次蒙特卡洛實(shí)驗(yàn)，OCMP算法和改進(jìn)算法信號(hào)重構(gòu)所用時(shí)間的平均值。

圖5 算法運(yùn)行時(shí)間對(duì)比Fig.5 The contrast of algorithm run time

從圖5中可以看出在稀疏度K<30時(shí)，改進(jìn)算法重構(gòu)所需時(shí)間開銷相對(duì)于原始算法有所改善，這是因?yàn)楦倪M(jìn)算法在每次迭代進(jìn)行支撐集原子選擇時(shí)，滿足閾值的原子數(shù)目有時(shí)會(huì)多于1，這就會(huì)使改進(jìn)算法比原始算法更快的完成信號(hào)重構(gòu)所需支撐集的建立，只需要更少的迭代次數(shù)便可以完成信號(hào)重構(gòu)；在稀疏度K>30，改進(jìn)算法重構(gòu)所需時(shí)間多于原始算法，這是因?yàn)樵贛=80，K>30時(shí)，原始算法與改進(jìn)算法的重構(gòu)成功概率急劇下降，信號(hào)在重構(gòu)過程中若始終無(wú)法達(dá)到迭代終止條件，則強(qiáng)制性使算法完成預(yù)先設(shè)置的迭代次數(shù)才會(huì)終止，但改進(jìn)算法相對(duì)于原始算法多了模糊閾值計(jì)算和二次篩選過程，所以會(huì)使得重構(gòu)時(shí)間開銷增大，出現(xiàn)改進(jìn)算法重構(gòu)時(shí)間長(zhǎng)于原始算法重構(gòu)時(shí)間的情況。

由以上三個(gè)仿真實(shí)驗(yàn)結(jié)果分析可知，改進(jìn)算法在重構(gòu)時(shí)間開銷、重構(gòu)成功概率等方面相對(duì)于OCMP算法都有一定的優(yōu)勢(shì)。在信號(hào)的稀疏程度較低時(shí)，改進(jìn)算法的成功重構(gòu)概率仍要高于原算法，但是時(shí)間開銷會(huì)略有增加。

4 結(jié)論

本文提出了改進(jìn)的正交補(bǔ)空間匹配追蹤算法。該算法相對(duì)于OCMP算法具有更高的重構(gòu)成功概率，成功重構(gòu)所需的運(yùn)行時(shí)間有所減少。