葛 明，錢 玲

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

?

基于A*OMP算法及其改進(jìn)算法的寬帶雷達(dá)信號(hào)稀疏分解

葛 明，錢 玲

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

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

稀疏分解；正交匹配追蹤算法；雷達(dá)信號(hào)

0 引 言

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

1 壓縮感知基本原理

壓縮感知理論主要由信號(hào)的稀疏分解、測(cè)量矩陣的設(shè)計(jì)、信號(hào)重構(gòu)這三大核心內(nèi)容組成。

1.1 信號(hào)的稀疏分解

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

(1)

式中:β為稀疏系數(shù)，如果β中只含有K個(gè)非零值(K?N)，則可認(rèn)為信號(hào)f是K稀疏的。

1.2 測(cè)量矩陣的設(shè)計(jì)

在對(duì)信號(hào)進(jìn)行稀疏表示之后，用一組與稀疏變換基不相關(guān)的測(cè)量矩陣Φ對(duì)原始信號(hào)進(jìn)行投影，將信號(hào)從高維空間投影到低維空間上，則表達(dá)式為：

y=Φβ

(2)

該表達(dá)式也可以理解為：

y=Φβ=ΦθTf=Θf

(3)

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

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

(4)

此時(shí)就能從M個(gè)測(cè)量值中還原出K個(gè)非零系數(shù)。

1.3 信號(hào)的重構(gòu)

當(dāng)原始信號(hào)f是可壓縮的，感知矩陣Θ滿足RIP準(zhǔn)則時(shí)，就能夠求出式(2)中的稀疏向量β，最后將β帶入式(1)中求出原始信號(hào)f，實(shí)現(xiàn)了從M維的測(cè)量值y中重構(gòu)出原始信號(hào)。對(duì)于β的求解可以通過求解最小l0范數(shù)問題：

(5)

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

(6)

當(dāng)采樣點(diǎn)數(shù)(即獨(dú)立同分布的高斯測(cè)量值的個(gè)數(shù))滿足M≥cKlg(N/K)時(shí)，就能夠以很大概率重構(gòu)出K稀疏向量，此時(shí)最小l1范數(shù)求解問題就變成了一個(gè)凸優(yōu)化問題，該問題可以轉(zhuǎn)化為求解線性規(guī)劃的問題[2-4]。

2 A*OMP算法

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

A*算法是一種迭代樹形搜索算法。在每次迭代中，當(dāng)前最優(yōu)的路徑和它所有的子集將會(huì)被添加到搜索樹中，當(dāng)最優(yōu)路徑被發(fā)現(xiàn)是完整的時(shí)候搜索中止。

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

(7)

式中:d(Pl)大于或等于路徑Pl產(chǎn)生的任何一個(gè)擴(kuò)展路徑所對(duì)應(yīng)評(píng)價(jià)函數(shù)的衰減。

因此定義代價(jià)函數(shù)：

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

(8)

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

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

3.1 初始化搜索樹

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

3.2 擴(kuò)大已選擇的部分路徑

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

3.2.1 每條擴(kuò)展路徑的修剪

在設(shè)置A*搜索參數(shù)的時(shí)候，需要限制每個(gè)節(jié)點(diǎn)的擴(kuò)展個(gè)數(shù)B,因此在每一次A*OMP迭代中,僅通過B子集來擴(kuò)大搜索樹，B子集與殘留選擇的路徑有著內(nèi)積絕對(duì)值最大值。這樣可以大大減少搜索路徑。

3.2.2 樹尺寸的修剪

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

3.2.3 等效路徑的修剪

3.3 選擇最好的路徑

最小的殘差誤差是衡量最好路徑的標(biāo)準(zhǔn)，因此，對(duì)于一條長(zhǎng)度為l的路徑Sl來說，評(píng)價(jià)函數(shù)可以寫成如下形式：

(9)

輔助函數(shù)對(duì)于評(píng)估長(zhǎng)度不等的多條路徑是極其重要的。下面利用關(guān)于殘差的不同假設(shè)提出3種不同的輔助函數(shù)[5]。

3.3.1 加性代價(jià)模型

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

(10)

因此定義了加性輔助函數(shù)：

(11)

式中:β為一個(gè)大于1的常數(shù)。

最后獲得了代價(jià)函數(shù)：

(12)

式中:β為正則化常數(shù),如果它是比較大的數(shù),則越短的路徑越有利,這會(huì)使搜索過程中擴(kuò)展更多的候選人,當(dāng)它變得更小時(shí),搜索就喜歡更長(zhǎng)的路徑。

3.3.2 自適應(yīng)乘性代價(jià)模型

輔助函數(shù)還可以通過修改未開放節(jié)點(diǎn)的期望平均貢獻(xiàn)自適應(yīng)地被選擇：

(13)

然后,自適應(yīng)輔助函數(shù)應(yīng)該滿足：

(14)

在這種情況下,結(jié)合β>1最終獲得自適應(yīng)輔助函數(shù)：

(15)

自適應(yīng)代價(jià)函數(shù)可以寫成如下形式：

(16)

3.3.3 乘性代價(jià)模型

與加性輔助函數(shù)相比,乘法代價(jià)模型路徑采用權(quán)重函數(shù)。這里假設(shè)每個(gè)節(jié)點(diǎn)減少‖r‖2，根據(jù)定比α，乘法代價(jià)函數(shù)被定義為：

(17)

在這里α應(yīng)該選擇在0和1之間，α的作用非常接近加性代價(jià)函數(shù)β。

3.4 A*OMP算法流程

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

初始化：

T←?

fori←1toIdo%將初始化路徑長(zhǎng)度設(shè)置為1

endfor

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

best_path←1

whileLbest_path≠Kdo

T←Sbest_path

fori←1toBdo%對(duì)每一條擴(kuò)展路徑進(jìn)行修剪

endif

endfor

endwhile

returnSbest_path,cbest_path

3.5 算法的改進(jìn)

在A*OMP算法里，通過使用代價(jià)函數(shù)，將迭代之后的擴(kuò)展路徑分別與迭代之前的最優(yōu)路徑進(jìn)行對(duì)比，通過計(jì)算路徑的代價(jià)，選擇代價(jià)最小的作為當(dāng)前最優(yōu)路徑，以達(dá)到更新最優(yōu)路徑的目的。而在使用代價(jià)函數(shù)的過程中又可以根據(jù)不同的情況選擇不同的輔助函數(shù)。

而在A*OMP的改進(jìn)算法里，在更新最優(yōu)路徑的過程中不使用輔助函數(shù)，直接將擴(kuò)展節(jié)點(diǎn)的殘差作為路徑代價(jià)函數(shù)與迭代之前的最優(yōu)路徑的代價(jià)進(jìn)行對(duì)比。這是因?yàn)樽钚埐钫`差是衡量最好路徑的標(biāo)準(zhǔn)，殘差越小，表明路徑的代價(jià)越小，該路徑就越優(yōu)，因此可以直接將擴(kuò)展節(jié)點(diǎn)的殘差作為路徑代價(jià)函數(shù)與迭代之前的最優(yōu)路徑的代價(jià)進(jìn)行對(duì)比。如果殘差小于最優(yōu)路徑，則更新當(dāng)前最優(yōu)路徑。經(jīng)過改進(jìn)之后的算法將大大提高信號(hào)稀疏分解的重構(gòu)精度和運(yùn)行效率。

4 仿真結(jié)果與分析

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

圖1 使用OMP算法對(duì)信號(hào)的稀疏分解

圖2 使用A*OMP算法對(duì)信號(hào)的稀疏分解

圖3 使用A*OMP改進(jìn)算法對(duì)信號(hào)的稀疏分解

為了進(jìn)一步顯示A*OMP及其改進(jìn)算法的優(yōu)越性，表1列出了該算法與OMP算法在相同條件下的信噪比、相對(duì)誤差、匹配度以及重構(gòu)運(yùn)行時(shí)間的對(duì)比。

表1 信號(hào)稀疏分解的相對(duì)速度與重建質(zhì)量對(duì)比

通過仿真結(jié)果可以看出，由于A*OMP算法采用的是多路徑搜索，相比OMP算法的單路徑搜索而言，它的運(yùn)行時(shí)間要長(zhǎng)于OMP算法的運(yùn)行時(shí)間；然而在重構(gòu)精度方面A*OMP算法及其改進(jìn)算法要高于OMP算法，而且A*OMP算法特別是它的改進(jìn)算法在運(yùn)行效率方面與OMP算法相差并不大。因此總體而言，A*OMP算法要優(yōu)于OMP算法。

5 結(jié)束語

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

[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] 趙慧民，倪霄.壓縮感知的冗余字典及其迭代閥值實(shí)現(xiàn)算法[J].電路與系統(tǒng)學(xué)報(bào),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