齊煥芳,徐源浩

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

用于壓縮感知信號(hào)重建的SL0改進(jìn)算法

齊煥芳,徐源浩

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

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

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

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

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

1 SL0算法

2 SL0算法的改進(jìn)算法

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

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

(1)

定義

(2)

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

(3)

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

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

(4)

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

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

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

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

(5)

(6)

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

或

或

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 實(shí)驗(yàn)結(jié)果及分析

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

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

圖2 SL0、NSL0和DNSL0重建效果對(duì)比

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

表1 SL0、NSL0和DNSL0重建質(zhì)量比較

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

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

表2 各算法重建質(zhì)量對(duì)比

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

4 結(jié)束語

目前,SL0算法中近似l0范數(shù)估計(jì)函數(shù)選取的均為高斯函數(shù)族,如1-高斯函數(shù)、雙曲正切函數(shù)、近似雙曲正切函數(shù)等。本文選取了重建性能更好的復(fù)合三角函數(shù)來近似l0范數(shù),結(jié)合修正牛頓法和阻尼牛頓法提出了一種DNSL0算法。實(shí)驗(yàn)結(jié)果表明,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ì)[J].宇航學(xué)報(bào),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].計(jì)算機(jī)輔助設(shè)計(jì)與圖形學(xué)學(xué)報(bào),2012,24(4):478-484.

[20]楊良龍.基于SL0壓縮感知信號(hào)重建的改進(jìn)算法[J].信號(hào)處理,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