基于壓縮感知理論NSL0算法的改進*

陶 亮，劉海鵬，王 蒙

(昆明理工大學 信息工程與自動化學院，云南 昆明 650500)

0 引言

傳統的信號采樣受限于奈奎斯特定理[1-2]，采樣速率低下，急需一種新的信號采樣方法，在這種情況下壓縮感知[3]被提了出來。

壓縮感知中最重要的環節就是信號重構，它的作用就是在觀測值較少的情況下精確、快速地恢復原信號。目前最直接的重構方法就是在L0范數下求解最優化表達式[4-5]。于是，為了提高信號的重構速率，MOHIMSNI G H等人在2009年提出了基于平滑L0范數的重建。隨后在此算法上，研究者們相繼提出了基于SL0的TSL0(Thresholded SL0)[6]算法、基于SL0的NSL0(Newton SL0)算法[7]和L0AM(L0 Norm Approximation)算法[8]。在以上所提算法中，NSL0算法重構得到的圖像是最優的[9]，但NSL0算法重構質量依然不足。于是本文在NSL0算法的基礎上提出了ACNSL0算法，該算法采用反余弦函數來近似估計L0范數，結合修正牛頓法[10-12]和阻尼牛頓法，獲得的一種更快速、高效的信號重建算法，經過仿真，得出該算法在重構誤差和峰值信噪比[13-14]方面有較大改善。

1 NSL0算法

NSL0算法的主要思想是采用雙曲正切函數族來取代SL0所采用的高斯函數族，用修正牛頓法取代最速下降法，而且相對于高斯函數，雙曲正切函數更陡峭，所以會更加逼近L0范數，重構的效果理論上更好。雙曲正切函數的數學表達式如下：

式中，si為稀疏系數s的分量，σ 為趨近于0的遞減參數。在NSL0算法中，σ 的取值尤其關鍵，由圖1可以看出，當σ 較大時，函數值Fσ(si)變得非常平滑，局部最大值也變得極少，可以避免受到局部極值點的影響；當σ非常小時，Fσ與L0范數非常接近，但是函數曲線很不平滑。基于這種性質，所以一開始直接選取σ 的最大值(即4max|si|)，然后以一定間隔遞減，最后逐漸逼近全局最優解。因為NSL0算法精度高，所以得到了廣泛的應用。但是NSL0算法采用雙曲正切函數來逼近L0范數未必是最優的，也就是它的重構質量依然不夠好，故本文提出來一種改進的ACNSL0算法。

圖1 雙曲正切函數在不同σ 下的函數逼近效果

2 ACNSL0算法

ACNSL0算法主要原理是采用反余弦函數替代雙曲正切函數去逼近L0范數，如圖2所示，由于反余弦函數比SL0采用的高斯函數、NSL0采用的雙曲正切函數更具有“陡峭性”，因此其在數學意義上也更逼近于L0范數，因而理論上重構效果也更好，并加入牛頓阻尼，以此選擇合適的步長，不斷更新，直到重構出信號。

本文提出的反余弦函數的數學表達式如下：

其中，Re表示函數值fσ(si)取實部，μ 可以取一個大于1的常數。由此可得到：

定義反正弦函數族如下：

圖2 當σ=0.1時3種函數逼近效果對比圖

其中，N表示信號的長度，當遞減參數σ 非常小時，函數Fσ(s)的函數值等同于稀疏系數s中不為0元素的個數，所以公式min||s||0s.t.y=As可以轉換為：

其中，||s||0表示稀疏系數中非0系數的個數。該算法同NSL0算法一致，采用修正牛頓法，從而避免出現“鋸齒”現象，修正牛頓公式計算如下：

接著求二階偏導：

由于海森矩陣的特征值不一定是正定的，現提出式(8)表示的構造矩陣對其進行修正，求得：

得到修正法牛頓方向：

但是上面提到的修正牛頓法存在一個缺點，就是迭代公式為定長迭代，對于目標函數，有時候會出現迭代發散的情況，這表明牛頓法不能保證函數值穩定地下降，對此，為了消除該弊病，引用了牛頓阻尼法。牛頓阻尼法的最優步長因子滿足：

其中，sk表示k次迭代后的重構系數，dk表示k次迭代后的步長，由式(10)可得到本算法的最優步長因子為γk=-sk/dk。

本文提出的算法(ACNSL0算法)如下：

輸入：傳感矩陣AM×N，觀測矩陣YM×N；

(1)初始s=AT(AAT)-1Y；σj=βσj-1，σ 為遞減數列，β 為衰減因子。

(2)外部循環：j=1，2，3，…，J。

①令σ=σj；

③內部循環：l=1，2，3，…，L。

(a)計算修正后的牛頓方向：

(b)用牛頓阻尼法選擇最優步長γ，對重構信號進行更新s=s+γd；

(c)根據梯度投影原理，得到s←s-AT(AAT)-1(As-y)；

④σj=βσj-1，更新σ，其中β 為衰減因子

3 仿真結果與分析

3.1 一維信號測試

為了測試ACNSL0算法對信號的重構效果，首先用一維信號進行仿真測試，信號的長度為N=128，仿真結果如圖3所示，帶空心圓球的黑線表示重構信號，黑線表示重構信號。由圖3可以看出，兩種類型的黑線基本重合，且重構誤差為2.208 4×10-13，因此可得出本算法可以達到對一維信號的高精度重構。

圖3 ACNSL0算法的一維信號測試

然后給出3種算法的峰值信噪比(PSNR)對比圖，如圖4所示，隨著壓縮比的增大，3種算法的峰值信噪比也相對增大，但是ACNSL0算法壓縮比在[0.1，0.9]區間中始終大于另外兩種算法，可見其重構性能的優越性。

圖4 3種算法的SRNR對比圖

3.2 二維圖像重構測試

為了更深一步驗證該算法的性能，最后驗證其對二維圖片的重構效果。仿真結果如圖5～圖7所示。

圖5 3種算法在壓縮比為0.4時的二維重構實驗

圖5～圖7分別是SL0、NSL0、ACNSL0算法在壓縮比分別為0.4、0.5和0.6時的重構圖像，隨著壓縮比的增大，3種算法的峰值信噪比(SRNR)均明顯上升。但從表1～表3均可以可以看出，雖然本算法重構時間多于另外兩種算法，但無論壓縮比為0.4、0.5還是0.6時，ACNSL0算法的峰值信噪比始終最大，重構誤差也是最小的。由此可以看出該算法的優越性。

4 結論

針對壓縮感知中NSL0算法信號重構精度的不足，本文在此算法的基礎上提出了一種改進算法，命名為ACNSL0算法，該算法用反余弦函數代替NSL0所采用雙曲正切函數去逼近L0范數，并引入牛頓阻尼法使本算法穩定收斂，經過一維和二維仿真對比，發現該算法的重構質量明顯優于另外兩種算法。但在運行時間上，由于ACNSL0算法的復雜性，故稍慢于另兩種算法，后續將針對算法運行時間方面做進一步研究。

圖6 3種算法在壓縮比為0.5時的二維重構實驗

圖7 3種算法在壓縮比為0.6時的二維重構實驗

表1 SL0、NSLO、ACNSL0算法壓縮比為0.4時二維重構性能比較

表2 SL0、NSL0、ACNSL0算法壓縮比為0.5時二維重構性能比較

表3 SL0、NSL0、ACNSL0算法壓縮比為0.6時二維重構性能比較