郝雯潔,齊春

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

?

一種魯棒的稀疏信號重構算法

郝雯潔,齊春

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

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

稀疏信號;重構;魯棒;局部極小點

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

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

1 半閾值迭代算法

1.1 信號的稀疏表示

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

‖x‖0s.t.y=Ax

(1)

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

‖x‖1s.t.y=Ax

(2)

1.2 半閾值迭代算法

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

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

(3)

然而,式(3)是一個非凸優(yōu)化問題,很難用一種高效的算法來求解。結合有關非凸優(yōu)化問題的一些解決方法[11,13],文獻[12]通過使用閾值迭代算法求解該問題,推導得出其表達式

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為由半閾值函數h導出的半閾值算子,其表達式為

h(xn)=

(6)

式中

(7)

(8)

(9)

(10)

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

2 魯棒的稀疏信號重構算法

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

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

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

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

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

|B(xn)-xn|<ε

(11)

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

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

(14)

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

(15)

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

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

(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)重構信號的分步結果圖

表1 信號重構分步均方誤差值

注:黑體數據為符合要求的重構信號。

3 實驗結果及分析

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

3.1 信號重構實驗

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

(a)隨機高斯信號

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

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

3.2 圖像重構實驗

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

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

表2 6種算法在不同觀測點數情況下的重構圖像

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

算法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 結 論

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

[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]史金剛, 齊春.一種雙約束稀疏模型圖像修復算法 [J].西安交通大學學報, 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]楊揚, 劉哲, 呂方園.一種迭代加權l(xiāng)1范數的信號優(yōu)化恢復方法 [J].計算機工程與應用, 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].通信技術, 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—),女,碩士生;齊春(通信作者),男,教授,博士生導師。 基金項目:國家自然科學基金資助項目(60972124);國家“863計劃”資助項目(2009AA01Z321);教育部高等學校博士學科點專項科研基金資助項目(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