基于A*OMP算法及其改進算法的寬帶雷達信號稀疏分解

葛 明，錢 玲

(南京理工大學，南京 210000)

?

基于A*OMP算法及其改進算法的寬帶雷達信號稀疏分解

葛 明，錢 玲

(南京理工大學，南京 210000)

傳統稀疏分解算法正交匹配追蹤(OMP)算法里采用內積最大值來尋找最優原子，該方法容易陷入局部最優，為了彌補這一缺點，采用了新的算法：A*OMP算法，該算法使用A*搜索(即最佳優先搜索技術)尋找最優原子，該搜索方式尋找的最優原子具有全局最優性。實驗表明相比傳統OMP算法而言，該算法有效地提高了信號的重構精度。

稀疏分解；正交匹配追蹤算法；雷達信號

0 引 言

一直以來，奈奎斯特采樣定理一直是信號采樣、存儲、傳輸領域所采用的主要方法，它要求采樣頻率必須大于或等于信號中最高頻率的2倍，然而面對快速發展的信息化社會，該采樣理論已經無法滿足社會的需要。因此，近年來出現了一種全新的信號采集理論：壓縮感知(CS)理論。該理論指出：若信號在某個變換域是稀疏的(稀疏性)或可壓縮的，則可以設計一個與稀疏變換基不相關的測量矩陣，將變換所得的信號從高維空間投影到低維空間上，得到一組測量值，最后通過求解優化問題，將低維的測量值還原成高維的原始信號，實現信號的近似或準確重構。該理論的提出，使得能夠以遠低于傳統采樣定理所需的采樣頻率對信號進行采樣。

1 壓縮感知基本原理

壓縮感知理論主要由信號的稀疏分解、測量矩陣的設計、信號重構這三大核心內容組成。

1.1 信號的稀疏分解

假設一個具有稀疏性的長度為N的一維離散實值信號f(f∈RN)，可以用變換域θ中的一組正交基?i(i=1,2,…N)表示，則信號可以表示[1]為：

(1)

式中:β為稀疏系數，如果β中只含有K個非零值(K?N)，則可認為信號f是K稀疏的。

1.2 測量矩陣的設計

在對信號進行稀疏表示之后，用一組與稀疏變換基不相關的測量矩陣Φ對原始信號進行投影，將信號從高維空間投影到低維空間上，則表達式為：

y=Φβ

(2)

該表達式也可以理解為：

y=Φβ=ΦθTf=Θf

(3)

式中:Θ=ΦθT，Φ為M×N矩陣(M?N)。

由于式(2)中方程的個數M遠遠小于未知數的個數N，所以方程無解。但若β是K稀疏的，并且β中的非零系數的位置是已知的，則當M≥K時，該問題就能夠得到解決，此時只需要式(3)中的矩陣Θ滿足有限等距性質(簡稱RIP)，即對于任意K稀疏向量u，ε∈(0,1)滿足如下不等式：

(4)

此時就能從M個測量值中還原出K個非零系數。

1.3 信號的重構

當原始信號f是可壓縮的，感知矩陣Θ滿足RIP準則時，就能夠求出式(2)中的稀疏向量β，最后將β帶入式(1)中求出原始信號f，實現了從M維的測量值y中重構出原始信號。對于β的求解可以通過求解最小l0范數問題：

(5)

然而在求解式(5)的過程中發現，該式的求解極其復雜，而且還是個無解難題(NP)問題，所以對于求解最小l0范數問題，可以用能夠產生相同解但是更為方便的最小l1范數的求解來代替，最小l1范數問題的求解如下所示：

(6)

當采樣點數(即獨立同分布的高斯測量值的個數)滿足M≥cKlg(N/K)時，就能夠以很大概率重構出K稀疏向量，此時最小l1范數求解問題就變成了一個凸優化問題，該問題可以轉化為求解線性規劃的問題[2-4]。

2 A*OMP算法

A*OMP(即A*正交匹配追蹤)算法是一種新的采用最佳優先搜索方式的半貪婪算法。該算法本質上是將A*算法與OMP[5]算法相結合的算法[6]，算法中包含了A*搜索[7-8]：一種最佳優先搜索技術,利用最佳優先搜索可以評估多條路徑。

A*算法是一種迭代樹形搜索算法。在每次迭代中，當前最優的路徑和它所有的子集將會被添加到搜索樹中，當最優路徑被發現是完整的時候搜索中止。

d(Pl)≥g(Pl)-g(Pl∪zK-l),?zK-l

(7)

式中:d(Pl)大于或等于路徑Pl產生的任何一個擴展路徑所對應評價函數的衰減。

因此定義代價函數：

F(Pl)=g(Pl)-d(Pl).

(8)

3 使用A*算法搜索最匹配的原子

A*搜索從候選子集的單一元素開始，執行一個多路徑搜索，在所有可能的含有K個原子的子集中選取最好的一個。將采用3個主要步驟來討論A*OMP：初始化搜索樹，擴展已選擇的部分路徑和選擇最優路徑。

3.1 初始化搜索樹

A*搜索將搜索樹的所有可能的路徑長度初始化為1。由于每次迭代會在一條已選擇部分的路徑中添加多個子集，因此開始搜索時盡可能用很少的路徑，為此限制了初始化搜索子集I(I?K)。

3.2 擴大已選擇的部分路徑

在典型的A*搜索中,在每次迭代中所有最有前途的路徑的子集都會被添加到搜索樹中。這將產生大量的可能的子集，導致太多的搜索路徑，為了限制這些,將采用如下3種修剪策略。

3.2.1 每條擴展路徑的修剪

在設置A*搜索參數的時候，需要限制每個節點的擴展個數B,因此在每一次A*OMP迭代中,僅通過B子集來擴大搜索樹，B子集與殘留選擇的路徑有著內積絕對值最大值。這樣可以大大減少搜索路徑。

3.2.2 樹尺寸的修剪

為了進一步減少內存需求,限制樹中搜索路徑的最大數量P,當超過這個限制,最壞的路徑(即以最大的成本)從樹中刪除,直到P路徑仍然保留。

3.2.3 等效路徑的修剪

3.3 選擇最好的路徑

最小的殘差誤差是衡量最好路徑的標準，因此，對于一條長度為l的路徑Sl來說，評價函數可以寫成如下形式：

(9)

輔助函數對于評估長度不等的多條路徑是極其重要的。下面利用關于殘差的不同假設提出3種不同的輔助函數[5]。

3.3.1 加性代價模型

加性代價模型假定表示的K個向量的平均貢獻等同于‖y‖2，則一個向量的平均貢獻為δe=‖y‖2/K。一條長度為l的部分路徑里未開放的K-l節點預計將減少‖r‖2，即(K-l)δe。結合式(7),輔助函數應該滿足：

(10)

因此定義了加性輔助函數：

(11)

式中:β為一個大于1的常數。

最后獲得了代價函數：

(12)

式中:β為正則化常數,如果它是比較大的數,則越短的路徑越有利,這會使搜索過程中擴展更多的候選人,當它變得更小時,搜索就喜歡更長的路徑。

3.3.2 自適應乘性代價模型

輔助函數還可以通過修改未開放節點的期望平均貢獻自適應地被選擇：

(13)

然后,自適應輔助函數應該滿足：

(14)

在這種情況下,結合β>1最終獲得自適應輔助函數：

(15)

自適應代價函數可以寫成如下形式：

(16)

3.3.3 乘性代價模型

與加性輔助函數相比,乘法代價模型路徑采用權重函數。這里假設每個節點減少‖r‖2，根據定比α，乘法代價函數被定義為：

(17)

在這里α應該選擇在0和1之間，α的作用非常接近加性代價函數β。

3.4 A*OMP算法流程

為了全面展示該算法，算法的偽代碼如下所示：

初始化：

T←?

fori←1toIdo%將初始化路徑長度設置為1

endfor

Ci=‖y‖2,Li=0,?i=I+1,I+2,…,P

best_path←1

whileLbest_path≠Kdo

T←Sbest_path

fori←1toBdo%對每一條擴展路徑進行修剪

endif

endfor

endwhile

returnSbest_path,cbest_path

3.5 算法的改進

在A*OMP算法里，通過使用代價函數，將迭代之后的擴展路徑分別與迭代之前的最優路徑進行對比，通過計算路徑的代價，選擇代價最小的作為當前最優路徑，以達到更新最優路徑的目的。而在使用代價函數的過程中又可以根據不同的情況選擇不同的輔助函數。

而在A*OMP的改進算法里，在更新最優路徑的過程中不使用輔助函數，直接將擴展節點的殘差作為路徑代價函數與迭代之前的最優路徑的代價進行對比。這是因為最小殘差誤差是衡量最好路徑的標準，殘差越小，表明路徑的代價越小，該路徑就越優，因此可以直接將擴展節點的殘差作為路徑代價函數與迭代之前的最優路徑的代價進行對比。如果殘差小于最優路徑，則更新當前最優路徑。經過改進之后的算法將大大提高信號稀疏分解的重構精度和運行效率。

4 仿真結果與分析

本文使用頻帶寬度B=80 MHz,脈沖寬度T=0.5 μs、采樣頻率Fs=160 MHz的寬帶雷達信號，對其進行稀疏分解。由于Gabor字典對稀疏信號具有普遍適用性，因此構造Gabor字典，選取字典里的基函數作為稀疏基，分別采用OMP算法和A*OMP算法以及其改進算法將信號進行稀疏分解，其仿真結果如圖1～圖3所示。

圖1 使用OMP算法對信號的稀疏分解

圖2 使用A*OMP算法對信號的稀疏分解

圖3 使用A*OMP改進算法對信號的稀疏分解

為了進一步顯示A*OMP及其改進算法的優越性，表1列出了該算法與OMP算法在相同條件下的信噪比、相對誤差、匹配度以及重構運行時間的對比。

表1 信號稀疏分解的相對速度與重建質量對比

通過仿真結果可以看出，由于A*OMP算法采用的是多路徑搜索，相比OMP算法的單路徑搜索而言，它的運行時間要長于OMP算法的運行時間；然而在重構精度方面A*OMP算法及其改進算法要高于OMP算法，而且A*OMP算法特別是它的改進算法在運行效率方面與OMP算法相差并不大。因此總體而言，A*OMP算法要優于OMP算法。

5 結束語

本文主要介紹了與OMP算法相比，A*OMP算法及其改進算法對信號的稀疏分解具有能夠大大提高重構精度的優點。OMP算法里采用內積最大值來尋找最優原子，該方法容易陷入局部最優。在用了半貪婪的A*OMP算法后，使得這種不準確的選擇有了緩沖的余地。A*OMP算法通過使用A*搜索方式，使得尋找的最優原子具有全局最優性，因此在重構精度方面，A*OMP算法要優于OMP算法。目前對信號的稀疏分解仍然是研究的熱點，在研究過程中根據各自不同的需求，有時候以犧牲精度來提高運算效率，有時候以犧牲運算效率來提高精度，然而這都是需要人們進行改進克服的，如何能夠既提高運算效率又提高信號的重構精度仍然是人們研究的重點。

[1] Justin Romberg.Compressive sensing by random convolution[J].SIAM Journal on Imaging Sciences,2009,2(4)：1098-1128.

[2] Elad M.Optimized projections for compressed sensing[J].IEEE Transactions on Signal Processing,2007,52(12):5695-5702.

[3] Candes E J,Tao.Near optimal signal recovery from random projection:Universal encoding strategies[J].IEEE Transactions on Information Theory,2006,52(12):5406-5425.

[4] Dechter R,Pearl J.Generalized best-first search strategies and the optimality of A*[J].ACM,1985(32)：505- 536.

[5] Tropp J,Gilbert A.Signal recovery from random measurements via orthogonal matching pursuit[J].IEEE Transactions on information theory,2007,53(12):4655- 4665.

[6] Nazim Burak,Karahanoglua,Hakan Erdogana.A*Orthogonal matching pursuit:best-first search for compressed sensing signal recovery,Digital Signal Processing[J],2012,22(4):1051-2004.

[7] Koenig S,Likhachev M,Liu Y,Furcy D.Incremental heuristic search in AI[J].AI Magzine,2004(25)：99- 112.

[8] 趙慧民，倪霄.壓縮感知的冗余字典及其迭代閥值實現算法[J].電路與系統學報,2013(1):59-64.

[9] Jelinek F.Statistical Methods for Speech Recognition[M].Cambridge,MA,USA:MIT Press,1998.

[10]Hart P E,Nilsson N J,Raphael B.A formal basis for the heuristic determination of minimum cost paths[J].IEEE Transactions on Systems Cybernetics,1968,SS-(2):100-107.

Sparse Decomposition of Broadband Radar Signals Based on A*OMP Algorithm and Its Improved Algorithm

GE Ming，QIAN Ling

(Nanjing University of Science &Technology,Nanjing 210000,China)

In the traditional sparse decomposition algorithm——orthognal matching pursuit (OMP) algorithm,maximum inner product is used to find the optimal atom.The method is easy to fall into local optimization,in order to make up the shortcoming,a new algorithm is proposed in this paper:A*OMP algorithm,the algorithm uses A*search (the best first search technology) to find the optimal atom,the optimal atom searched by using the search way has global optimality.Experiments show that the algorithm effectively improves the reconstruction accuracy of signal compared with the traditional OMP algorithms.

sparse decomposition;orthogonal matching pursuit algorithm;radar signal

2014-08-21

TN971.1

A

CN32-1413(2015)01-0065-05

10.16426/j.cnki.jcdzdk.2015.01.016