聶棟棟 弓耀玲

(燕山大學(xué)理學(xué)院 河北秦皇島 066004) (niedd@ysu.edu.cn)

自壓縮感知(compressed sensing, CS)信號(hào)處理理論[1]提出以來(lái)，信號(hào)重構(gòu)作為其關(guān)鍵的環(huán)節(jié)，一直是該理論的研究重點(diǎn).信號(hào)重構(gòu)的目標(biāo)是根據(jù)非自適應(yīng)線性測(cè)量的低維數(shù)據(jù)，準(zhǔn)確而有效地恢復(fù)原始采樣獲取的高維數(shù)據(jù).在壓縮感知理論框架下，信號(hào)在特定基下或一定的變換下可稀疏表示，則信號(hào)重構(gòu)問(wèn)題可轉(zhuǎn)化為稀疏信號(hào)的重構(gòu).如何求欠定方程組最稀疏的解是稀疏重構(gòu)問(wèn)題的本質(zhì)，即l0范數(shù)的最小化問(wèn)題.

然而直接求解欠定方程組的最稀疏解是NP難問(wèn)題，處理起來(lái)非常棘手.在實(shí)際中，貪婪算法是最常見(jiàn)的近似求解方法[2-5]，如正交匹配追蹤法(orthogonal matching pursuit, OMP)[2]、梯度追蹤法(gradient pursuit, GP)[3]、子空間追蹤法(subspace pursuit, SP)[4]等，其基本思想是通過(guò)逐步迭代找到未知信號(hào)的支撐集，原信號(hào)的估計(jì)值即可利用最小二乘法得到.貪婪類(lèi)算法需要較少的計(jì)算量，但是通常估計(jì)精度不高且需要較多的觀測(cè)值.

另一種思路是尋找新的模型替代l0范數(shù)的求解.這種方法分為2步：

1) 需要找到合適的函數(shù)近似估計(jì)l0范數(shù)，由于l0范數(shù)是x的不連續(xù)函數(shù)，實(shí)際計(jì)算中不好處理，很多文獻(xiàn)常用l1范數(shù)來(lái)近似l0范數(shù)，如基追蹤法(basis pursuit, BP)[6]，其依據(jù)是l1范數(shù)最小化與l0范數(shù)最小化在滿足一定條件時(shí)具有相同的稀疏解，可以通過(guò)線性規(guī)劃方法求解.然而，l1范數(shù)不能充分反映向量x的稀疏特性，重構(gòu)時(shí)需要較多的測(cè)量值，計(jì)算量較大.高斯函數(shù)類(lèi)也是近似l0范數(shù)經(jīng)典的函數(shù)之一，基于光滑l0范數(shù)算法(smoothedl0norm, SL0)[7]是用一個(gè)連續(xù)平滑函數(shù)的極限來(lái)近似l0范數(shù)，如文獻(xiàn)[7-8]采用

(1)

對(duì)l0范數(shù)進(jìn)行近似，其中σ為趨于0的正數(shù).文獻(xiàn)[9-10]則在式(1)的基礎(chǔ)上進(jìn)一步改進(jìn)，采用式雙曲正切函數(shù)

(2)

近似l0范數(shù)，其中σ為很小的正數(shù).在文獻(xiàn)[11-13]中，用一組反正切函數(shù)

(3)

近似l0范數(shù)，其中σ為接近于0的正常數(shù).文獻(xiàn)[14]是采用復(fù)合三角函數(shù)近似l0范數(shù).但以上函數(shù)表達(dá)式均稍復(fù)雜，使得迭代計(jì)算復(fù)雜度較高.文獻(xiàn)[15]的快速稀疏信號(hào)恢復(fù)算法(AL0算法)提出用函數(shù)

(4)

2) 對(duì)新的函數(shù)模型選擇不同的線性規(guī)劃或優(yōu)化算法求解.對(duì)于算法實(shí)現(xiàn)，NSL0算法選用修正牛頓法求解最優(yōu)化問(wèn)題，需要對(duì)海森矩陣進(jìn)行修正，構(gòu)造一個(gè)可近似海森矩陣逆的正定對(duì)稱(chēng)陣作為迭代方向，一定程度上提高了收斂速度.AL0算法將問(wèn)題分解為2個(gè)最小化問(wèn)題分別求解，然后交替迭代，將解投影到可行域.本文選取高精度的牛頓迭代法，將問(wèn)題轉(zhuǎn)為無(wú)約束優(yōu)化問(wèn)題后，對(duì)無(wú)約束問(wèn)題直接應(yīng)用牛頓算法，迭代得到最優(yōu)解，不需要進(jìn)一步對(duì)解進(jìn)行投影.而且得到的牛頓方向?yàn)橄陆捣较?，不需要進(jìn)一步修正，從而減少了誤差影響，保證了精度.

信號(hào)的恢復(fù)質(zhì)量在算法的不斷改進(jìn)下有所提升，但仍存在存儲(chǔ)量大、計(jì)算復(fù)雜度高、精確度不夠高等問(wèn)題，需要進(jìn)一步研究和改進(jìn).本文在之前l(fā)0范數(shù)工作的基礎(chǔ)上，結(jié)合AL0算法快速收斂和牛頓迭代法高精度的優(yōu)點(diǎn)，提出新的基于近似l0范數(shù)的稀疏信號(hào)重構(gòu)算法，用一個(gè)簡(jiǎn)單的分式函數(shù)的和來(lái)近似估計(jì)l0范數(shù)，通過(guò)牛頓迭代算法求得稀疏解.最后，通過(guò)數(shù)值仿真和已有的相似算法及經(jīng)典的OMP算法進(jìn)行比較，并分析了本文算法恢復(fù)的信號(hào)在重構(gòu)誤差、信噪比方面的優(yōu)勢(shì).

1 壓縮感知理論

令z∈n是傳統(tǒng)采樣得到的信號(hào)，經(jīng)過(guò)正交基或緊框架ψ變換后的系數(shù)是稀疏的，即z=ψx，其中x∈n且為稀疏度.在無(wú)噪聲干擾的情形下，測(cè)量向量y可以表示為y=Φψx，其中y∈m，Φ為m×n維測(cè)量矩陣，ψ為n×n維基矩陣.令A(yù)=Φψ，則重構(gòu)問(wèn)題簡(jiǎn)化為在矩陣A和測(cè)量向量y已知的條件下，求方程組y=Ax最稀疏解的問(wèn)題，即l0范數(shù)的最小化問(wèn)題：

(5)

在實(shí)際應(yīng)用中往往會(huì)不可避免地受噪聲的影響，測(cè)量值是不精確的，令γ表示噪聲，則測(cè)量值進(jìn)一步表示為y=Ax+γ.

2 基于近似l0范數(shù)的稀疏信號(hào)重構(gòu)

2.1 l0范數(shù)近似

本文采用一個(gè)形式較為簡(jiǎn)單的分式函數(shù)

(6)

來(lái)近似l0范數(shù)，其中δ是很小的正數(shù)，實(shí)驗(yàn)中參數(shù)δ可取為一組下降且趨于0的序列.顯然有:

(7)

令:

(8)

根據(jù)l0范數(shù)的定義可知，當(dāng)δ無(wú)限趨近于0時(shí)，F(xiàn)(x)的值就無(wú)限接近于向量x中非0元的個(gè)數(shù)，即x的l0范數(shù)，故有:

(9)

因此,我們可以用式(8)來(lái)近似l0范數(shù)進(jìn)行迭代計(jì)算.式(6)的優(yōu)勢(shì)在于形式簡(jiǎn)單，尤其在算法迭代時(shí)簡(jiǎn)化了計(jì)算，同時(shí)又不降低精度.

2.2 算法實(shí)現(xiàn)

本文將最優(yōu)化問(wèn)題式(5)等價(jià)變換為拉格朗日形式最小化問(wèn)題：

(10)

其中,λ是拉格朗日乘子.然后對(duì)式(10)進(jìn)行求解.由2.1節(jié)可知，式(10)可轉(zhuǎn)化為

(11)

式(11)是無(wú)約束的最優(yōu)化問(wèn)題，最優(yōu)解x*滿足優(yōu)化條件:

(12)

進(jìn)一步有:

(13)

其中,f′(x)為f(x)的導(dǎo)數(shù)，AT為A的轉(zhuǎn)置.

當(dāng)δ→0，

(14)

為方便表示，令:

(15)

Hf=ATA+λXf,

(16)

(17)

由式(17)可以得到Hessian矩陣可表示為

(18)

顯然，Hessian矩陣Hf為正定矩陣，故得到的牛頓方向必然為下降方向，可以利用牛頓迭代[16]求解式(11)得：

(19)

式(19)即算法的迭代式，hx為迭代步長(zhǎng)，初始解x0取最小二乘解.

鑒于求逆運(yùn)算會(huì)隨著矩陣維數(shù)的增高計(jì)算量迅速加大，為盡量降低算法的計(jì)算復(fù)雜度，考慮在算法迭代中設(shè)法降低維數(shù).

由于稀疏化后的信號(hào)向量的大部分值為0或接近于0，故可以只迭代計(jì)算對(duì)應(yīng)變量的關(guān)鍵元素，如變量中絕對(duì)值最大的l個(gè)分量，忽略0元素及接近于0的元素.

令：

(20)

其中，參數(shù)α∈[0,1)，通?？扇ˇ?0.01.

xS=(xi),i∈S,

(21)

AS=(ai),i∈S,

(22)

其中，ai為A的第i列，則算法迭代的Hf可替換為

(23)

相應(yīng)地:

(24)

2.3 算法的計(jì)算復(fù)雜度分析

在算法實(shí)現(xiàn)過(guò)程中，直接計(jì)算式(19)時(shí)，涉及到矩陣和向量的乘積及矩陣的求逆，假設(shè)A是n×n矩陣，y為n×1向量，則ATy的計(jì)算復(fù)雜度為O(n2)，對(duì)Hf求逆的計(jì)算復(fù)雜度為O(n3).

經(jīng)過(guò)降維后，令l為式(20)中S的元素個(gè)數(shù)，則如式(23)，對(duì)Hf求逆的計(jì)算復(fù)雜度變?yōu)镺(l3)，而通常情況下，l?n，從而使得本文算法每次迭代的計(jì)算復(fù)雜度維持在O(n2)，這與SL0，NSL0，OMP，AL0算法的計(jì)算復(fù)雜度均是相當(dāng)?shù)?

2.4 算法描述

本文算法的偽代碼描述如下：

算法1. 基于近似l0范數(shù)的稀疏信號(hào)重構(gòu)算法.

輸入：矩陣A、測(cè)量向量y、正則化參數(shù)λ、參數(shù)δ、終止條件δmin；

輸出：重構(gòu)信號(hào)x.

初始化：初始解x0=AT(AAT)-1y.

迭代：

步驟1. 令:

S={t:|xt|>0},
xS=(xi),i∈S,
AS=(ai),i∈S;

步驟2. 更新矩陣：

步驟3. 迭代x，

步驟4. 更新δ，δ=δ×0.5；

步驟5. 判斷算法是否終止，若δ>δmin不滿足輸出迭代的結(jié)果x，否則返回步驟1繼續(xù)迭代.

2.5 算法的理論證明

在不考慮噪聲存在的情況下，算法的理論證明如下.

證明. 由矩陣逆的分塊形式知：

(25)

(26)

將式(25)帶入式(26)并經(jīng)過(guò)推導(dǎo)可以得到:

證畢.

(ATA+λXf)-1ATy=x.

(27)

(28)

證畢.

3 仿真實(shí)驗(yàn)

為驗(yàn)證本文算法的有效性，對(duì)一維隨機(jī)稀疏信號(hào)進(jìn)行實(shí)驗(yàn)，并與經(jīng)典算法OMP及相似的AL0算法等進(jìn)行了比較.下面所有數(shù)值仿真中，矩陣A取高斯隨機(jī)矩陣, 測(cè)量值向量通過(guò)y=Ax+γ生成, 其中γ表示高斯白噪聲.實(shí)驗(yàn)采用信噪比(signal noise radio,SNR)作為評(píng)估算法精度的性能指標(biāo)，定義為

(29)

其中,xopt表示對(duì)源信號(hào)x的稀疏估計(jì)值.相對(duì)誤差定義為

(30)

實(shí)驗(yàn)中隨機(jī)產(chǎn)生稀疏信號(hào)x和矩陣A，實(shí)驗(yàn)結(jié)果在參數(shù)設(shè)定的情況下進(jìn)行100次求平均.實(shí)驗(yàn)條件為T(mén)hinkpadT410i筆記本電腦Microsoft Windows 7操作系統(tǒng)MatlabR2010a 處理平臺(tái)的運(yùn)行環(huán)境.

實(shí)驗(yàn)1. 測(cè)試不同算法的整體恢復(fù)性能.在相同取值下，信號(hào)長(zhǎng)度n=256，稀疏度k=20，測(cè)量值向量長(zhǎng)度m=128，噪聲均方差取為0.01，分別測(cè)試本文算法(Proposed)、AL0算法、SL0算法、NSL0算法及OMP算法所重建的信號(hào)在信噪比、重構(gòu)誤差和重構(gòu)時(shí)間方面的對(duì)比.結(jié)果如表1所示，可以看出，本文算法重建的信號(hào)信噪比提升幅度較大，相對(duì)誤差也較低，較優(yōu)于其他算法.

Table 1 Performance Comparison under Different Algorithms表1 各算法恢復(fù)性能比較

實(shí)驗(yàn)2. 測(cè)試在不同數(shù)量測(cè)量值的情況下，各算法的性能.信號(hào)長(zhǎng)度n=256，稀疏度k=20，測(cè)量值數(shù)量分別是100，128，150，192時(shí)，測(cè)試各算法的恢復(fù)效果.結(jié)果如圖1～3所示.

圖1是信噪比隨測(cè)量值數(shù)量的變化曲線圖.測(cè)試結(jié)果表明：在不同壓縮比下，本文算法所重建信號(hào)的信噪比均高于對(duì)比算法，信號(hào)的精確度有較大的提升.

圖2是相對(duì)誤差隨測(cè)量值數(shù)量變化的曲線圖.由圖2可以看出，在壓縮比較低時(shí)，各算法的重建誤差都比較大，但是隨著測(cè)量值數(shù)量的增加，本文算法重建信號(hào)的相對(duì)誤差比其他算法都有所降低，優(yōu)勢(shì)進(jìn)一步體現(xiàn).

Fig. 1 SNR comparison under different number of measured value圖1 不同測(cè)量數(shù)值各算法重構(gòu)信號(hào)的信噪比

Fig. 2 Relative error comparison under different number of measured value圖2 不同測(cè)量數(shù)值各算法重構(gòu)信號(hào)的相對(duì)誤差

Fig. 3 Time comparison under different number of measured value圖3 不同測(cè)量數(shù)值各算法重構(gòu)時(shí)間

圖3則展示了各算法的重構(gòu)時(shí)間，在各壓縮比下，本文算法的運(yùn)算時(shí)間要少于NSL0算法和SL0算法，和AL0算法相差不大.實(shí)驗(yàn)3. 測(cè)試算法在不同稀疏度情況下的恢復(fù)精度.信號(hào)長(zhǎng)度n=256，壓縮比m/n=0.5，稀疏度由15～35變化，分別測(cè)試各算法的恢復(fù)效果.結(jié)果如圖4所示，仿真結(jié)果表明：在不同稀疏度下，由本文算法所重建信號(hào)的信噪比均高于對(duì)比算法，尤其在稀疏度較低時(shí)，本文算法恢復(fù)的信號(hào)精度提高較大.

Fig. 4 SNR comparison under different sparseness圖4 不同稀疏度下各算法重構(gòu)信號(hào)的信噪比

實(shí)驗(yàn)4. 測(cè)試算法在不同噪聲水平下的恢復(fù)精度.信號(hào)長(zhǎng)度n=256，壓縮比m/n=0.5，噪聲均方差由0.004～0.02變化，分別測(cè)試各算法的恢復(fù)效果,結(jié)果如圖5所示.可以看出，在不同噪聲水平下，與對(duì)比算法相比，本文算法依然保持優(yōu)越性，重建信號(hào)的信噪比仍提高較大.進(jìn)一步說(shuō)明在噪聲干擾較小時(shí)，本文算法的性能要較好.

Fig. 5 SNR comparison under different noise levers圖5 不同噪聲均方差下各算法重構(gòu)信號(hào)的信噪比

4 總 結(jié)

本文在之前l(fā)0范數(shù)工作的基礎(chǔ)上，結(jié)合AL0算法快速收斂和牛頓迭代法高精度的優(yōu)點(diǎn)，用一個(gè)簡(jiǎn)單的分式函數(shù)的和來(lái)近似估計(jì)l0范數(shù)，通過(guò)牛頓迭代算法求得稀疏解，從而對(duì)AL0算法恢復(fù)信號(hào)的精度不夠高的缺陷得以改進(jìn).最后通過(guò)數(shù)值仿真，在恢復(fù)精度上和經(jīng)典的OMP算法、相似的現(xiàn)有算法進(jìn)行了比較.數(shù)值仿真結(jié)果表明：在不同壓縮比、稀疏度及噪聲干擾下，本文算法恢復(fù)精度均有較大提升，有效地改善了重建效果，提高了信號(hào)的重建質(zhì)量.

[1]Candes E J, Wakin M B. An introduction to compressive sampling[J]. IEEE Signal Processing Magazine, 2008, 25(2): 21-30

[2]Tropp J A, Gilbert A C. Signal recover from random measurements via orthogonal matching pursuit[J]. IEEE Trans Information Theory, 2007, 53(12): 4655-4666

[3]Blumensath T, Davies M E. Gradient pursuits[J]. IEEE Trans on Signal Processing, 2008, 56(6): 2370-2382

[4]Dai Wei, Milenkovic O. Subspace pursuit for compressive sensing signal reconstruction[J]. IEEE Trans Information Theory, 2009, 55(5): 2230-2249

[5]Pei Tingrui, Yang Shu, Li Zhetao, et al. Detouring matching pursuit algorithm in compressed sensing[J]. Journal of Computer Research and Development, 2014, 51(9): 2101-2107 (in Chinese)

(裴廷睿, 楊術(shù), 李哲濤, 等. 壓縮感知中迂回式匹配追蹤算法[J]. 計(jì)算機(jī)研究與發(fā)展, 2014, 51(9): 2101-2107)

[6]Chen S S B, Donoho D L, Saunders M A. Atomic decomposition by basis pursuit[J]. SIAM Review, 2001, 43(1): 129-159

[7]Mohimani H, Babaie-Zadeh M, Tutten C. A fast approach for overcomplete sparse decomposition based on smoothedl0norm[J]. IEEE Trans Information Theory, 2009, 57(1): 289-301

[8]Liu Wanjun, Wang Hongzhi, Wang Xianlong. Iterative shrinkage SL0 compressed sensing recovery algorithm[J]. Journal of Changchun University of Technology, 2014, 35(4): 434-437 (in Chinese)

(劉婉軍, 王宏志, 王賢龍. 迭代收縮SL0壓縮感知恢復(fù)算法[J]. 長(zhǎng)春工業(yè)大學(xué)學(xué)報(bào), 2014, 35(4): 434-437)

[9]Zhao Ruizhen, Lin Wanjuan, Li Hao, et al. Reconstruction algorithm for compressive sensing based on smoothedl0norm and revised Newton method[J]. Journal of Computer-Aided Design & Computer Graphics, 2012, 24(4): 478-484 (in Chinese)

(趙瑞珍, 林婉娟, 李浩, 等. 基于光滑l0范數(shù)和修正牛頓法的壓縮感知重建算法[J]. 計(jì)算機(jī)輔助設(shè)計(jì)與圖像學(xué)學(xué)報(bào), 2012, 24(4): 478-484)

[10]Yang Lianglong, Zhao Shengmei, Zheng Baoyu, et al. The improved reconstruction algorithm for compressive sensing on SL0[J]. Signal Processing, 2012, 28(6): 834-841 (in Chinese)

(楊良龍, 趙生妹, 鄭寶玉, 等. 基于SL0壓縮感知信號(hào)重建的改進(jìn)算法[J]. 信號(hào)處理, 2012, 28(6): 834-841)

[11]Wang Junhua, Huang Zhitao, Zhou Yiyu, et al. Robust sparse recovery based on approximatel0norm[J]. Acta Electronica Sinica, 2012, 46(6): 1185-1189 (in Chinese)

(王軍華, 黃知濤, 周一宇, 等. 基于近似l0范數(shù)的穩(wěn)健稀疏重構(gòu)算法[J]. 電子學(xué)報(bào), 2012, 40(6): 1185-1189)

[12]Xiang Gao, Zhang Xiaoling, Shi Jun. Complex-valued sparse reconstruction via arctangent regularization[J]. Signal Processing, 2014, 104(6): 450-463

[13]Li Ying, Wang Ze, Wang Junhua, et al. Sparse signal reconstruction based onl0norm approximation minimization[J]. Computer Engineering and Application, 2015, 51(10): 200-204 (in Chinese)

(李穎, 王澤, 王軍華, 等. 基于l0范數(shù)近似最小化的稀疏信號(hào)重構(gòu)方法[J]. 計(jì)算機(jī)工程與應(yīng)用, 2015, 51(10): 200-204)

[14]Qi Huanfang, Xu Yuanhao. Improved SL0 algorithm for compressive sensing signal reconstruction[J]. Electronic Science & Technology, 2015, 28(4): 27-30 (in Chinese)

(齊煥芳, 徐源浩. 用于壓縮感知信號(hào)重建的SL0改進(jìn)算法[J]. 電子科技學(xué)報(bào), 2015, 28(4): 27-30)

[15]Wu Feiyun, Zhou Yuehai, Tong Feng. A fast sparse signal recovery algorithm based on approximatel0norm and hybrid optimization[J]. Acta Automatica Sinica, 2014, 40(10): 2145-2150 (in Chinese)

(伍飛云, 周躍海, 童峰. 基于似零范數(shù)和混合優(yōu)化的壓縮感知信號(hào)快速重構(gòu)算法[J]. 自動(dòng)化學(xué)報(bào), 2014, 40(10): 2145-2150)

[16]Shi Jun, Ding Renhuan, Xiang Gao, et al. Complex-valued sparse recovery via double-threshold sigmoid penalty[J]. Signal Processing, 2015, 114: 231-244