用于壓縮感知信號重建的SL0改進算法

齊煥芳,徐源浩

(西安電子科技大學 數(shù)學與統(tǒng)計學院,陜西 西安 710126)

用于壓縮感知信號重建的SL0改進算法

齊煥芳,徐源浩

(西安電子科技大學 數(shù)學與統(tǒng)計學院,陜西 西安 710126)

SL0算法是一種基于近似l0范數(shù)的壓縮感知信號重建算法,其思想是用一個光滑函數(shù)來近似l0范數(shù),然后求解一個優(yōu)化問題。目前采用的光滑函數(shù)都是高斯函數(shù)族,文中突破了以往采用高斯函數(shù)族近似l0范數(shù),提出了采用復合三角函數(shù)作為近似估計l0范數(shù)的函數(shù),然后結合修正牛頓法和阻尼牛頓法提出一種更精確的重建算法DNSL0。實驗結果表明,在相同測試環(huán)境下,DNSL0算法在峰值信噪比和匹配度方面比SL0算法和NSL0算法都有了大幅提高。

壓縮感知;重建算法;復合三角函數(shù);近似l0范數(shù);牛頓法

壓縮感知理論(Compressive Sensing)[1-4]是一種全新的信號采樣理論,它指出,只要信號是可壓縮的或具有稀疏度,就可以用一個與變換基不相關的觀測矩陣將變換所得高維信號投影到一個低維空間上,再通過求解一個優(yōu)化問題就可以從這些少量的投影中以高概率重構出信號。該理論表明,通過采集少量的信號值就可以實現(xiàn)可壓縮或稀疏信號的精確重構,克服了采樣數(shù)據(jù)量大,采樣時間以及數(shù)據(jù)存儲空間等物理資源嚴重浪費的問題,具有良好的應用前景。目前用于壓縮感知重建的算法從廣義上主要分為兩大方向:一是針對l0范數(shù)最小的;二是針對l1范數(shù)最小的。本文主要討論l0范數(shù)最小化問題。

本文討論的是SL0算法,它用光滑連續(xù)函數(shù)來近似l0范數(shù),目前采用的是高斯函數(shù)族,致力于尋找優(yōu)于高斯函數(shù)族的平滑連續(xù)函數(shù)來更精確地近似l0范數(shù)。因此,本文提出了基于SL0算法的一種新算法,用復合三角函數(shù)來近似估計l0范數(shù),結合修正牛頓法和阻尼牛頓法獲得的一種更精確、收斂速度更快的信號重構算法,稱為DNSL0(DampNewtonSmoothl0Norm)算法。通過數(shù)值仿真,說明了該算法在峰值信噪比、匹配度和信噪比等方面的性能。

1 SL0算法

2 SL0算法的改進算法

2.1 改進算法近似估計l0范數(shù)

SL0算法的關鍵問題是選取合適的平滑連續(xù)函數(shù)來近似l0范數(shù),通過求解連續(xù)函數(shù)的最小解使得l0范數(shù)最小。目前采用高斯函數(shù)族來近似l0范數(shù),如采用高斯函數(shù)來近似l0范數(shù)[18],趙瑞珍等人提出用雙曲正切函數(shù)來近似l0范數(shù)[19]。本文突破了以往采用高斯函數(shù)族近似l0范數(shù),提出了逼近性能更好的非高斯函數(shù)族—復合三角函數(shù)作為近似估計l0范數(shù)的函數(shù),其表達式為

(1)

定義

(2)

l0范數(shù)指的是向量X中非零元素的個數(shù),故l0范數(shù)可以近似表示為

(3)

由圖1中3個函數(shù)的分布可見,復合三角函數(shù)對近似l0范數(shù)的估計要好于1-高斯函數(shù)和雙曲正切函數(shù)。在區(qū)間[-0.4,0.4]內,復合三角函數(shù)比高斯函數(shù)和雙曲正切函數(shù)“陡峭性”更大,因此復合三角函數(shù)對l0范數(shù)的逼近要好于高斯函數(shù)和雙曲正切函數(shù)。

圖1 σ=0.1兩種函數(shù)對比圖

(4)

2.2 DNSL0算法具體實現(xiàn)

SL0算法采用高斯函數(shù)近似l0范數(shù),將最小l0范數(shù)問題轉化為凸優(yōu)化問題,然后運用最速下降法求解該優(yōu)化問題。由數(shù)學知識可知在搜索最優(yōu)值過程中,搜索路徑會出現(xiàn)“鋸齒效應”,不能求得全局最優(yōu)解,進而l0范數(shù)的估計精度降低。

針對以上問題,為了更好地近似估計l0范數(shù)以及提高算法的收斂速度,提出了用復合三角函數(shù)來近似l0范數(shù),搜索方向為牛頓方向、步長因子由阻尼牛頓法求得的一種新的重建算法。

牛頓方向:d=-2Fσ(X)-1Fσ(X)。對式(2)取牛頓方向

(5)

(6)

從上述計算發(fā)現(xiàn),該牛頓方向d中的Hesse矩陣不是正定矩陣,不能保證牛頓方向d為下降方向。為此,本文將通過對上述Hesse矩陣進行修正,得到一個修正的牛頓方向。

或

或

d=-G-1

(7)

綜上,DNSL0算法的具體步驟如下:

選擇遞減序列σ,[σ1,σ2,L,σS];

fors=1,2,K,S:

①σ=σs;

forj=1,K,L(最速下降法迭代次數(shù))

a.搜索方向d=-G-1

b.阻尼牛頓法X←X+λd;

c.梯度投影X=X-ΦT(ΦΦT)-1(ΦX-Y);

3 實驗結果及分析

為說明改進后算法的優(yōu)良性,本文通過Matlab對該算法進行測試。

(1)對改進前后算法的性能做了比較。對512×512的Lena圖像分別用SL0算法、NSL0算法和DNSL0算法進行重建,圖2給出了重建后的直觀視覺效果對比,壓縮比為M/N=256/512=0.5。如圖2所示,DNSL0算法的重建效果更好。

圖2 SL0、NSL0和DNSL0重建效果對比

表1是不同的兩幅圖像,大小均為512×512,在壓縮比為M/N=0.25下,SL0算法、NSL0算法和DNSL0算法在峰值信噪比、相對誤差和匹配度之間的對比。DNSL0算法得到的數(shù)據(jù)取的是在該代碼運行100次得到的結果取平均值。SL0算法和NSL0算法的數(shù)據(jù)參考文獻[20]中的數(shù)據(jù)。

表1 SL0、NSL0和DNSL0重建質量比較

由表1可以看出,DNSL0算法與NSL0算法相比,峰值信噪比平均提高了2.2dB,相對誤差平均減少了0.22%,匹配度也有所提高。

(2)在相同的壓縮比M/N=0.5的情況下,對DNSL0算法和其他常用的重建算法進行比較。表2所示為Lena圖像在不同算法下重建質量對比,從此表中可以明顯看出DNSL0算法相比傳統(tǒng)壓縮感知重建算法在各方面性能均有較大提高。

表2 各算法重建質量對比

各種實驗結果表明,DNSL0算法用復合三角函數(shù)通過遞減序列σ的逐步逼近來近似l0范數(shù),能有效地實現(xiàn)l0范數(shù)的近似,從而改進了重建質量。另外,采用修正牛頓法求解比最速下降法收斂速度更快,并有效防止“鋸齒現(xiàn)象”。

4 結束語

目前,SL0算法中近似l0范數(shù)估計函數(shù)選取的均為高斯函數(shù)族,如1-高斯函數(shù)、雙曲正切函數(shù)、近似雙曲正切函數(shù)等。本文選取了重建性能更好的復合三角函數(shù)來近似l0范數(shù),結合修正牛頓法和阻尼牛頓法提出了一種DNSL0算法。實驗結果表明,DNSL0算法是一種綜合性能較好的重建算法。三角函數(shù)族中是否有更好的函數(shù)來逼近l0范數(shù)將是下一步需要繼續(xù)研究的問題。

[1]CandésE.Compressivesampling[C].Zürich,Switzerland:ProceedingsofInternationalCongressofMathematicians,EuropeanMathematicalSocietyPublishingHouse,2006,21:1433-1452.

[2]BaraniukR.Compressivesensing[J].IEEESignalProcessingMagazine,2007,24(4):118-121.

[3]ZhaoRuizhen,LiuXiaoyu,LiChingchung.Waveletdenoisingviasparserepresentation[J].ScienceinChinaSeriesF,2009,52(8):1371-1377.

[4]CandèsE,RombergJ,TaoT.Stablesignalrecoveryfromincompleteandinaccuratemeasurements[J].CommunicationsonPureandAppliedMathematics,2006,59(8):1207-1223.

[5]JeevanKPant,LuWusheng,AndreasAntoniou.Reconstructionofsparsesignalbyminimizingare-weightedapproximatel0-norminthenullspaceofthemeasurementmatrix[J].IEEETransactionsonSignalProcssing,2005,53(8):3010-3022.

[6] 賀亞鵬,李洪濤,王克讓,等.基于壓縮感知的高分辨DOA估計[J].宇航學報,2011,32(6):1344-1349.

[7]ChenS,DonohoDL,SaundersMA.Atomicdecompositionbybasispursuit[J].SLAMJournalScienceComput,2001,43(1):129-159.

[8]ChenS,DonohoD.Basispursuit[C].Monterey,CA:Proceedingof28thAsilonmarConferenceSignals,SystemComputer,1994.

[9]WangY,YinW.Sparsesignalreconstructionviaiterativesupportdetection[J].SLAMJournalonImagingSciences,2010,3(3):462-491.

[10]DonnhoDL.Formostlargeunderdeterminedsystemsoflinearequationstheminimall1-normSolutionisalsothesparsestsolution[J].CommunicationPureApplication,2006,59(6):797-829.

[11]TroppJ,GilbertA.Signalrecoveryfromrandommeasurementsviaorthogonalmatchingpursuit[J].IEEETransactionsonInformationTheory,2007,53(12):4655-4666.

[12]NeedellD,VershyninR.Signalrecoveryfromincompleteandinaccuratemeasurementsviaregularizedorthogonalmatchingpursuit[J].IEEEJournalSel.TopicsSignalProcess,2010,4(2):310-316.

[13]DaiW,MilenkovicO.Subspacepursuitforcompressivesensingsignalreconstruction[J].IEEETransactionsonSignalProcessing,2009,55(5):2230-2249.

[14]NeedellD,TroppJ.CoSaMP:Iterativesignalrecoveryfromincompleteandinaccuratesamples[J].ApplicationofOmputimoArmon,2009,26(2):301-321.

[15]RodriguezP,WohlbergB.Aniterativereweightednormalgorithmfortotalvariationregularization[J].IEEESignalProcessingLetters,2007,14(12):948-951.

[16]ChartrandR,YinW.Iterativereweightednormalgorithmforcompressivesensing[J].Acoustics,SpeechandSignalProcessing,2008(6):3869-3872.

[17]MohimaniGH,Babaie-ZadehM,JuttenC.Fastsparserepresentationusingsmoothednorm[J].IEEETransactiononSignalProcessing,2007,46(6):1-12.

[18]MohimaniGH,Babaie-ZadehM,JuttenC.Afastapproachforovercompletesparsedecompositionbasedonsmoothednorm[J].IEEETransactiononSignalProcessing,2009,57(1):289-301.

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

[20]楊良龍.基于SL0壓縮感知信號重建的改進算法[J].信號處理,2012,28(6):834-841.

Improved SL0Algorithm for Compressive Sensing Signal Reconstruction

QI Huanfang,XU Yuanhao

(School of Mathematics and Statistics,Xidian University,Xi’an 710126,China)

The smoothedl0norm algorithm (SL0) is a reconstruction algorithm in compressive sensing based on approximatel0norm.It is to use a smooth function to approximate thel0norm and then solve an optimization problem.Currently people use the Gauss family function as a smooth function.This paper makes a breakthrough in the use of the composite trigonometric function,instead of the traditionally used Gauss family function,which is used to approximate thel0norm.And a new efficient and more accurate algorithm named DNSL0(Damp Newton Smoothl0Norm) is proposed based on the smoothedl0norm and the revised Newton method and the damped Newton method.Experimental results show that the DNSL0algorithm is greatly improved in both the peak value signal-to-noise ratio and matching degree compared with the SL0algorithm and NSL0algorithm under the same experimental conditions.

compressive sensing;reconstruction algorithm;composite trigonometric function;approximatel0norm;Newton method

2014- 08- 21

齊煥芳(1988—),女,碩士研究生。研究方向:壓縮感知重建方法。E-mail:983036383@qq.com。徐源浩(1989—),男,碩士研究生。研究方向:圖像處理。

10.16180/j.cnki.issn1007-7820.2015.04.008

TN911.73;TP391.41

A

1007-7820(2015)04-027-04