一種魯棒的稀疏信號(hào)重構(gòu)算法

郝雯潔,齊春

(西安交通大學(xué)電子與信息工程學(xué)院,710049,西安)

?

一種魯棒的稀疏信號(hào)重構(gòu)算法

郝雯潔,齊春

(西安交通大學(xué)電子與信息工程學(xué)院,710049,西安)

針對(duì)稀疏信號(hào)重構(gòu)性能不穩(wěn)定的問(wèn)題,結(jié)合半閾值迭代算法,提出了一種魯棒的稀疏信號(hào)重構(gòu)算法。該算法首先對(duì)隨機(jī)信號(hào)采用半閾值迭代算法進(jìn)行重構(gòu),以獲得初步的重構(gòu)信號(hào),然后改變迭代初值和參數(shù)初值進(jìn)行新的迭代計(jì)算,同時(shí)增加一個(gè)新的循環(huán)終止條件,在保證算法穩(wěn)定性與收斂速度的同時(shí),使迭代結(jié)果跳出相對(duì)誤差較大的局部極小點(diǎn)而收斂于誤差較小的點(diǎn)成為可能,提高了重構(gòu)信號(hào)的成功率。對(duì)該算法進(jìn)行了信號(hào)重構(gòu)和圖像重構(gòu)2個(gè)方面的實(shí)驗(yàn),結(jié)果表明,與半閾值算法及相關(guān)算法比較,無(wú)論是對(duì)高斯信號(hào)、符號(hào)信號(hào)還是自然圖像信號(hào),該算法重構(gòu)信號(hào)的成功率都有明顯提高,較半閾值算法平均提高了約30%～40%,表現(xiàn)出較強(qiáng)的魯棒性。

稀疏信號(hào);重構(gòu);魯棒;局部極小點(diǎn)

近年來(lái),隨著科學(xué)技術(shù)的快速發(fā)展,高分辨率圖像采集的要求越來(lái)越高,需要處理的數(shù)據(jù)量以極大的速度在增加,這給信號(hào)處理的能力提出了更高的要求。信號(hào)的稀疏表示理論越來(lái)越引起人們的廣泛關(guān)注和研究[1-3],而快速穩(wěn)健的稀疏信號(hào)重構(gòu)算法對(duì)該理論的應(yīng)用發(fā)展起著至關(guān)重要的作用,目前已發(fā)展了多種算法。文獻(xiàn)[4]提出的匹配追蹤(MP)算法,通過(guò)在過(guò)完備庫(kù)中自適應(yīng)地選取能夠表達(dá)信號(hào)局部特性的時(shí)頻原子,最終將信號(hào)表示為時(shí)頻原子的線性組合,但由于該算法所選原子具有非正交性,因而其收斂速度慢。正交匹配追蹤(OMP)算法[5]對(duì)MP算法進(jìn)行了改進(jìn),通過(guò)對(duì)已選擇原子集合進(jìn)行正交化以保證迭代的最優(yōu)性,從而減少迭代次數(shù)。隨后提出的規(guī)則化正交匹配追蹤(ROMP)算法[6]、壓縮采樣匹配追蹤(CoSaMP)算法[7]等都有不同程度的改進(jìn),得到了更好的稀疏信號(hào)重構(gòu)效果。

2012年,由徐宗本等人提出了基于l1/2范數(shù)的半閾值迭代算法[8],相比基于l1范數(shù)最小化的算法,該方法具有所需觀測(cè)點(diǎn)數(shù)少、運(yùn)算速度快等特點(diǎn),因此極具研究?jī)r(jià)值,但在實(shí)際應(yīng)用中,該算法的信號(hào)重構(gòu)性能并不穩(wěn)定,有些信號(hào)不能得到成功重構(gòu)。本文對(duì)文獻(xiàn)[8]算法進(jìn)行了進(jìn)一步研究和改進(jìn),提出了一種魯棒的稀疏信號(hào)重構(gòu)算法,通過(guò)改變迭代初值和更新參數(shù)初值,在保證算法穩(wěn)定性和收斂速度的同時(shí),使重構(gòu)信號(hào)跳出相對(duì)誤差較大的局部極小點(diǎn)成為可能;同時(shí),根據(jù)收斂性判斷公式,增加了新的循環(huán)終止條件,對(duì)誤差進(jìn)一步約束,通過(guò)多次循環(huán)迭代,使算法收斂于誤差較小的點(diǎn),將半閾值算法不能重構(gòu)的信號(hào)成功重構(gòu),提高了重構(gòu)信號(hào)的成功率,獲得了更好的稀疏信號(hào)重構(gòu)能力。

1 半閾值迭代算法

1.1 信號(hào)的稀疏表示

設(shè)有一長(zhǎng)度為N的信號(hào)x∈RN,A是一個(gè)M×N的觀測(cè)矩陣,并且M?N,觀測(cè)值y=Ax是一個(gè)M維向量,則信號(hào)的重建可表示為

‖x‖0s.t.y=Ax

(1)

即利用觀測(cè)向量y通過(guò)求解該優(yōu)化問(wèn)題來(lái)重構(gòu)原信號(hào)。然而,式(1)是NP難的,很難用現(xiàn)有的優(yōu)化算法得到求解。進(jìn)一步研究發(fā)現(xiàn),由于信號(hào)是稀疏的,當(dāng)觀測(cè)矩陣滿足限制等距條件(restricted isometry property,RIP)[9]時(shí),信號(hào)就可能由觀測(cè)值精確重構(gòu),并指出可將其轉(zhuǎn)化為等效的l1范數(shù)凸集優(yōu)化問(wèn)題[1]進(jìn)行求解,即

‖x‖1s.t.y=Ax

(2)

1.2 半閾值迭代算法

雖然l1范數(shù)最小化為凸優(yōu)化問(wèn)題易于求解,但實(shí)際應(yīng)用中發(fā)現(xiàn),該方法得到的解并不是最優(yōu)的[10-11]。為此,Xu等人通過(guò)使用一種相位圖的處理方法研究發(fā)現(xiàn),運(yùn)用l1/2范數(shù)代替l1范數(shù)求解最優(yōu)化問(wèn)題可產(chǎn)生更加稀疏的解[8],于是提出了半閾值迭代算法的基本模型[12]

‖x‖1/2s.t.y=Ax

(3)

然而,式(3)是一個(gè)非凸優(yōu)化問(wèn)題,很難用一種高效的算法來(lái)求解。結(jié)合有關(guān)非凸優(yōu)化問(wèn)題的一些解決方法[11,13],文獻(xiàn)[12]通過(guò)使用閾值迭代算法求解該問(wèn)題,推導(dǎo)得出其表達(dá)式

xn=H(B(xn-1))

(4)

B(xn-1)=xn-1+μAT(y-Axn-1)

(5)

式中:H(x)=(h(x1),h(x2),…,h(xN))T為由半閾值函數(shù)h導(dǎo)出的半閾值算子,其表達(dá)式為

h(xn)=

(6)

式中

(7)

(8)

(9)

(10)

其中,[B(xn)]S+1是B(xn)按照由大到小排列后的第S+1個(gè)。算法以x0=0為迭代初值,通過(guò)不斷迭代直至滿足|xn-xn-1|<ε條件時(shí)迭代終止,得到重構(gòu)信號(hào)。

2 魯棒的稀疏信號(hào)重構(gòu)算法

半閾值迭代算法是一種有效的信號(hào)重構(gòu)算法,已得到廣泛的應(yīng)用[14-16]。然而,非凸優(yōu)化問(wèn)題可能存在多個(gè)局部極小點(diǎn),該算法僅能保證收斂于某一局部極小點(diǎn)[17],當(dāng)陷入一個(gè)相對(duì)誤差較大的局部極小點(diǎn)時(shí),迭代終止條件|xn-xn-1|<ε也可能得到滿足,但此時(shí)并未成功重構(gòu)信號(hào),從而影響了信號(hào)重構(gòu)的成功率。針對(duì)上述問(wèn)題,本文提出了一種魯棒的稀疏信號(hào)重構(gòu)算法。算法的具體步驟如下:

(1)參數(shù)初始化,x0=0,根據(jù)式(5)、(8)～(10)計(jì)算參數(shù)初值B(x0)、μ、λ0、t0;

(2)運(yùn)用半閾值迭代算法獲得重構(gòu)信號(hào)xn;

(3)根據(jù)式(5)計(jì)算B(xn);

(4)判斷迭代結(jié)果是否滿足新的循環(huán)終止條件

|B(xn)-xn|<ε

(11)

(6)返回步驟(2),直到算法迭代結(jié)果滿足式(11)。

雖然改變了迭代初值使算法跳出局部極小點(diǎn)成為可能,但由于半閾值算法的迭代終止條件|xn-xn-1|<ε只能使迭代結(jié)果收斂于某一局部極小點(diǎn),并不能保證恢復(fù)得到原稀疏信號(hào),因此本文算法在此基礎(chǔ)上增加了新的循環(huán)終止條件|B(xn)-xn|<ε。為了進(jìn)一步說(shuō)明該終止條件的作用,引入條件數(shù)的概念,條件數(shù)是指線性方程y=Ax的解對(duì)y中誤差或不確定度的敏感性的度量。定義矩陣A的條件數(shù)等于A的范數(shù)與A的逆的范數(shù)的乘積,即cond(A)=‖A‖‖A-1‖, 由于B(xn) =xn+μAT·

(y-Axn)(式(5)),將式(5)代入式(11)得到

|μAT(y-Axn)|<ε

(12)

另外,對(duì)于Axn=y-r在等式兩邊同時(shí)左乘A的逆矩陣,可得xn=A-1(y-r)(r為誤差),以及x*=A-1y(x*為真值),因此可以得到誤差向量

‖e‖=‖x*-xn‖=‖A-1r‖≤‖A-1‖‖r‖

(13)

同時(shí)得到觀測(cè)值‖y‖=‖Ax*‖≤‖A‖‖x*‖,進(jìn)一步推導(dǎo)可得

(14)

結(jié)合式(13)、(14)可以得到

(15)

由于條件數(shù)總是大于1的,因此‖y-Axn‖小的擾動(dòng)可能會(huì)造成‖x*-xn‖形成較大的誤差。通常情況下,真值是未知的,為了盡量減小真值與所得值的誤差,對(duì)‖y-Axn‖進(jìn)行約束,使誤差e保持在一個(gè)較小的范圍內(nèi),從而得到相對(duì)誤差較小的重構(gòu)信號(hào),提高算法重構(gòu)信號(hào)的成功率。

為了驗(yàn)證本文算法的有效性,對(duì)大量的隨機(jī)稀疏信號(hào)進(jìn)行實(shí)驗(yàn)。為了方便敘述,本文將一次改變迭代初值進(jìn)行迭代計(jì)算得到重構(gòu)信號(hào)稱(chēng)為一次循環(huán),將信號(hào)長(zhǎng)度(即信號(hào)點(diǎn)數(shù))用N表示。圖1給出了運(yùn)用本文算法多次循環(huán)對(duì)信號(hào)進(jìn)行重構(gòu)的分步結(jié)果圖。可以看出,第1次循環(huán)即運(yùn)用半閾值算法所得到的重構(gòu)信號(hào)與原稀疏信號(hào)的差異很大,很多點(diǎn)處的信號(hào)值都沒(méi)有得到成功重構(gòu),而運(yùn)用本文算法隨著循環(huán)次數(shù)的增多,重構(gòu)得到的信號(hào)與原信號(hào)的差異逐漸減小,在第6次循環(huán)結(jié)束后,成功重構(gòu)信號(hào)。為了定量分析本文算法的性能, 表1給出了5組不同隨機(jī)稀疏信號(hào)每次循環(huán)得到的重構(gòu)信號(hào)與原稀疏信號(hào)的均方誤差(MSE)值。從表1中的數(shù)據(jù)可以看出,第1次循環(huán)得到的重構(gòu)信號(hào)均方誤差值較大,此時(shí)認(rèn)為信號(hào)沒(méi)有成功重構(gòu),而運(yùn)用本文算法,經(jīng)過(guò)多次循環(huán)迭代后,最終得到均方誤差值很小的信號(hào),即本文算法將半閾值算法不能重構(gòu)的信號(hào)成功重構(gòu)。

(a)第1次循環(huán)(Half算法) (b)第2次循環(huán) (c)第3次循環(huán)

(d)第4次循環(huán) (e)第5次循環(huán) (f)第6次循環(huán)圖1 本文算法多次循環(huán)重構(gòu)信號(hào)的分步結(jié)果圖

表1 信號(hào)重構(gòu)分步均方誤差值

注:黑體數(shù)據(jù)為符合要求的重構(gòu)信號(hào)。

3 實(shí)驗(yàn)結(jié)果及分析

為了驗(yàn)證本文算法的有效性,進(jìn)行了信號(hào)重構(gòu)和圖像重構(gòu)2個(gè)方面的實(shí)驗(yàn),并與一些信號(hào)重構(gòu)的主流算法進(jìn)行對(duì)比,如硬閾值迭代算法(IHT)[18]、正交匹配追蹤算法(OMP)[5]、規(guī)則化正交匹配追蹤算法(ROMP)[6]、壓縮采樣匹配追蹤算法(CoSaMP)[7]等。通過(guò)大量的實(shí)驗(yàn)數(shù)據(jù)分析比較來(lái)評(píng)價(jià)算法的性能。

3.1 信號(hào)重構(gòu)實(shí)驗(yàn)

實(shí)驗(yàn)使用長(zhǎng)度N=256、稀疏度S從1到100連續(xù)變化的隨機(jī)高斯信號(hào)和隨機(jī)符號(hào)信號(hào)2種稀疏信號(hào)來(lái)模擬可能遇到的信號(hào),即信號(hào)非零元素的幅值分別服從正態(tài)分布和1,-1分布。實(shí)驗(yàn)所用的觀測(cè)矩陣為高斯隨機(jī)矩陣,滿足RIP條件,觀測(cè)點(diǎn)數(shù)M=130,使用原信號(hào)與重構(gòu)信號(hào)的均方誤差值(MSE)作為判決條件,門(mén)限值取為10-4,為了保證實(shí)驗(yàn)結(jié)果的可靠性,本文進(jìn)行了1 000次重復(fù)實(shí)驗(yàn),運(yùn)用成功重構(gòu)信號(hào)的概率來(lái)評(píng)價(jià)算法的性能。

(a)隨機(jī)高斯信號(hào)

(b)隨機(jī)符號(hào)信號(hào)圖2 幾種算法對(duì)不同稀疏度信號(hào)的重構(gòu)成功率

幾種不同算法在固定觀測(cè)點(diǎn)數(shù)情況下對(duì)不同稀疏度信號(hào)的重構(gòu)成功率情況如圖2所示,可以看出,隨著稀疏度的增加,各算法的性能均有所下降,半閾值迭代算法在各算法中的信號(hào)重構(gòu)成功率較高,而本文算法相比半閾值算法性能又有了明顯的提高,信號(hào)重構(gòu)成功率平均提高了約30%～40%,并且大多數(shù)算法對(duì)隨機(jī)符號(hào)信號(hào)重構(gòu)時(shí)性能明顯下降,而本文算法的性能基本保持不變,體現(xiàn)了較強(qiáng)的魯棒性。

3.2 圖像重構(gòu)實(shí)驗(yàn)

實(shí)驗(yàn)使用一幅64×64像素的Shepp-Logan大腦圖進(jìn)行仿真實(shí)驗(yàn),首先對(duì)該圖像進(jìn)行4層小波分解,得到N為4 096、稀疏度為723的稀疏信號(hào),再運(yùn)用幾種算法在不同觀測(cè)點(diǎn)數(shù)情況下對(duì)信號(hào)進(jìn)行重構(gòu),最后將重構(gòu)信號(hào)進(jìn)行小波逆變換得到重構(gòu)圖像。實(shí)驗(yàn)結(jié)果如表2所示。為了定量分析本文算法重構(gòu)圖像的性能,表3給出了表2重構(gòu)圖像的峰值信噪比RPSN值。

由表2的實(shí)驗(yàn)結(jié)果可以看出,在觀測(cè)點(diǎn)數(shù)較多的情況下,6種算法都能夠得到較好的重構(gòu)圖像,隨著觀測(cè)點(diǎn)數(shù)的減少,重構(gòu)圖像逐漸模糊;從表3的數(shù)據(jù)中清楚地看出,當(dāng)觀測(cè)點(diǎn)數(shù)下降到1 600時(shí),各算法的性能都迅速下降,只有本文算法的重構(gòu)圖像仍保持著較高的RPSN值,可見(jiàn)在觀測(cè)點(diǎn)數(shù)較少的情況下,本文算法的優(yōu)勢(shì)更為突出,相比半閾值算法重構(gòu)圖像的RPSN值有了明顯的提高,具有較強(qiáng)的圖像重構(gòu)能力。

表2 6種算法在不同觀測(cè)點(diǎn)數(shù)情況下的重構(gòu)圖像

表3 不同采樣率下6種算法重構(gòu)圖像的峰值信噪比

算法RPSN/dBM=2500M=2050M=1600M=1450本文192.2186.7166.238.7Half104.896.787.120.2IHT166.0157.219.317.6OMP288.7278.662.334.2ROMP20.611.96.56.3CoSaMP281.2270.16.15.6

4 結(jié) 論

針對(duì)稀疏信號(hào)重構(gòu)性能不穩(wěn)定的缺陷,本文提出了一種魯棒的稀疏信號(hào)重構(gòu)算法。通過(guò)改變半閾值迭代算法的迭代初值和更新參數(shù),在保證算法穩(wěn)定性和收斂速度的同時(shí),使迭代結(jié)果跳出局部極小點(diǎn)成為可能;同時(shí),提出了新的循環(huán)終止條件,使算法收斂于相對(duì)誤差較小的點(diǎn),將半閾值算法不能重構(gòu)的信號(hào)成功重構(gòu),提高了算法重構(gòu)信號(hào)的成功率。實(shí)驗(yàn)結(jié)果表明,相對(duì)比其他5種算法,本文算法重構(gòu)信號(hào)的成功率有了明顯提高,在觀測(cè)點(diǎn)數(shù)較少的情況下仍能獲得較清晰的重構(gòu)圖像,并且對(duì)于不同種類(lèi)的信號(hào),本文算法均能獲得較好的效果,表現(xiàn)出較強(qiáng)的魯棒性。

[1]CANDES E, WAKIN M, BOYD S.Enhancing sparsity by reweightedL1minimization [J].Fourier Analysis and Applications, 2008, 14(5):877-905.

[2]MALIOUTOV D M, CETIN M, WILLSKY A S.A sparse signal reconstruction perspective for source localization with sensor arrays [J].IEEE Transactions on Signal Processing, 2005, 53(8):3010-3022.

[3]史金剛, 齊春.一種雙約束稀疏模型圖像修復(fù)算法 [J].西安交通大學(xué)學(xué)報(bào), 2012, 46(2):6-11.SHI Jingang, QI Chun.An image inpainting algorithm based on sparse modeling with double constraints [J].Journal of Xi’an Jiaotong University, 2012, 46(2):6-11.

[4]MALLAT S G, ZHANG Z.Matching pursuits with time-frequency dictionaries [J].IEEE Transactions on Signal Processing, 1993, 41(12):3397-3415.

[5]TROPP J A, GILBERT A C.Signal recovery from random measurements via orthogonal matching pursuit [J].IEEE Transactions on Information Theory, 2007, 53(12):4655-4666.

[6]NEEDELL D, VERSHYNIN R.Uniform uncertainty principle and signal recovery via regularized orthogonal matching pursuit [J].Foundations of Computational Mathematics, 2009, 9(3):317-334.

[7]NEEDELL D, TROPP J A.CoSaMP:iterative signal recovery from incomplete and inaccurate samples [J].Applied and Computational Harmonic Analysis, 2009, 26(3):301-321.

[8]XU Zongben, GUO Hailiang, WANG Yao, et al.Representative ofL1/2regularization amongLq(0

[9]CANDES E J, ROMBERG J, TAO T.Robust uncertainty principles:exact signal reconstruction from highly incomplete frequency information [J].IEEE Transactions on Information Theory, 2006, 52(2):48.

[10]楊揚(yáng), 劉哲, 呂方園.一種迭代加權(quán)l(xiāng)1范數(shù)的信號(hào)優(yōu)化恢復(fù)方法 [J].計(jì)算機(jī)工程與應(yīng)用, 2010, 46(3):128-130.YANG Yang, LIU Zhe, LV Fangyuan.Signal recovery based on iterative weightedl1norm [J].Computer Engineering and Applications, 2010, 46(3):128-130.

[11]桂麗華, 徐兵, 崔永福.基于lq最小化算法的稀疏信號(hào)分離 [J].通信技術(shù), 2010, 43(8):84-86.GUI Lihua, XU Bing, CUI Yongfu.Sparse signal separation based onlqminimization [J].Communications Technology, 2010, 43(8):84-86.

[12]XU Zongben, CHANG Xiangyu, XU Fengmin, et al.L1/2regularization:a thresholding representation theory and a fast solver [J].IEEE Transactions on Neural Networks and Learning Systems, 2012, 23(7):1013-1027.

[13]GASSO G, RAKOTOMAMONJY A, CANU S.Recovering sparse signals with a certain family of nonconvex penalties and DC programming [J].IEEE Transactions on Signal Processing, 2009, 57(12):4686-4698.

[14]QIAN Y T , JIA S, ZHOU J, et al.Hyperspectral unmixing viaL1/2sparsity-constrained matrix factorization [J].IEEE Transactions on Geoscience and Remote Sensing, 2011, 49(11):4282-4297.

[15]ZENG Jinshan, XU Zongben, ZHANG Bingchen, et al.AcceleratedL1/2regularization based SAR imaging via BCR and reduced Newton skills [J].Signal Processing, 2013, 93(7):1831-1844.

[16]XU Chen, PENG Zhiming, JING Wenfeng.Sparse kernel logistic regression based onL1/2regularization [J].Science China:Information Sciences, 2013, 56(4):1-16.

[17]ZENG Jinshan, LIN Shaobo, WANG Yao, et al.L1/2regularization:convergence of iterative half thresholding algorithm [J].IEEE Transactions on Signal Processing, 2014, 62(9):2317-2329.

[18]BLUMENSATH T, DAVIES M E.Iterative hard thresholding for compressed sensing [J].Applied and Computational Harmonic Analysis, 2009, 27(3):265-274.

(編輯 劉楊)

A Robust Reconstruction Algorithm for Sparse Signals

HAO Wenjie,QI Chun

(School of Electronics and Information Engineering, Xi’an Jiaotong University, Xi’an 710049, China)

A robust reconstruction algorithm for sparse signals is proposed to focus on the problem that sparse signal reconstruction has unstable performance.Firstly, the signal is reconstructed by using the half thresholding algorithm.Then, initial value and initial parameters are changed to perform new iterations, and a new termination condition is applied, so that it is possible for the algorithm to escape from the local minima with large error, and the success rate of the signal reconstruction is improved.Experimental results of signal recovery and image reconstruction on Gaussian signals, sign signals and natural image signals show that the proposed algorithm increases the success rate of recovering signals, and its performance is better than that of the half thresholding algorithm and other competitive ones.Comparisons with the half thresholding algorithm show that the success rate of signal recovery of the proposed algorithm has an increase of 30%-40% in average with better robustness.

sparse signal; reconstruction; robust; local minima

2014-04-20。 作者簡(jiǎn)介:郝雯潔(1989—),女,碩士生;齊春(通信作者),男,教授,博士生導(dǎo)師。 基金項(xiàng)目:國(guó)家自然科學(xué)基金資助項(xiàng)目(60972124);國(guó)家“863計(jì)劃”資助項(xiàng)目(2009AA01Z321);教育部高等學(xué)校博士學(xué)科點(diǎn)專(zhuān)項(xiàng)科研基金資助項(xiàng)目(20110201110012)。

時(shí)間:2015-01-16

http:∥www.cnki.net/kcms/detail/61.1069.T.20150116.1510.003.html

10.7652/xjtuxb201504016

TN911.7

A

0253-987X(2015)04-0098-06