一種基于廣義Jaccard系數的改進SAMP壓縮信號快速恢復算法

時天昊, 白銀山, 沈 堤, 沈志遠

(1.南京航空航天大學民航學院,南京,211106;2.94116部隊,新疆和田,848000;3.空軍工程大學空管領航學院,西安,710051)

根據《“十四五”民用航空發展規劃》,預計到2025年,民用運輸機場數量達到270個以上,保障起降架次1 700萬。民航的快速發展導致機場終端區的頻譜資源需求及安全隱患大大增加,對頻譜的快速高效監測可以指導頻譜的智能管理。在機場終端管制區認知無線電技術可以包括:利用信號能量檢測實現信號狀態感知及稀疏化處理,將電磁信號轉換成二進制信號,并將二進制信號作為測量信號,引入寬帶壓縮頻譜感知模型,利用壓縮感知[1](compressed sensing,CS)算法進行信號傳遞后的重構工作。壓縮感知可以在較小的采樣頻率的情況下對頻譜進行高精度監測,同時在廣播式自動相關監視(automatic dependent surveillance-broadcast, ADS-B)的來波信號估計、干擾抑制、空管數據處理等方面也有著廣泛的應用。

壓縮感知算法是一種高效的信號采集及重構算法,該算法在采樣頻率遠低于奈奎斯特頻率情況下依然有著優秀的重構精度,大大降低了信號的傳輸量,在圖像重建[2]、遠距離通信[3]等領域有廣泛的應用前景。對于壓縮感知的研究主要集中在測量矩陣構造、信號稀疏表示、重構算法3個方面[4]。重構算法的選擇直接影響著信號恢復的精度及速度。重構算法主要有組合類算法、凸優化類算法和貪婪追蹤類算法3種[5]。貪婪類算法憑借復雜度低,重構效果好,收斂速度快等特點得到了廣泛應用。貪婪算法需要較多的先驗信息,然后在每次迭代過程中,不斷地將迭代目標像原始信號靠近,并通過設定一個收斂條件來結束算法,從而達到具有較高重構精度的信號。常用的貪婪類算法包括匹配追蹤[6]、正交匹配追蹤[7]、正則化正交匹配追蹤[8]、分段正交匹配追蹤[9]、壓縮采樣匹配追蹤[10]、子空間追蹤算法[11]。但是上述介紹的算法一般需要先驗參數稀疏度K來確定迭代的次數,在實際運用中不具備較高的應用性,為了解決這個問題,文獻[12]提出了稀疏度自適應匹配追蹤算法(sparsity adaptive matching pursuit,SAMP),該算法在稀疏度未知的情況下依舊具有較高的重構精度。SAMP算法在迭代過程中的原子篩選標準均采用的是內積匹配準則,有時會導致2個相似原子信息的丟失,降低重構精度。SAMP-RB算法[13]在原子篩選階段采用了正則化回溯的思想,用正則化進行原子的二次篩選,大大提高了重構精度,但是由于增加了二次篩選,其算法運行時間也大大增加。文獻[14]提出的DSAMP算法用Dice系數代替了SAMP算法中的內積匹配準則進行原子篩選,Dice系數可以更好地突出殘差信號中的重要元素組成部分,更準確的選擇符合信號重構的原子,大大提高了重構精度。同時,SAMP算法在運行前需要進行一個固定步長設置,過大的步長設置會導致算法的精度達無法達到理想效果,而過小的步長設置會降低算法的運行效率。文獻[15]將變步長的思想引入到算法之中,作者利用Sigmoid函數作為變步長的判斷條件,利用大步長逼近,小步長漸進的方法提高了算法的重構精度及運行效率。SAMP-PVRB[16]不僅采用了正則化回溯的思想,還將拋物線函數和變步長思想結合,函數的變化率與算法迭代過程中步長的大小變化呈正相關,取得了良好的效果。在變步長思想中增加初始稀疏度估計有助于大小步長的設置,降低算法的迭代次數,Gao[17]根據定理:稀疏度小于等于測量數的1/4時,信號可以完全準確地重建。將初始稀疏度大小設置為測量數的1/4進行取根號處理,與未設置初始稀疏度情況相比重構效率大大提高。

由于民航終端區頻譜資源態勢復雜,以上方法在解決頻譜感知等問題時的精度及效率還未達到要求,為解決上述問題,本文提出了一種基于SAMP算法改進的算法:JTVS-SAMP(J代表廣義Jaccard系數,T代表t-平均相關系數,VS代表變步長思想)。該算法在原子篩選過程中,利用廣義Jaccard系數代替了SAMP算法中的內積匹配準則,并引入t-平均相關系數對初始稀疏度進行預測來確定算法迭代的初始步長,同時引入了變步長的思想來優化算法的重構效率和重構精度。

1 壓縮感知

1.1 壓縮感知的概述

壓縮感知的流程如圖1所示[18],主要分為3步:信號稀疏表示、信號采樣、信號重構。

圖1 壓縮感知流程圖

常用的信號稀疏化處理包括小波變換[19]、曲波變換[20]、離散傅里葉變換[21]等。圖1中,Ψ是N×N維稀疏表示陣,x∈RN是長度為N的一維信號,經過稀疏表示陣處理后,信號就具備了稀疏性,數學表達為:

y=ΦΨx=Θx

(1)

式中:y∈RM為壓縮信號;Φ表示測量矩陣;Θ=ΦΨ為M×N的感知矩陣。

如果一個信號本來就具備稀疏性且為一維的,那就可以直接使用一個測量矩陣來對信號進行測量,數學表達為:

y=Φx

(2)

式中:Φ∈RM×N,M?N為測量矩陣;y是被測量矩陣測量后的測量信號。

在信號的采樣過程中,會丟棄原始信號x大量的無用信息,因此測量信號會有一定程度上的能量缺失,Tao和Candès證明了稀疏度為K的測量信號要從M個測量值準確的進行信號重構,就要保證測量矩陣Φ滿足有限等距特性[22](restricted isometry property,RIP)。

信號重構過程即對式(2)的逆向求解過程。在式中M?N,因此x的解會有無窮多個,考慮到x具有稀疏性,可以把信號重構過程轉換成l0范數問題進行計算[23],信號重構的數學模型可表示為:

(3)

式中:‖·‖0是一個非凸函數,代表輸入信號中非零元素數量,對于公式的求解屬于NP(non-deterministic polynomial,NP)難問題,無法直接求解,文獻[24]將L0范數最小化問題轉換成了更加簡單的L1范數最小化問題,實現了從非凸向凸的轉變,計算式如下:

(4)

1.2 SAMP算法

SAMP算法是貪婪類算法的一種,該算法不需要稀疏度K等先驗信息,更符合自然界信號的實際情況。算法步驟流程如下:

表1 SAMP算法步驟

2 JTVS-SAMP算法

2.1 算法改進

2.1.1 基于廣義Jaccard系數的原子篩選

傳統的SAMP算法采用了內積匹配準則[25]來作為原子篩選標準,原子與迭代過程中的殘差匹配度越高,其內積計算結果越大,將該原子加入到支撐集中就可以更快地逼近原始信號,可以達到較為優秀的重構精度,內積匹配準則表達式為:

(5)

式中:x=(x1,x2,…,xn);y=(y1,y2,…,yn)。

由于內積匹配準則更多地考慮了原子和信號殘差之間角度的差距,缺乏對信號本身的關注,這會導致在原子篩選過程中會忽略2個相似度較高的原子,造成信號丟失,降低重構質量。為了避免上述情況的出現,引用了廣義jaccard系數來代替內積匹配準則[23],計算式如下:

(6)

由式(6)可以看出,廣義jaccard系數可以反應出2個向量之間的相似度。分母上放大了2個原子的差異部分,減去了兩者的相似部分,使得原子不容易混淆,減少了重要信息的丟失,使得重構精度大大提升。

2.1.2 初始稀疏度的預估計

準確合適的初始稀疏度估計可以指導設置初始步長,有效地減少迭代次數,提高運行效率,本文采用的稀疏估計策略基于如下性質[26]:

當滿足RIP條件的測量矩陣Φ在稀疏度K下有以下規定時:

(7)

式中:‖Λ‖0=K0,則K0

式(7)中RIP系數δK計算復雜,不容易通過計算得出準確結果。δK與矩陣的正交性呈正相關,其值的大小與信號采樣過程中保留的原始信號信息有關,與0越靠近代表保存的原始信息更完整。根據上述特點,引入了t-平均相關系數來代替RIP系數δK,可以在保證稀疏度估計精確度的同時大大降低計算復雜度,如式(8)所示:

(8)

式中:μt(Φ)是測量矩陣Φ的t-平均相關系數。

t-平均相關系數作為測量矩陣的評價指標,定義如下[27]:

(9)

由此,可以對初始稀疏度K0進行估計,初始化K0=1,代入式(8)進行驗證,如果滿足條件,則K0=K0+1,繼續代入公式驗證,否則就結束迭代并輸出K0。

2.1.3 迭代過程中的變步長處理

在測量矩陣滿足RIP條件的前提下,測量信號y與原始稀疏信號x滿足以下關系[17]:

(10)

雖然考慮了大小步長變化的方法來平衡重構效率及重構精度之間的平衡,但是由于稀疏度K的未知性,無法準確地確定算法迭代的次數,若在最后一次迭代計算時,步長S仍然有著較大的值,可能會導致過估計[28]的現象,為了避免出現上述情況,結合回溯的思想,本文提出了一種步長S的處理方法。若最后一次迭代過程中,步長S=1,就不進行額外處理;若S>1,則將迭代中的參數回溯至上次迭代的數據,然后以步長S=1繼續迭代,直到再一次滿足迭代結束條件,經過回溯處理后,重構信號的誤差會大大降低。

2.2 算法步驟

根據以上改進措施,本文在SAMP算法的基礎上提出了JTVS-SAMP算法,步驟流程如下:

表2 JTVS-SAMP算法步驟

3 仿真結果及對比分析

為了比較本算法和其他算法重構精度及重構效率上的優越性,本文選擇一維高斯隨機稀疏信號來模擬算法所需的測量信號,該信號可以有效的模擬機場終端區信號經過能量檢測處理后的信道狀態[27]。測量矩陣Φ選擇為高斯隨機矩陣進行信號采樣,實驗中所采用的對比算法為實驗選用OMP、CoSaOMP、SP、gOMP、SAMP,參數設置見表3。

表3 仿真參數表

本文所有實驗運行的平臺為MATLAB R2022a,計算機配置為Intel i5-6500 CPU @ 3.20Hz,8.00 GB RAM,Windows 7。為避免額外因素干擾,程序運行期間保證后臺其余程序全部關閉。

3.1 不同觀測值下的算法重構成功率

每種算法實驗重復500次,運行結果見圖2。

圖2 不同觀測值信號重構成功率

從圖中的曲線我們可以看出,隨著測量數M的的增加,各個算法的信號重構成功率都有較大的提升。50

3.2 不同稀疏度下的算法重構成功率

圖3 不同稀疏度信號重構成功率

從圖3可以看出,在測量值為定值的情況下,隨著稀疏度K的增加,所有的算法信號重構成功率均呈現不同程度的下降。JTVS-SAMP算法下降速度遠遠慢于其它算法,在稀疏度K=65的時,依然保持著一定的信號重構成功率,而SAMP算法的重構成功率已經接近0。

3.3 不同算法的重構誤差比較

為了驗證JTVS-SAMP算法及SAMP算法在信號重構成功情況下其重構精度的優劣,我們引入了重構誤差這個指標來表示重構信號和原始信號的相似性,重構誤差越大,代表信號重構效果越差,計算公式如下:

(11)

選擇K=30,35,40共3個稀疏度。SAMP算法的步長設置由2～8,選取步長為4和8兩種情況進行對比分析。對每個特定K值條件下仿真1 000次,統計仿真結果計算信號的平均重構誤差,見表4。

表4 重構誤差對比表

由表格可得,隨著稀疏的K的增加,JTVS-SAMP、SAMP-4和SAMP-8的重構誤差都會逐漸增大,SAMP-4相比于SAMP-8,采用了更小的步長設置,在算法迭代過程中具有更高的精度,因此其重構誤差小于SAMP-8的重構誤差。JTVS-SAMP的重構誤差略優于SAMP-4算法,這是因為JTVS-SAMP算法利用廣義Jaccard系數篩選原子、小步長逼近等措施,使得該算法具有較高的精度。

3.4 不同信號采樣率情況下的重構精度分析

信號采樣率的大小是測量數與信號長度的比值,代表了采集過程中的所需的信號采集數量。為了證明算法在不同信號采樣率情況下的重構性能,引入均方誤差(MSE)作為評價指標,其計算公式如下:

(12)

在壓縮感知中,測量信號K≤M/4是稀疏信號完全恢復的充分條件[17]。因此在本次仿真實驗中,設置測量信號稀疏度K=M/4。采用SAMP算法作為對比算法,其步長設置分為4和8兩種情況,探討采樣率為0.1,0.2,0.3,0.4,0.5情況下的改進算法與對比算法的重構精度,結果見圖4。

圖4 不同采樣率下的算法均方誤差比較圖

從圖4可以看出,隨著采樣率的增加,3種算法的均方誤差數值在逐漸減小,當采樣率大于0.3時,所有的算法均可以完成高精度信號重構,但在低采樣率的信號重構過程中,JTVS-SAMP算法相比于SAMP算法,具有更高的誤差控制能力,表明了算法在低采樣率情況下也具有較高的算法穩定性。

3.5 算法重構時間的比較

為了驗證JTVS-SAMP算法的重構效率的優越性,使用Matlab軟件進行算法用時統計,與步長設置為4、8的SAMP-4、SAMP-8算法進行比較。采樣信號固定測量數M=128,設置稀疏度K從5開始,步長為10增加到40。進行循環200次處理計算平均運行時間,仿真結果見圖5。

圖5 平均運行時間對比圖

由圖5可以看出,隨著稀疏的K的增加,3種算法的平均運行時間都在增加,這是由于信號重構的內容增多,其耗費的時間也在逐漸增加。SAMP-4的平均運行時間大于其余兩種算法,是由于其步長設置較小導致的效率偏低。JTVS-SAMP算法在效率方面略優于SAMP-4算法,這是因為JTVS-SAMP算法對初始稀疏度進行了預測,且采用了變步長的思想,在大步長階段的快速迭代,大大降低了算法所需時間。

4 結語

本文基于的SAMP算法,通過融合廣義Jaccard系數、t-平均相關系數、變步長思想,提出了JTVS-SAMP算法。相比于SAMP,COSaOMP,gOMP等傳統壓縮感知算法,在使用二進制信號模擬信號能量檢測后的機場電磁信號時,JTVS-SAMP算法在同稀疏度不同觀測值、不同稀疏度同觀測值下的情況下,算法重構的成功率表現更為優秀,且與其原算法SAMP相比,在重構誤差、低采樣率信號穩定性、重構時間等方面均有了明顯的提高。該改進算法未來可在機場終端區頻譜分析、波達方向估計等領域廣泛應用。