張連娜,張慧萍,李榮鵬,宋學力

(長安大學理學院,陜西 西安 710064)

0 引 言

基于奈奎斯特采樣定理的傳統(tǒng)信號處理方式存在數(shù)據(jù)處理效率低、資源浪費嚴重等問題。壓縮感知[1]是一種新型的信號采樣及重構(gòu)理論，能夠在遠低于奈奎斯特采樣率的條件下重構(gòu)出原始稀疏信號，在核磁共振成像[2]、無線通信[3]和模式識別[4]等領域具有十分廣泛的應用。壓縮感知理論主要包括信號的稀疏表示、觀測矩陣的設定和信號重構(gòu)3個部分[1]，其中信號重構(gòu)是指從較少的觀測值中精確重構(gòu)出原始稀疏信號。高效的信號重構(gòu)算法是壓縮感知由理論轉(zhuǎn)向?qū)嶋H應用的樞紐，因此信號重構(gòu)的研究具有重要的實際意義。

現(xiàn)有的信號重構(gòu)算法主要有凸松弛算法、非凸松弛算法和貪婪算法等。凸松弛算法是將稀疏條件下的欠定線性問題轉(zhuǎn)化為凸問題，如基追蹤方法[5]、內(nèi)點法[6]和梯度投影法[7]等。凸松弛算法所需的觀測值較少，但其計算復雜度較高，算法收斂速度慢,不適合求解大規(guī)模問題。非凸松弛算法是通過構(gòu)造近似l0范數(shù)的函數(shù)來恢復稀疏信號，如光滑l0算法[8]、逐次凹稀疏逼近算法[9]和非凸復合稀疏基算法[10]等。非凸松弛算法重構(gòu)精度高，但其函數(shù)較為復雜，計算速度較慢，不適用于復雜的實際問題。貪婪算法利用內(nèi)積匹配準則選取感知矩陣與信號殘差相關性最大的原子，組成信號的支撐集，然后以支撐集為基礎根據(jù)最小二乘法估計原始稀疏信號。貪婪算法因其算法理論簡單、計算量小等優(yōu)點備受關注。傳統(tǒng)的貪婪算法有匹配追蹤算法[11](Matching Pursuit, MP)、正交匹配追蹤算法[12-13](Orthogonal Matching Pursuit, OMP)、正則化正交匹配追蹤算法[14](Regularization Orthogonal Matching Pursuit, ROMP)、壓縮采樣匹配追蹤算法[15](Compression Sample Match Pursuit, CoSaMP)、子空間追蹤算法[16](Subspace Pursuit, SP)和廣義正交匹配追蹤算法[17](Generalized Orthogonal Matching Pursuit, GOMP)等。GOMP算法是基于OMP算法改進的，該算法在每次迭代時選取S個匹配原子，其中S是小于稀疏度K的一個固定常數(shù)。GOMP算法加快了原子選取速度，減少了迭代次數(shù)，降低了計算復雜度，因此該算法應用較為廣泛。為了剔除GOMP算法支撐集中的錯誤原子，減小算法的計算代價，2017年，Zhao等人[18]提出了回溯廣義正交匹配追蹤算法(Backtracking Generalized Orthogonal Matching Pursuit, BGOMP)，將SP算法中的回溯過程引入到GOMP算法中，提高了算法的重構(gòu)精度。

然而，BGOMP算法仍存在不足，即算法在原子識別過程中，利用內(nèi)積匹配準則進行相似性度量時，內(nèi)積匹配準則側(cè)重于從方向的角度區(qū)別2個向量的差異，但對絕對數(shù)值不敏感，無法完整利用2個向量的原始信息，影響原子選取的準確率。廣義Jaccard系數(shù)準則在分母中將2個向量的相同部分去掉，凸顯了2個向量差異部分，從而將向量元素的作用效果放大，使得原子不容易混淆。因此，本文為了既保留內(nèi)積匹配準則利用方向?qū)ο蛄窟M行相似性度量的優(yōu)勢，同時利用廣義Jaccard系數(shù)準則彌補內(nèi)積準則對數(shù)值不敏感的缺陷，提出一種基于二次篩選的回溯廣義正交匹配追蹤算法,該算法首先采用內(nèi)積匹配準則選取較大數(shù)目的相關原子，再利用廣義Jaccard系數(shù)準則對已選出的原子進行二次篩選，選出其中最優(yōu)的匹配原子，優(yōu)化原子選取方式。在仿真實驗中，通過與其他貪婪算法對比，驗證了本文提出的算法在重構(gòu)誤差和重構(gòu)成功率方面效果更好。

1 壓縮感知理論模型

壓縮感知理論是指從較少的觀測值中恢復原始的稀疏信號。但實際應用中，不是所有的信號都是稀疏的，因此考慮將信號f轉(zhuǎn)換到某些線性基Ψ上，使其變?yōu)橄∈栊盘?，計算公式為?/p>

(1)

其中，Ψ=[φ1,φ2,…,φN]是N×N維的稀疏矩陣，x=[x1,x2,…,xN]T是稀疏度為K的N×1維稀疏信號，即向量x中只有K個不為0的值。

然后利用預設的投影矩陣Φ，將高維信號投影到一個低維空間上，計算公式為：

y=Φf

(2)

其中，Φ為M×N(M

結(jié)合公式(1)和公式(2)可得：

y=Φf=ΦΨx=Ax

(3)

其中，A=ΦΨ是M×N維的感知矩陣。感知矩陣A需滿足有限等距性質(zhì)[19-20](Restricted Isometry Property, RIP)，即若K階向量x∈RN和常數(shù)0<δk<1滿足式(4)：

(1-δk)‖x‖2≤‖Ax‖≤(1+δk)‖x‖2

(4)

則稱感知矩陣A符合RIP特性。

信號重構(gòu)是指從觀測得到的M維信號y中重構(gòu)出完整的N維的原始信號x。由于x具有稀疏性，信號重構(gòu)可轉(zhuǎn)化為l0范數(shù)問題來求解[18]，計算公式為：

(5)

關于公式(5)的求解，典型的貪婪算法有OMP，ROMP、SP、GOMP等算法，貪婪算法的基本思想是在每次迭代時根據(jù)感知矩陣和信號殘差的相關性，選取感知矩陣A中相關性最大的列向量(原子)加入到支撐集中，再根據(jù)支撐集中的原子利用最小二乘法恢復原始信號。

2 回溯廣義正交匹配追蹤算法

2017年，Zhao等人[18]對GOMP算法進行了改進，提出了回溯廣義正交匹配追蹤算法。該算法在估計稀疏信號和更新殘差步驟之間加入了回溯過程，對支撐集中的原子重新進行判斷，每次迭代時選取支撐集中的K個較大元素對應的原子來進行后面的殘差更新，剔除其中的錯誤原子，從而減小了計算代價，有效地提高了算法的重構(gòu)精度。

回溯廣義正交匹配追蹤算法具體步驟如下所示，其中AΛt?是指AΛt的偽逆。迭代停止條件中t=M/S是為了使支撐集中原子構(gòu)成的矩陣滿足列滿秩[18]。

輸入：測量值y，感知矩陣A，稀疏度K，正整數(shù)S

初始化：迭代次數(shù)t=1，初始殘差r0=y，支撐集Λ0=?

算法具體步驟：

1)原子識別。

計算，從||中選取S個最大元素相對應的原子，并記下它們的原子序號{λ(i)}i=1,2,…,S。

2)擴大支撐集。

Λt=Λt-1∪{λ(1),λ(2),…,λ(S)}

3)利用最小二乘法估計稀疏信號。

4)回溯。

5)更新殘差。

6)當t≥min{K,M/S}或‖rt‖2<ε時，停止迭代，否則t=t+1，返回步驟1。

3 基于二次篩選的回溯廣義正交匹配追蹤算法

回溯廣義正交匹配追蹤算法在原子識別過程中采用內(nèi)積匹配準則進行相似性度量。內(nèi)積準則實際上求的是2個向量的夾角余弦值，側(cè)重于從方向的角度計算相似度，相似度和向量的余弦值呈正相關，2個向量越相似，余弦值越大。內(nèi)積準則的表達式為：

(6)

由公式(6)可以看出，內(nèi)積準則將向量歸一化，導致在計算相似度時數(shù)據(jù)重要的部分不夠突出，因此利用內(nèi)積準則在原子識別過程中可能會導致信號重要信息的丟失[22]，進而使得原子相關性計算不準確，影響重構(gòu)效果。

為了提高原子選取的準確率，本文考慮在內(nèi)積準則的基礎上再利用廣義Jaccard系數(shù)準則對原子進行二次篩選。廣義Jaccard系數(shù)[23-24]也是對2個向量x,y之間相似度的一種衡量，它的表達式為：

(7)

其中，x=(x1,x2,…,xn)，y=(y1,y2,…,yn)。

由公式(7)可以看出，它的分母是2個向量模的平方和減去這2個向量的乘積，即將2個向量相同的部分去掉，從而增大了2個向量的差異，將其中各個元素的作用效果放大，原子變得不容易混淆，避免了信號重要信息的丟失，對支撐集進行了優(yōu)化，進而實現(xiàn)了重構(gòu)精度的提高。

為了驗證二次篩選的可行性和有效性，本文分別利用內(nèi)積準則，廣義Jaccard系數(shù)準則以及利用2種準則進行二次篩選作為相關性度量方法來判斷感知矩陣與殘差信號的相關性，選取最佳原子。實驗選取256×1維的稀疏隨機信號，稀疏度K=40，感知矩陣為128×256的隨機高斯矩陣。在這3種相關性度量方法下，殘差向量的模隨迭代次數(shù)的變化情況如圖1所示。

圖1 不同匹配準則對殘差的影響

由圖1可以看出，隨著迭代次數(shù)的增加，這3種方法的殘差模的值都在減小，但利用內(nèi)積準則和廣義Jaccard系數(shù)準則進行二次篩選的殘差值趨于0的速度更快，說明原子識別階段利用內(nèi)積準則和廣義Jaccard系數(shù)準則進行二次篩選的效果不僅優(yōu)于利用內(nèi)積準則的效果，也優(yōu)于利用廣義Jaccard系數(shù)準則的效果，利用二次篩選進行原子相關性計算能更準確地找到與殘差信號相匹配的原子。

因此，本文提出一種基于二次篩選的回溯廣義正交匹配追蹤算法(Backtracking Generalized Orthogonal Matching Pursuit Based on Secondary Screening, SSBGOMP)。該算法在原子選取階段，首先利用內(nèi)積準則選取2S個相關性最大的原子，然后再利用廣義Jaccard系數(shù)準則對已選出的原子進行二次篩選，選出其中S個最相關的原子，既保留了內(nèi)積匹配準則利用方向?qū)ο蛄窟M行相似性度量的優(yōu)勢，又利用廣義Jaccard系數(shù)準則彌補了內(nèi)積準則對數(shù)值不敏感的缺陷，從而提高了原子選取的正確率，優(yōu)化了支撐集。

SSBGOMP算法的具體步驟如下：

輸入：測量值y，感知矩陣A，稀疏度K，正整數(shù)S

初始化：迭代次數(shù)t=1，初始殘差r0=y，支撐集Λ0=?

算法具體步驟：

1)原子識別。

計算，從||中選取2S個最大元素所對應的原子，取A中這些值對應的原子構(gòu)成新的相關矩陣B。

計算Jaccard(BTrt-1)，從|Jaccard(BTrt-1)|中選取S個最大元素相對應的原子，并記下它們的原子序號{λ(i)}i=1,2,…,S。

2)擴大估計支撐集。

Λt=Λt-1∪{λ(1),λ(2),…,λ(S)}

3)利用最小二乘法估計稀疏信號。

4)回溯。

5)更新殘差。

6)當t≥min{K,M/S}或‖rt‖2<ε時，停止迭代，否則t=t+1，返回步驟1。

4 仿真實驗

為了驗證本文提出的SSBGOMP算法的重構(gòu)性能，對該算法進行仿真實驗，以下實驗結(jié)果是在MATLABR2014a的條件下獲得的。選擇N×1維的稀疏隨機信號，M×N維的高斯隨機矩陣作為感知矩陣，其中N=256,選取原子個數(shù)S在不說明的情況下默認為K/4(當K<4時，S=1)。

實驗1 各種算法在不同稀疏度下的重構(gòu)誤差的比較

圖2 不同稀疏度下算法的重構(gòu)誤差

由圖2可以看出，各個算法的重構(gòu)誤差隨著稀疏度的增大而增大。在同一稀疏度下，SSBGOMP算法的重構(gòu)誤差略低于其他3種算法。說明該算法在不同稀疏度下的重構(gòu)效果好于其他3種對比算法。其中當稀疏度為40、50和60時這4種算法的重構(gòu)誤差如表1所示。

表1 不同稀疏度下各種算法的重構(gòu)誤差

實驗2 各種算法在不同稀疏度下的重構(gòu)成功率的比較

選擇的對比算法為OMP[12]、SP[16]、BGOMP[18]。實驗結(jié)果如圖3示。

圖3 不同稀疏度下算法的重構(gòu)成功率

由圖3可知，這4種算法的重構(gòu)成功率與稀疏度呈負相關，稀疏度越大，算法的重構(gòu)成功率越低。稀疏度K<40時，本文所提算法與SP算法、BGOMP算法的重構(gòu)成功率十分接近，幾乎都為100%，而OMP算法的重構(gòu)成功率已經(jīng)隨著稀疏度的增大而不斷減小，稀疏度為40時其重構(gòu)成功率已降低至48%；稀疏度40

表2 不同稀疏度下各種算法的重構(gòu)成功率

實驗3 在不同觀測數(shù)目下幾種算法重構(gòu)成功率的對比

實驗中設稀疏度K一定，且選取K=40，觀測值M的取值為70～200，每次增加10，對SSBGOMP算法分別運行100次來求重構(gòu)成功率，選擇的對比算法為OMP[12]、SP[16]、BGOMP[18]。實驗結(jié)果如圖4所示。

圖4 不同觀測值下算法的重構(gòu)成功率

觀察圖4，可以看出當稀疏度一定時，M的取值越大，算法的重構(gòu)誤差越小，進而重構(gòu)成功率越高。當M≥130時，除OMP算法之外的其他幾種算法重構(gòu)成功率均達到了100%；當觀測值70

表3 不同觀測值下各種算法的重構(gòu)成功率

5 結(jié)束語

本文提出了基于二次篩選的回溯廣義正交匹配追蹤算法，優(yōu)化了回溯廣義正交匹配追蹤算法中的原子選取方式。該算法首先采用內(nèi)積匹配準則選取較大數(shù)目的相關原子，然后再利用廣義Jaccard系數(shù)準則對已選出的原子進行二次篩選，選出其中最匹配的原子，提高了原子識別的正確率，減小了重構(gòu)誤差。仿真實驗驗證了本文提出的算法對回溯廣義正交匹配追蹤算法改進的可行性及有效性，且在重構(gòu)成功率上優(yōu)于回溯廣義正交匹配追蹤算法、正交匹配追蹤算法和子空間追蹤算法。