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

郝雯潔,齊春

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

?

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

郝雯潔,齊春

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

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

稀疏信號;重構(gòu);魯棒;局部極小點

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

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

1 半閾值迭代算法

1.1 信號的稀疏表示

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

‖x‖0s.t.y=Ax

(1)

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

‖x‖1s.t.y=Ax

(2)

1.2 半閾值迭代算法

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

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

(3)

然而,式(3)是一個非凸優(yōu)化問題,很難用一種高效的算法來求解。結(jié)合有關(guān)非凸優(yōu)化問題的一些解決方法[11,13],文獻(xiàn)[12]通過使用閾值迭代算法求解該問題,推導(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個。算法以x0=0為迭代初值,通過不斷迭代直至滿足|xn-xn-1|<ε條件時迭代終止,得到重構(gòu)信號。

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

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

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

(2)運用半閾值迭代算法獲得重構(gòu)信號xn;

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

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

|B(xn)-xn|<ε

(11)

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

雖然改變了迭代初值使算法跳出局部極小點成為可能,但由于半閾值算法的迭代終止條件|xn-xn-1|<ε只能使迭代結(jié)果收斂于某一局部極小點,并不能保證恢復(fù)得到原稀疏信號,因此本文算法在此基礎(chǔ)上增加了新的循環(huán)終止條件|B(xn)-xn|<ε。為了進(jìn)一步說明該終止條件的作用,引入條件數(shù)的概念,條件數(shù)是指線性方程y=Ax的解對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)

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

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

(13)

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

(14)

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

(15)

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

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

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

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

3 實驗結(jié)果及分析

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

3.1 信號重構(gòu)實驗

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

(a)隨機(jī)高斯信號

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

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

3.2 圖像重構(gòu)實驗

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

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

表2 6種算法在不同觀測點數(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é) 論

針對稀疏信號重構(gòu)性能不穩(wěn)定的缺陷,本文提出了一種魯棒的稀疏信號重構(gòu)算法。通過改變半閾值迭代算法的迭代初值和更新參數(shù),在保證算法穩(wěn)定性和收斂速度的同時,使迭代結(jié)果跳出局部極小點成為可能;同時,提出了新的循環(huán)終止條件,使算法收斂于相對誤差較小的點,將半閾值算法不能重構(gòu)的信號成功重構(gòu),提高了算法重構(gòu)信號的成功率。實驗結(jié)果表明,相對比其他5種算法,本文算法重構(gòu)信號的成功率有了明顯提高,在觀測點數(shù)較少的情況下仍能獲得較清晰的重構(gòu)圖像,并且對于不同種類的信號,本文算法均能獲得較好的效果,表現(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é)報, 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]楊揚, 劉哲, 呂方園.一種迭代加權(quán)l(xiāng)1范數(shù)的信號優(yōu)化恢復(fù)方法 [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最小化算法的稀疏信號分離 [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。 作者簡介:郝雯潔(1989—),女,碩士生;齊春(通信作者),男,教授,博士生導(dǎo)師。 基金項目:國家自然科學(xué)基金資助項目(60972124);國家“863計劃”資助項目(2009AA01Z321);教育部高等學(xué)校博士學(xué)科點專項科研基金資助項目(20110201110012)。

時間: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