基于修正近似雙曲正切函數(shù)的平滑l0范數(shù)算法

陳金立，李 偉，朱筱嶸，陳 宣，李家強(qiáng)

(1.南京信息工程大學(xué) 氣象災(zāi)害預(yù)報(bào)預(yù)警與評(píng)估協(xié)同創(chuàng)新中心，江蘇 南京 210044；2.南京信息工程大學(xué) 電子與信息工程學(xué)院，江蘇 南京 210044；3.南京信息工程大學(xué) 物理與光電工程學(xué)院，江蘇 南京 210044)

0 引 言

在傳統(tǒng)信號(hào)采樣理論中，為保證信號(hào)的無(wú)失真輸出，需要的采樣率至少為信號(hào)帶寬的兩倍。因此，在處理較大帶寬的信號(hào)時(shí)，傳統(tǒng)信號(hào)采樣會(huì)對(duì)硬件系統(tǒng)造成很大的壓力。壓縮感知(compressing sensing，CS)[1-3]是一種新型的信號(hào)采樣理論，它只需要極少的稀疏信號(hào)采樣值即可利用重構(gòu)算法完成信號(hào)的精確重構(gòu)，現(xiàn)已廣泛地應(yīng)用在雷達(dá)成像[4]、信號(hào)處理[5]以及醫(yī)學(xué)成像[6]等領(lǐng)域。稀疏重構(gòu)問(wèn)題等價(jià)于欠定方程組y=Dx的稀疏求解問(wèn)題，其中，y∈M為測(cè)量矩陣，D∈M×N是感知矩陣，x∈N是稀疏向量。稀疏問(wèn)題的求解模型可表示為s.t.y=Dx。其中，表示l0范數(shù)，即向量非零元素的個(gè)數(shù)。l0范數(shù)最小化問(wèn)題是NP-難問(wèn)題，從而導(dǎo)致稀疏問(wèn)題模型難以求解[7]。基追蹤(basic pursuit，BP)算法[8]是解決上述問(wèn)題的一種有效的算法，該算法利用l1范數(shù)來(lái)代替l0范數(shù)，由此上述模型轉(zhuǎn)變?yōu)閟.t.y=Dx，然后對(duì)其進(jìn)行求解，從而實(shí)現(xiàn)對(duì)稀疏信號(hào)的重構(gòu)。但是，BP算法的計(jì)算量較大，無(wú)法快速重構(gòu)出稀疏信號(hào)。此外，還有許多其它稀疏重構(gòu)算法，比如，迭代加權(quán)最小二乘(iterative re-weighted least squares，IRLS)算法[9]、正交匹配追蹤(orthogonal matching pursuit，OMP)算法[10]以及平滑l0范數(shù)(smoothedl0norm，SL0)算法[11,12]等。其中，SL0算法利用高斯函數(shù)來(lái)逼近l0范數(shù)，并通過(guò)最速下降法和梯度投影原理實(shí)現(xiàn)稀疏信號(hào)的重構(gòu)。盡管SL0算法能夠快速重構(gòu)稀疏信號(hào)，但是該算法所采用的高斯函數(shù)對(duì)l0范數(shù)的逼近性能較差，并且在利用最速下降法解決該函數(shù)極值問(wèn)題時(shí)會(huì)產(chǎn)生“鋸齒效應(yīng)”，從而導(dǎo)致SL0算法的重構(gòu)精度較低。文獻(xiàn)[13]提出一種牛頓平滑l0范數(shù)(newton smoothedl0norm，NSL0)算法，該算法采用近似雙曲正切函數(shù)來(lái)逼近l0范數(shù)，并利用修正牛頓法解決函數(shù)的極值問(wèn)題，從而提高了SL0算法的重構(gòu)性能。文獻(xiàn)[14]采用另一種近似雙曲正切函數(shù)來(lái)逼近l0范數(shù)，并在牛頓方向上搜尋該函數(shù)的極值，進(jìn)而獲得一種近似SL0(approximate smoothedl0norm，ASL0)算法，然后利用該算法進(jìn)行MIMO雷達(dá)目標(biāo)成像，有效地提高了其成像性能。

針對(duì)SL0算法中所采用的高斯函數(shù)對(duì)l0范數(shù)的逼近效果不理想從而導(dǎo)致算法的重構(gòu)性能差的問(wèn)題，本文提出一種基于修正近似雙曲正切函數(shù)的平滑l0范數(shù)算法，該算法采用一種修正的近似雙曲正切函數(shù)來(lái)對(duì)l0范數(shù)實(shí)現(xiàn)較優(yōu)的逼近，并通過(guò)牛頓法求解該平滑函數(shù)所表示的稀疏問(wèn)題，從而有效地提高了稀疏信號(hào)的重構(gòu)性能。仿真結(jié)果表明，本文算法的重構(gòu)性能優(yōu)于SL0算法、NSL0算法以及ASL0算法。

1 基于修正近似雙曲正切函數(shù)的平滑l0范數(shù)算法

1.1 一種用于逼近l0范數(shù)的修正近似雙曲正切函數(shù)

SL0算法的核心思想在于采用高斯函數(shù)來(lái)逼近l0范數(shù)，從而將l0范數(shù)最小化問(wèn)題轉(zhuǎn)變成平滑函數(shù)的極值問(wèn)題，避免了對(duì)l0范數(shù)最小化問(wèn)題的直接求解。SL0算法所采用的高斯函數(shù)的表達(dá)式為

(1)

則

(2)

令

(3)

可以得到

(4)

則稀疏求解模型可轉(zhuǎn)化為

(5)

為了提高SL0算法中的平滑函數(shù)對(duì)l0范數(shù)的逼近程度，文獻(xiàn)[13]和文獻(xiàn)[14]分別采用兩種不同的近似雙曲正切函數(shù)來(lái)代替標(biāo)準(zhǔn)高斯函數(shù)。這兩種雙曲正切函數(shù)表達(dá)式分別為

(6)

(7)

由此可知，尋找一種合適的平滑函數(shù)來(lái)有效的逼近l0范數(shù)，這對(duì)SL0算法的重構(gòu)性能至關(guān)重要。在NSL0算法和ASL0算法的基礎(chǔ)上，為了更進(jìn)一步提高平滑函數(shù)對(duì)l0范數(shù)的近似程度，本文構(gòu)造一種平滑函數(shù)來(lái)近似l0范數(shù)，從而提高其逼近程度。本文構(gòu)造的一種修正近似雙曲正切函數(shù)表達(dá)式如下

(8)

圖1為高斯函數(shù)、文獻(xiàn)[13]和文獻(xiàn)[14]中分別采用的兩種近似雙曲正切函數(shù)以及本文所采用的修正近似雙曲正切函數(shù)fσxi在σ=0.1處的分布圖。由圖1可以看出，與文獻(xiàn)[13]和文獻(xiàn)[14]中提出的兩種近似雙曲正切函數(shù)相比，本文提出的修正近似雙曲正切函數(shù)在x∈[-0.5, 0.5]內(nèi)的“陡峭性”更大，表明該函數(shù)對(duì)l0范數(shù)的逼近程度更優(yōu)。

圖1 4種函數(shù)在σ=0.1時(shí)的分布

令

(9)

可以得到

(10)

則對(duì)應(yīng)修正近似雙曲正切函數(shù)的稀疏模型為

(11)

與文獻(xiàn)[11-14]類似，參數(shù)σ控制著函數(shù)Fσx對(duì)l0范數(shù)的近似程度，即σ越小，函數(shù)越趨近于l0范數(shù)，但同時(shí)函數(shù)存在的局部極值也越多，則Fσx在逼近l0范數(shù)的過(guò)程中，易陷入局部極值，極大地增加了對(duì)函數(shù)全局極值的求解難度。為了解決該問(wèn)題，本文將σ取為一組逐次下降的序列σ1>σ2>,…>σJ，其中σJ為一個(gè)接近于零的極小正值。然后利用修正牛頓法將σi1≤i≤J對(duì)應(yīng)的式(13)進(jìn)行求解，使得算法能夠逐漸逼近全局最大值。

1.2 利用修正牛頓法求解修正函數(shù)所表示的稀疏問(wèn)題

SL0算法通常利用最速下降法求解高斯函數(shù)的全局最大值，雖然最速下降法步驟簡(jiǎn)單，且每次計(jì)算函數(shù)極大值時(shí)的迭代量很小，但是在搜尋函數(shù)全局最大值的過(guò)程中會(huì)出現(xiàn)“鋸齒效應(yīng)”[13]，從而對(duì)SL0算法的重構(gòu)精度產(chǎn)生不利影響。針對(duì)此問(wèn)題，本文利用修正牛頓法[15]求解式(11)，從而提高了稀疏信號(hào)的重構(gòu)精度。對(duì)于函數(shù)Fσ(x)，其牛頓方向?yàn)?/p>

d=-Δ2Fσ(x)-1ΔFσ(x)

(12)

式中

(13)

(14)

其中

在計(jì)算出函數(shù)Fσ(x)的牛頓方向d之后，其中矩陣Δ2Fσ(x)是Hessen矩陣，該矩陣不滿足正定條件，進(jìn)而不能保證牛頓方向d為下降方向。為保證d為下降方向，文中對(duì)式(14)中的對(duì)角元素進(jìn)行修正，從而構(gòu)造一個(gè)新矩陣H來(lái)代替牛頓方向d中的Δ2Fσ(x)矩陣。新矩陣H的表達(dá)式為

H=Δ2Fσ(x)+ψ

(15)

式中：ψ為一個(gè)對(duì)角矩陣，為方便計(jì)算，本文將其對(duì)角元素ψi取為

(16)

由此可得，H中第i個(gè)對(duì)角線上的元素為

(17)

由上式可知，修正后的新矩陣H滿足正定條件，利用新矩陣H代替牛頓方向d中的Δ2Fσ(x)矩陣，以保證牛頓方向d為下降方向，即改進(jìn)后的修正牛頓方向?yàn)?/p>

(18)

本文算法步驟總結(jié)如下：

步驟1 初始化：

步驟2 算法迭代：

forj=1,2,…,J

(2) 在修正牛頓方向上逐次搜尋函數(shù)Fσ(x)的全局最小值，并將該最小值投影到可行集上。

forl=1,2,…,L

2 仿真結(jié)果及分析

為驗(yàn)證本文算法的稀疏重構(gòu)性能，本節(jié)設(shè)計(jì)了幾組SL0算法、NSL0算法、ASL0算法和本文算法的對(duì)比實(shí)驗(yàn)。在本文仿真中，稀疏源信號(hào)是通過(guò)伯努立-高斯模型[16]隨機(jī)生成，該模型為

xi～p·N0,δon+1-p·N0,δoff

(19)

其中，p為源信號(hào)中出現(xiàn)大的非零量的概率；N(0,δ)為高斯加性白噪聲，其均值為零，方差為δ;δon和δoff分別是構(gòu)成源信號(hào)的較大非零系數(shù)和較小非零系數(shù)。設(shè)置δoff?δon，且p?1，以保證源信號(hào)的稀疏性。在本文仿真中，y∈M×1為隨機(jī)采樣矩陣，x∈N×1為稀疏源信號(hào)矩陣，D∈M×N為感知矩陣。對(duì)于y=Dx，在已知y和D的情況下，分別利用SL0算法、NSL0算法、ASL0算法以及本文算法對(duì)稀疏源信號(hào)進(jìn)行重構(gòu)。用于產(chǎn)生稀疏源信號(hào)的模型中參數(shù)設(shè)置分別為M=1000,N=400,δon=1,δoff=10-3,p=0.1；在SL0算法、NSL0算法、ASL0算法和本文算法中，設(shè)置σJ=0.001,ρ=0.7，內(nèi)循環(huán)次數(shù)L=5。

定義信噪比為

(20)

式中：tr(·)表示對(duì)矩陣進(jìn)行求跡。本文采用重構(gòu)信噪比和重構(gòu)誤差來(lái)評(píng)價(jià)各算法的重構(gòu)性能，重構(gòu)信噪比定義為

(21)

(22)

仿真內(nèi)容一：不同算法對(duì)稀疏信號(hào)重構(gòu)的實(shí)驗(yàn)

圖2是原始信號(hào)以及利用各算法獲得的重構(gòu)信號(hào)對(duì)比圖。源信號(hào)稀疏度表示信號(hào)矩陣中非零元素的個(gè)數(shù)。本次仿真中，取稀疏度K=100，信噪比SNR=30 dB。本文算法采用了一種修正近似雙曲正切函數(shù)來(lái)逼近l0范數(shù)，提高了平滑函數(shù)對(duì)l0范數(shù)的近似程度，由圖2可知，相比于SL0算法，NSL0算法和ASL0算法，本文算法重構(gòu)出的稀疏信號(hào)最接近于原始源信號(hào)。

圖2 原始稀疏信號(hào)以及利用各算法獲得的重構(gòu)信號(hào)

仿真內(nèi)容二：各算法的重構(gòu)性能與信噪比的關(guān)系

圖3和圖4分別為4種算法的重構(gòu)信噪比和重構(gòu)誤差與信噪比的變化關(guān)系。設(shè)信噪比變化范圍為20 dB～40 dB，信號(hào)稀疏度K=100，進(jìn)行200次仿真實(shí)驗(yàn)。由圖3和圖4可知，由于在NSL0算法和ASL0算法中所采用的近似雙曲正切函數(shù)對(duì)l0范數(shù)的近似程度優(yōu)于高斯函數(shù)，而且利用了修正牛頓法來(lái)求解平滑函數(shù)的極值問(wèn)題，避免了最速下降法在迭代過(guò)程中產(chǎn)生的“鋸齒效應(yīng)”，因此NSL0算法和ASL0算法的重構(gòu)信噪比要高于SL0算法，而重構(gòu)誤差要低于SL0算法。本文算法采用了一種修正的近似雙曲正切函數(shù)，其近似l0范數(shù)的程度要優(yōu)于NSL0算法和ASL0算法中的平滑函數(shù)，由圖3和圖4可知，本文算法的重構(gòu)性能最好。

圖3 不同算法的重構(gòu)信噪比與信噪比的變化關(guān)系

圖4 不同算法的重構(gòu)誤差與信噪比的變化關(guān)系

仿真內(nèi)容三：各算法的重構(gòu)性能與稀疏度之間的變化關(guān)系

圖5和圖6分別為各算法的重構(gòu)信噪比和重構(gòu)誤差與稀疏度的變化關(guān)系。假設(shè)稀疏度K的變化范圍為20～100，信噪比為30 dB。由圖5和圖6可知，本文算法在不同信號(hào)稀疏度下其重構(gòu)性能始終要優(yōu)于SL0算法、NSL0算法和ASL0算法。

圖5 不同算法的重構(gòu)信噪比與稀疏度的變化關(guān)系

圖6 不同算法的重構(gòu)誤差與稀疏度的變化關(guān)系

3 結(jié)束語(yǔ)

SL0算法一般采用高斯函數(shù)作為平滑函數(shù)來(lái)近似l0范數(shù)，但是高斯函數(shù)對(duì)l0范數(shù)的近似程度不夠理想，并且利用最速下降法求解函數(shù)極值問(wèn)題時(shí)會(huì)產(chǎn)生“鋸齒效應(yīng)”，從而導(dǎo)致該算法的稀疏信號(hào)重構(gòu)性能較差。本文提出一種基于修正近似雙曲正切函數(shù)的平滑l0范數(shù)算法，該算法采用一種修正近似雙曲正切函數(shù)來(lái)逼近l0范數(shù)，同時(shí)利用牛頓法求解該函數(shù)的極值問(wèn)題，從而實(shí)現(xiàn)了稀疏信號(hào)的高精度重構(gòu)。數(shù)值仿真實(shí)驗(yàn)結(jié)果表明，與其它算法相比，本文算法的稀疏信號(hào)重構(gòu)性能最優(yōu)。