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

陳金立，李 偉，朱筱嶸，陳 宣，李家強

(1.南京信息工程大學 氣象災害預報預警與評估協同創新中心，江蘇 南京 210044；2.南京信息工程大學 電子與信息工程學院，江蘇 南京 210044；3.南京信息工程大學 物理與光電工程學院，江蘇 南京 210044)

0 引 言

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

針對SL0算法中所采用的高斯函數對l0范數的逼近效果不理想從而導致算法的重構性能差的問題，本文提出一種基于修正近似雙曲正切函數的平滑l0范數算法，該算法采用一種修正的近似雙曲正切函數來對l0范數實現較優的逼近，并通過牛頓法求解該平滑函數所表示的稀疏問題，從而有效地提高了稀疏信號的重構性能。仿真結果表明，本文算法的重構性能優于SL0算法、NSL0算法以及ASL0算法。

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

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

SL0算法的核心思想在于采用高斯函數來逼近l0范數，從而將l0范數最小化問題轉變成平滑函數的極值問題，避免了對l0范數最小化問題的直接求解。SL0算法所采用的高斯函數的表達式為

(1)

則

(2)

令

(3)

可以得到

(4)

則稀疏求解模型可轉化為

(5)

為了提高SL0算法中的平滑函數對l0范數的逼近程度，文獻[13]和文獻[14]分別采用兩種不同的近似雙曲正切函數來代替標準高斯函數。這兩種雙曲正切函數表達式分別為

(6)

(7)

由此可知，尋找一種合適的平滑函數來有效的逼近l0范數，這對SL0算法的重構性能至關重要。在NSL0算法和ASL0算法的基礎上，為了更進一步提高平滑函數對l0范數的近似程度，本文構造一種平滑函數來近似l0范數，從而提高其逼近程度。本文構造的一種修正近似雙曲正切函數表達式如下

(8)

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

圖1 4種函數在σ=0.1時的分布

令

(9)

可以得到

(10)

則對應修正近似雙曲正切函數的稀疏模型為

(11)

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

1.2 利用修正牛頓法求解修正函數所表示的稀疏問題

SL0算法通常利用最速下降法求解高斯函數的全局最大值，雖然最速下降法步驟簡單，且每次計算函數極大值時的迭代量很小，但是在搜尋函數全局最大值的過程中會出現“鋸齒效應”[13]，從而對SL0算法的重構精度產生不利影響。針對此問題，本文利用修正牛頓法[15]求解式(11)，從而提高了稀疏信號的重構精度。對于函數Fσ(x)，其牛頓方向為

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

(12)

式中

(13)

(14)

其中

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

H=Δ2Fσ(x)+ψ

(15)

式中：ψ為一個對角矩陣，為方便計算，本文將其對角元素ψi取為

(16)

由此可得，H中第i個對角線上的元素為

(17)

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

(18)

本文算法步驟總結如下：

步驟1 初始化：

步驟2 算法迭代：

forj=1,2,…,J

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

forl=1,2,…,L

2 仿真結果及分析

為驗證本文算法的稀疏重構性能，本節設計了幾組SL0算法、NSL0算法、ASL0算法和本文算法的對比實驗。在本文仿真中，稀疏源信號是通過伯努立-高斯模型[16]隨機生成，該模型為

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

(19)

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

定義信噪比為

(20)

式中：tr(·)表示對矩陣進行求跡。本文采用重構信噪比和重構誤差來評價各算法的重構性能，重構信噪比定義為

(21)

(22)

仿真內容一：不同算法對稀疏信號重構的實驗

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

圖2 原始稀疏信號以及利用各算法獲得的重構信號

仿真內容二：各算法的重構性能與信噪比的關系

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

圖3 不同算法的重構信噪比與信噪比的變化關系

圖4 不同算法的重構誤差與信噪比的變化關系

仿真內容三：各算法的重構性能與稀疏度之間的變化關系

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

圖5 不同算法的重構信噪比與稀疏度的變化關系

圖6 不同算法的重構誤差與稀疏度的變化關系

3 結束語

SL0算法一般采用高斯函數作為平滑函數來近似l0范數，但是高斯函數對l0范數的近似程度不夠理想，并且利用最速下降法求解函數極值問題時會產生“鋸齒效應”，從而導致該算法的稀疏信號重構性能較差。本文提出一種基于修正近似雙曲正切函數的平滑l0范數算法，該算法采用一種修正近似雙曲正切函數來逼近l0范數，同時利用牛頓法求解該函數的極值問題，從而實現了稀疏信號的高精度重構。數值仿真實驗結果表明，與其它算法相比，本文算法的稀疏信號重構性能最優。