錢 陽，宋歡歡，李 雷

(南京郵電大學(xué) 視覺認(rèn)知計(jì)算與應(yīng)用研究中心，江蘇 南京 210023)

一種新型的快速信號重構(gòu)算法

錢 陽，宋歡歡，李 雷

(南京郵電大學(xué) 視覺認(rèn)知計(jì)算與應(yīng)用研究中心，江蘇 南京 210023)

信號重構(gòu)是壓縮感知理論的關(guān)鍵組成部分，研究快速有效的重構(gòu)算法具有現(xiàn)實(shí)意義。目前，迭代閾值算法中的不動點(diǎn)迭代(FPC)算法，在重構(gòu)速度和精度方面存在很大的提升空間。為此，文中首先提出了一種快速不動點(diǎn)迭代(FFPC)算法。接著針對該算法，通過引入子空間優(yōu)化，充分利用壓縮感知貪婪算法和凸優(yōu)化算法的各自優(yōu)點(diǎn)，提出了快速不動點(diǎn)_活動集(FFPC_AS)算法，進(jìn)而得到更加準(zhǔn)確的解。對于FFPC_AS算法，給出了收縮階段和子空間優(yōu)化階段交替執(zhí)行方案，避免了除偏(Debiasing)操作。大量仿真對比實(shí)驗(yàn)表明，所提算法既能快速重構(gòu)圖像信號，又可以提高準(zhǔn)確率。

壓縮感知；快速不動點(diǎn)；活動子集；子空間優(yōu)化；除偏

0 引 言

在信息數(shù)字化時代，壓縮感知理論(Compressed Sensing,CS)[1-2]憑借其采樣與壓縮同時進(jìn)行，并能精確重構(gòu)出原始信號的良好性能，吸引了數(shù)學(xué)家和計(jì)算機(jī)學(xué)家的廣泛關(guān)注[3]。該理論主要包括信號的稀疏表示、觀測矩陣的選取和信號重構(gòu)這三個階段。其中最關(guān)鍵的一步是重構(gòu)信號，其性能的好壞決定了重構(gòu)質(zhì)量的優(yōu)劣與恢復(fù)時間的長短。

CS理論的目標(biāo)是從較少的相對不完整的測量值b=Ax中恢復(fù)出K稀疏信號x∈Rn。目前重構(gòu)算法主要集中于貪婪算法和凸優(yōu)化算法。當(dāng)滿足等距約束條件(RestrictedIsometryProperty,RIP)[4]時，貪婪算法效果較好。這類算法主要包括正交匹配算法(OMP)[5]、子空間追蹤(SP)[6]等。而典型的凸優(yōu)化算法包括基于閾值的算法[7-8]、NESTA算法[9]、不動點(diǎn)連續(xù)方法(FixedPointContinuation，F(xiàn)PC)[10]等。

FPC算法是一種基于算子分裂和連續(xù)的，能夠解決大規(guī)模數(shù)據(jù)密集問題的方法，被廣泛應(yīng)用于CS的核磁共振成像(MRI)中[11]。為了提高FPC算法的重構(gòu)性能，文中通過引入軟閾值和正則化參數(shù)的雙收縮，提出了快速不動點(diǎn)迭代方法(FFPC)。該方法表現(xiàn)出更優(yōu)的重構(gòu)性能。然而，F(xiàn)FPC方法重構(gòu)的信號存在一些誤差，需要采用除偏操作去除誤差較大的元素。受文獻(xiàn)[12]中所提基于收縮的快速稀疏重構(gòu)(FPC_AS)算法的啟發(fā)，針對輸入信號絕對稀疏時，F(xiàn)FPC算法重構(gòu)誤差較大的情況，文中通過引入子空間優(yōu)化概念，建立了快速不動點(diǎn)-活動子集算法(FFPC_AS)。大量對比實(shí)驗(yàn)驗(yàn)證了所提算法無需除偏，而且具有最好的重構(gòu)效果。

1 預(yù)備知識

1.1 壓縮感知理論基礎(chǔ)

在壓縮感知理論中，如果n維稀疏信號x∈Rn在某正交基或者緊框架Ψ(其中Ψ=(φ1,φ2,…,φn)T)上可壓縮，那么x在該基下可以線性表示為：

Θ=ΨTx

(1)

式中，Θ是x在Ψ變換域上的變換向量。

CS編碼中，通過設(shè)計(jì)一個平穩(wěn)的、與Ψ不相關(guān)的測量矩陣Φ，對稀疏信號Θ進(jìn)行非自適應(yīng)觀測，得到觀測向量b=ΦΘ=ΦΨTx(其中A=ΦΨT稱為信息算子[13])。Candes等指出，為保證準(zhǔn)確地從m個測量值中恢復(fù)出K個系數(shù)，A必須滿足等距性質(zhì)[14]。

實(shí)際的信號測量中，隨著被測信號的不同，變換基Ψ會有相應(yīng)的變化，因此希望找出可以與任意稀疏基不相關(guān)的觀測陣Φ。對于任意正交基Ψ，隨機(jī)產(chǎn)生一個測量矩陣Φ，若m≥CKlog(n/K)，其中C為某固定常數(shù)，則Ψ與Φ不相關(guān)的概率就很大，即A滿足RIP條件的概率很大。常用的觀測陣有高斯隨機(jī)矩陣、哈達(dá)瑪矩陣、伯努利矩陣等。

min‖x‖0subject toAx=b

(2)

然而，l0范數(shù)模型是NP難題[15]，在數(shù)值上是不可解的。因此，Candes等指出，在一定條件下，問題的解x∈Rn可以通過基追蹤問題(BP)獲得。

(3)

通過引入正則化參數(shù)μ，式(3)可以化為無約束最優(yōu)化問題。

(4)

1.2 基于不動點(diǎn)方法的信號重構(gòu)算法

2007年，Elaine T等首次提出解決l1范數(shù)問題的不動點(diǎn)算法(FPC)，并將其應(yīng)用于CS的信號重構(gòu)中。FPC主要解決式(5)所示的l1范數(shù)問題：

(5)

其不動點(diǎn)迭代式為：

xk+1=Sv°h(xk),ν=τ/μ

(6)

其中，Sv(·)是軟閾值收縮算子；ν是閾值。

2010年，WenZaiwen等提出了一種基于收縮的快速稀疏重構(gòu)算法—FPC_AS[16]，用于求式(5)的最優(yōu)解。該算法是在FPC算法的基礎(chǔ)上，引入子空間優(yōu)化，集成了閾值迭代算法求解速度快和凸優(yōu)化算法易獲得全局解的優(yōu)勢，從而得到式(5)更加精確的解。盡管如此，F(xiàn)PC算法在重構(gòu)速度和精度方面仍存在很大的提升空間。

2 快速不動點(diǎn)迭代算法(FFPC)

傳統(tǒng)FPC方法的收斂速度由ν=τ/μ和二次函數(shù)f(x)的部分Hessian矩陣HEE的譜性質(zhì)決定，在特定的參數(shù)τ下，不動點(diǎn)方法是線性收斂的。為提高FPC算法的收斂速度和信號重構(gòu)質(zhì)量，引入軟閾值步長參數(shù)和正則化參數(shù)的收縮，提出了快速不動點(diǎn)迭代算法。

FFPC算法求解的是問題(5)中M=2的情況，其中μ是引入的正則化參數(shù)，用來平衡l1,l2范數(shù)所占的比重，利用優(yōu)化算法可求得最優(yōu)解x*。

(7)

(8)

使用式(8)更新x類似于使用最速下降方法，在滿足式(9)的基礎(chǔ)上，使用式(10)來尋找最優(yōu)步長tk。

(10)

因此，更新不動點(diǎn)迭代式(6)為：

式中，⊙是按元素逐個作乘積的算子；ν=τ/μ為閾值，對確定不動點(diǎn)迭代式(11)的收斂速率起重要作用，ν值越大，收斂速率越快。因此只要使τ的值盡量大，μ的值盡量小，就能加快不動點(diǎn)迭代(11)的收斂速度。

利用BB(Barzilai和Borwein)步長更新參數(shù)τ。

(12)

對于參數(shù)μ，其作用是來平衡二次項(xiàng)f(x)和l1范數(shù)項(xiàng)‖x‖1的比重，通常設(shè)置δ·max(ATb)(δ是大于0的常數(shù))作為參數(shù)μ的初始值。此外，在迭代過程中，為加快x的稀疏速度，可以對μ作適當(dāng)?shù)氖湛s操作，即令μ=β·μ(其中β是收縮因子，0<β<1)，并且保證μ仍然能夠平衡二次函數(shù)f(x)和l1范數(shù)‖x‖1在迭代過程中的比重。

在FFPC算法中，兩次相鄰迭代的相對誤差決定了其迭代終止條件：

這里，迭代終止條件為xtol和gtol。當(dāng)滿足上述條件時，F(xiàn)FPC算法停止迭代。

利用FFPC算法恢復(fù)信號x，具體執(zhí)行步驟如下：

Step1：令信號在小波域的稀疏表示為x0=0，設(shè)置迭代次數(shù)初始值k=1,t1=1,z1=0。

Step2：利用式(6)計(jì)算xk。

Step3：計(jì)算tk+1，根據(jù)式(9)對t進(jìn)行更新，利用式(8)計(jì)算zk。

Step4：按式(13)計(jì)算函數(shù)Gk(xk,xk-1)，若滿足終止條件，則令x*=xk，否則轉(zhuǎn)Step5。

Step5：擴(kuò)張參數(shù)μ=β·μ，令k=k+1，更新τ，將zk代入Step2中，重復(fù)上述過程。

迭代結(jié)束后，得到的迭代結(jié)果x*即是對原始信號的估計(jì)值。

3 快速不動點(diǎn)_活動子集(FFPC_AS)

盡管FFPC算法比FPC算法表現(xiàn)出更優(yōu)的重構(gòu)性能，但和FPC算法一樣，重構(gòu)出的信號存在一些誤差，需要采用除偏操作去除誤差比較大的元素。針對在輸入信號絕對稀疏時，F(xiàn)FPC算法重構(gòu)結(jié)果誤差較大的情況，受文獻(xiàn)[16]的啟發(fā)，文中提出了快速不動點(diǎn)-活動集算法(FFPC_AS)。該方法在利用FFPC重構(gòu)信號后，通過提取重構(gòu)結(jié)果非零項(xiàng)的索引，建立活動子集，并進(jìn)行子空間優(yōu)化操作，在確保信號重構(gòu)準(zhǔn)確度的基礎(chǔ)上，提高算法收斂速度。

FFPC_AS算法分為收縮階段和子空間優(yōu)化階段。收縮階段利用FFPC算法逼近原始信號x，得到粗糙解xk，并且計(jì)算活動集A(xk)；當(dāng)活動集A(xk)逼近于真實(shí)的活動集A(x*)時，利用二階方法求解子空間優(yōu)化問題即可。不斷地重復(fù)這兩個階段，直至滿足精確解條件。

3.1 收縮階段

令dk=d(τk)(xk)為線性搜索的搜索方向，則dk可以按照下面方法進(jìn)行計(jì)算。

dk(x)=xk-xk-1,k>1

(14)

其中，xk是FFPC算法第k步迭代得到的結(jié)果，令x+=xk+αkdk，則不動點(diǎn)迭代式為：

xk=S(x+-τg,τ/μ)，μ>0,τ>0

(15)

(16)

(S(x,ν)-x)T(y-S(x,ν))+ν(ξ-

‖S(x,ν)‖1)≥0

(17)

用x-τg和‖x‖1，分別替換y和ξ，并且令ν=τ/μ，則式(17)可寫為：

(S(x-τg,τ/μ)-(x-τg))T(x-S(x-τg,τ/μ))+τ/μ(‖x‖1-‖S(x-τg,τ/μ)‖1)≥0

代入式(14)、(15)得：

(18)

minμf(x)+ξs.t. (x,ξ)∈Ω

(19)

因?yàn)棣?=‖x*‖1，故其對于不動點(diǎn)x*的一階最優(yōu)性條件為：

μf(x*)(x-x*)+(ξ-‖x*‖1)≥0 ?(x,ξ)∈Ω

(20)

因此，用dk求解問題(5)類似于求解式(19)的梯度投影方法，當(dāng)且僅當(dāng)x*是式(15)的駐點(diǎn)時，對?x*∈Rn,0<τ<∞,有：

d(τ)=0

(21)

ψ(xk+αkdk)≤Ck+ρhσΔk

(22)

(23)

由于式(18)和l1范數(shù)的凸性，故存在(回溯)步長滿足式(22)的要求，其中Ck=Φ(xk)。該線性回溯方法是單調(diào)的，因?yàn)棣?xk+1)<Φ(xk)。

FFPC_AS算法中使用了一種快速的非單調(diào)的線性搜索方法—FNMLS。

Ck+1=(ηQkCk+ψμ(xk+1))/Qk+1

(24)

其中，Ck是函數(shù)ψμ(xk)和Ck-1的凸組合；Qk+1=ηQk+1,Q0=1,0<η<1。

算法過程如下：

初始化：x0，設(shè)置參數(shù)0<η<1,t0=1和0<τm<τM<∞。

令C0=Φ(x0),Q0=1,k=0。

WHILE“不滿足收斂條件”DO

計(jì)算搜索方向：令τm<τk<τM，令dk=S(x+-τkgk,τk/μ)-xk-1。

更新：令Qk+1=ηQk+1，Ck+1=(ηQkCk+

Φ(xk+1))/Qk+1，k=k+1。

ENDWHILE

在迭代過程中，Ck的值隨著迭代次數(shù)的增加而變大。

3.2 子空間優(yōu)化階段

對于固定的常數(shù)δ，滿足下面任意一個條件，即可由收縮階段轉(zhuǎn)換到子空間優(yōu)化階段。

(25)

(26)

(27)

至此，子空間優(yōu)化為可簡化為：

minφμ(x) s.t.x∈Ω(xk)

(29)

該子空間優(yōu)化問題可以由共軛梯度方法來求解。

FFPC_AS算法：

(2)重復(fù)迭代直至收斂。

●閾值收縮階段。

令tk=1。若ψμk(xk+)>Ck+σαkΔk，那么用FNMLS算法搜索αk。更新x+=xk+αkdk，Qk+1=ηQk+1，Ck+1=(ηQkCk+Φ(xk+1))/Qk+1。

計(jì)算非活動集I(xk+1,ξk)和活動集A(xk+1,ξk)，更新閾值ξk+1=min(max(η2

若χ(xk+1,μ,ξk)≤max(ε,εxmax(‖xk+1‖,1))，則收縮階段結(jié)束。

●檢查是否需要做子空間優(yōu)化。

令do_sub=0，若I(xk,ξk-1)≠I(xk+1,ξk)，則

設(shè)置do_sub=1,δ=γδ。否則若

●做子空間優(yōu)化。

若do_sub=1，那么

若χ(xk+1,μ,ξk)≤max(ε,εxmax(‖xk+1‖,1))，則返回結(jié)果集。

若χ(xk+1,μ,ξk)≤max(ε,εxmax(‖xk+1‖,1))或者do_sub=1，并且μk>μ，那么

計(jì)算μk+1=max(βmin(‖gA(xk+1,ξk)‖,μk),μ)。令δ=δ0,Ck+1=Φ(xk+1),Qk+1=1。

否則令μk+1=μk。

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

以256*256的自然圖像Camera進(jìn)行實(shí)驗(yàn)仿真。實(shí)驗(yàn)平臺為Windows8.1，Intel(R)Core(TM)2DuoCPU，2.53GHz，實(shí)驗(yàn)設(shè)計(jì)基于Matlab7.11.0編程實(shí)現(xiàn)。采用DCT稀疏變換基，觀測矩陣選用高斯隨機(jī)矩陣。初始正則化參數(shù)μ=10-10。迭代過程中，設(shè)置收縮因子β=0.1，非線性搜索參數(shù)γ=0.85，σ=0.5，δ=10-6，執(zhí)行子空間優(yōu)化條件參數(shù)εf=10-20。

圖1 算法性能隨采樣率變化圖

圖1記錄了隨著采樣率變化不同算法對Camera圖像重構(gòu)性能的變化曲線。

實(shí)驗(yàn)中，由于FPC_AS、FFPC_AS算法均采用一階收縮方法和二階共軛梯度(CG)方法交替求解的方式來逼近最優(yōu)解，而其他算法則是一階算法，故FPC_AS與FFPC_AS算法的收斂速度要快些。圖(a)形象地展現(xiàn)了FPC_AS和FFPC_AS的重構(gòu)速度。當(dāng)采樣率超過0.6時，二階子空間優(yōu)化次數(shù)較多，算法收斂至精確解的速度更快。圖(b)展示了在不同采樣率下，F(xiàn)FPC_AS算法重構(gòu)出的圖像的峰值信噪比都是最高的。

表1給出了不同采樣率下對FPC和FFPC算法所得結(jié)果進(jìn)行除偏操作的重構(gòu)情況。

表1 Camera圖像處理結(jié)果

由表1可見，F(xiàn)FPC_AS算法重構(gòu)速度最快，在采樣率為0.5和0.75時，F(xiàn)FPC_AS的峰值信噪比要比FFPC經(jīng)過除偏(Debiase)的值要高出0.713 7dB和0.734 7dB。

為驗(yàn)證文中算法重構(gòu)性能最優(yōu)，分別采用FPC_AS和FFPC_AS算法對Camera圖像進(jìn)行重構(gòu)。圖2和圖3分別給出了不同采樣率下兩種算法的重構(gòu)效果直觀圖。

圖2 自然圖像Camera的FPC_AS處理結(jié)果

圖3 自然圖像Camera的FFPC_AS處理結(jié)果

從圖中不難發(fā)現(xiàn)，F(xiàn)FPC_AS的重構(gòu)效果更好些。在采樣率為0.25和0.5時，結(jié)果圖中均存在些噪點(diǎn)，F(xiàn)FPC_AS的重構(gòu)圖細(xì)節(jié)更加明顯。而當(dāng)采樣率達(dá)到0.75時，兩種方法的重構(gòu)圖像細(xì)節(jié)突出，對比度很高。

5 結(jié)束語

文中首先對傳統(tǒng)的不動點(diǎn)迭代方法(FPC)進(jìn)行改進(jìn)，通過引入軟閾值步長參數(shù)和正則化參數(shù)的收縮，形成快速不動點(diǎn)迭代(FFPC)算法；接著針對FFPC算法需要進(jìn)行除偏操作的缺陷，提出了快速不動點(diǎn)-活動子集(FFPC_AS)方法。該算法結(jié)合了一階FFPC方法和二階共軛梯度方法的優(yōu)勢，在FFPC算法求得結(jié)果的活動子集逼近精確解的活動子集時，利用二階共軛梯度方法再來逼近精確解，不僅能使FFPC_AS算法更快速地收斂至最優(yōu)解，而且大大提高了解的準(zhǔn)確度。仿真實(shí)驗(yàn)結(jié)果表明，文中所提算法在圖像重構(gòu)的質(zhì)量和速度方面有明顯優(yōu)勢。

[1]CandesE,RombergJ.Quantitativerobustuncertaintyprinciplesandoptimallysparsedecompositions[J].FoundationsofComputationalMathematics,2006,6(2):227-254.

[2]DonohoDL,TsaigY.Extensionsofcompressedsensing[J].SignalProcessing,2006,86(3):533-548.

[3]KashinBS,TemlyakovVN.Aremarkoncompressedsensing[J].MatematicheskieZametki,2007,82(6):829-837.

[4]CandesE,TaoT.Nearoptimalsignalrecoveryfromrandomprojections:universalencodingstrategies[J].IEEETransactionsonInformationTheory,2004,52(12):5406-5425.

[5]MallatS,ZhangZ.Matchingpursuitswithtime-frequencydictionaries[J].IEEETransactionsonSignalProcessing,1993,41(12):3397-3415.

[6]DaiW,OlgicaM.Subspacepursuitforcompressivesensing:closingthegapbetweenperformanceandcomplexity[R].Urbana,IL:UniversityofIllinoisatUrbana-Champaign,2008.

[7]CombettesPL,PesquetJC.Proximalthresholdingalgorithmforminimizationoverorthonormalbases[J].SIAMJournalonOptimzation,2007,18(4):1351-1376.

[8]BeckA,TeboulleM.Afastiterativeshrinkage-thresholdingalgorithmforlinearinverseproblems[J].SIAMJournalonImagingScience,2009,2(1):183-202.

[9]BeckerS,BobinJ,CandesE.NESTA:afastandaccuratefirst-ordermethodforsparserecovery[R].Pasadena:CaliforniaInstituteofTechnology,2009.

[10]HaleET,YinW,ZhangY.Fixed-pointcontinuationforl1-minimization:methodologyandconvergence[J].SIAMJ.Optim.,2008,19(3):1107-1130.

[11] 劉曉曼，叢 佳，朱永貴.不動點(diǎn)方法及其在壓縮感知核磁共振成像中的應(yīng)用[J].中國傳媒大學(xué)學(xué)報(bào):自然科學(xué)版，2014,21(1):28-34.

[12]HaleET,YinWotao,ZhangYin.Afastalgorithmforsparsereconstructionbasedonshrinkage[J].SIAMJournalonScientificComputing,2010,32(4):1832-1857.

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

[14]CandesE,RombergJ,TaoTerence.Robustuncertaintyprinciples:exactsignalreconstructionfromhighlyincompletefrequencyinformation[J].IEEETransactionsonInformationTheory,2006,52(2):489-509.

[15] 焦李成，公茂果，王 爽，等.自然計(jì)算、機(jī)器學(xué)習(xí)與圖像理解前沿[M].西安:西安電子科技大學(xué)出版社,2008.

[16]WenZ,YinW,GoldfarbD,etal.Ontheconvergenceofanactivesetmethodforl1minimization[R].NewYork:ColumbiaUniversity,2008.

A Novel Fast Signal Reconstruction Algorithm

QIAN Yang,SONG Huan-huan,LI Lei

(Center for Visual Cognitive Computation and Its Application,Nanjing University of Posts and Telecommunications,Nanjing 210023,China)

Signal recovery is the key component of compressed sensing theory,which has practical significance to research the fast effective reconstruction algorithms.At present,the convergence rate and accuracy of Fixed Point Continuation (FPC) algorithm still can be improved.So,a Fast Fixed-Point Continuation (FFPC) algorithm is put forward firstly,and then it makes full use of the respective advantages of greedy algorithm and convex optimization by introducing subspace optimization to come up with the fast Fixed-Point Continuation_Active Set (FFPC_AS) algorithm,which can improve the accuracy and the convergence rate of FFPC algorithm.For the FFPC_AS algorithm,the shrinkage phase and subspace optimization phase are performed repeatedly which can avoid the debiasing operation,and the embodiment of the two stages is given in this paper.A large number of comparative simulation results show that the proposed algorithm exhibits state-of-the-art performance in terms of both its speed and its ability to recover sparse signal.

compressed sensing;fast fixed-point continuation;active set;subspace optimization;debiasing

2015-09-21

2015-12-23

時間：2016-05-25

國家自然科學(xué)基金資助項(xiàng)目(61070234，61071167，61373137，61501251)；南京郵電大學(xué)引進(jìn)人才科研啟動基金資助項(xiàng)目(NY214191)；江蘇省2015年度普通高校研究生科研創(chuàng)新計(jì)劃項(xiàng)目(KYZZ15_0235)

錢 陽(1991-)，女，碩士生，研究方向?yàn)榉蔷€性分析及應(yīng)用；李 雷，博士，教授，研究方向?yàn)橹悄苄盘柼幚砗头蔷€性科學(xué)及其在通信中的應(yīng)用研究。

http://www.cnki.net/kcms/detail/61.1450.TP.20160525.1709.058.html

TP301.6

A

1673-629X(2016)06-0056-06

10.3969/j.issn.1673-629X.2016.06.012