基于二次篩選的回溯廣義正交匹配追蹤算法的稀疏信號(hào)重構(gòu)

張連娜,張慧萍,李榮鵬,宋學(xué)力

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

0 引 言

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

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

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

1 壓縮感知理論模型

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

(1)

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

然后利用預(yù)設(shè)的投影矩陣Φ，將高維信號(hào)投影到一個(gè)低維空間上，計(jì)算公式為：

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特性。

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

(5)

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

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

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

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

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

初始化：迭代次數(shù)t=1，初始?xì)埐顁0=y，支撐集Λ0=?

算法具體步驟：

1)原子識(shí)別。

計(jì)算，從||中選取S個(gè)最大元素相對應(yīng)的原子，并記下它們的原子序號(hào){λ(i)}i=1,2,…,S。

2)擴(kuò)大支撐集。

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

3)利用最小二乘法估計(jì)稀疏信號(hào)。

4)回溯。

5)更新殘差。

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

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

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

(6)

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

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

(7)

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

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

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

圖1 不同匹配準(zhǔn)則對殘差的影響

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

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

SSBGOMP算法的具體步驟如下：

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

初始化：迭代次數(shù)t=1，初始?xì)埐顁0=y，支撐集Λ0=?

算法具體步驟：

1)原子識(shí)別。

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

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

2)擴(kuò)大估計(jì)支撐集。

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

3)利用最小二乘法估計(jì)稀疏信號(hào)。

4)回溯。

5)更新殘差。

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

4 仿真實(shí)驗(yàn)

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

5 結(jié)束語

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