壓縮感知中基于快速不動點迭代算法的研究

劉 艷,宋歡歡,李 雷

(南京郵電大學 非結構化數據計算理論與應用研究中心,江蘇 南京 210046)

壓縮感知中基于快速不動點迭代算法的研究

劉 艷,宋歡歡,李 雷

(南京郵電大學 非結構化數據計算理論與應用研究中心,江蘇 南京 210046)

針對傳統迭代算法在解決大規模問題時速度較慢的問題，在介紹了壓縮感知中重構的基本模型以及傳統不動點迭代方法(FPC)的基礎上，提出了一種新的重構算法-快速不動點迭代方法(FFPC)。傳統的不動點迭代方法其實是基于算子分裂的方法。為了提高去重構性能，通過引入軟閾值和正則化參數的雙收縮，逐步迭代恢復原始圖像信號，以加快算法的收斂速度，減小重構誤差，從而改善圖像的重構質量。仿真結果表明，在相同的實驗環境下，與傳統的不動點迭代算法以及其他算法相比，快速不動點迭代算法重構圖像的峰值信噪比較高，相對誤差較小，在低采樣率下運行時間較少，性能最優。

壓縮感知；圖像重構；傳統不動點迭代算法；快速不動點迭代算法；收斂速度；重構質量

1 概 述

壓縮感知[1]理論指出：對可壓縮的信號可通過遠低于Nyquist標準的方式對數據進行測量，仍能夠精確地恢復出原始信號。壓縮感知理論的基本原則和目標就是從較少的相對不完整的測量值b=Ax中恢復出K稀疏的信號x∈Rn。理論上，恢復信號x最簡單的方法，是求解下面的l0范數最小化問題

(1)

其中，‖x‖0表示x中非零元素的個數。

但是l0范數模型(1)是NP難題[2]，在實踐上不可行。因此，Candes等[3-5]、Donoho等[6]指出，在一定條件下，問題的解x∈Rn通過解式(2)獲得：

(2)

詳細信息見文獻[3,7-16]。

優化算法通過解問題(2)或者與其相近的l1范數最小二乘問題來找到問題(1)的解。

(3)

其中，μ>0。

不動點連續(FPC)方法主要解決l1范數問題。

(4)

其能夠解決大規模問題。

基于不動點迭代方法，文中提出了一種收斂速度更快、算法性能更優的新算法-快速不動點迭代方法。實驗結果表明，該算法表現出了最優的性能。

2 FPC方法理論基礎

0∈T(x)?0∈(x+τT1)-(I-τT2)? (I-τT2)x∈(I+τT1)x?x=(I+τT1)-1(I-τT2)x

(5)

由式(5)，通過使用向前向后分裂算法即可找到算子T的零點。

xk+1=(I+τT1)-1(I-T2)xk

(6)

至此，得到了不動點迭代式(6)。對于凸優化問題(4)，令T2=f(x)。

g(x)=

(7)

|E|表示集合E的勢；λi(M),i=1,2,…,n，λmax(M)和λmin(M)分別表示矩陣的最大特征值和最小特征值。

對于t∈R，用符號函數表示。那么，|t|的次微分即可用集值函數來表示：

(8)

因此，對于向量x∈Rn，定義sgn(x)∈Rn和SGN(x)∈Rn，其中(sgn(x))i=sgn(xi)，(SGN(x))i=SGN(xi)，顯然有：

sgn(x)=sgn(x')?SGN(x)=SGN(x'),?x,x'

(9)

接著，對于凸規劃(4)的最優性和最優解集，假設X*是Φ(x)的最優解集。由凸分析[17]可知最優性條件為：

x*∈X*?0∈SGN(x*)+g(x*)

(10)

或者，等價表示為：

(11)

由式(11)可知，若‖g(0)‖∞≤1,則0是凸優化(4)的一個最優解，即

(12)

因此，可以很方便地檢測凸優化(4)是否有零解。

命題1：X*是Φ(x)的最優解集，對于?τ>0,x*∈X*，當且僅當

(13)

方程(13)是由兩個Rn→Rn映射組成，定義如下：

h(·)=I(·)-τg(·)

(14)

(15)

(16)

令向前向后分裂推導出的式(6)中的T1(x)=?‖x‖1,T2(x)=g(x)，即可直接得出式(6)與式(16)是等價的。

3 快速不動點迭代(FFPC)方法

3.1 FFPC算法思想

FFPC算法求解的是問題(4)的等價表示：

(17)

其中，μ是引入的正則化參數，用來平衡l1,l2范數所占的比重，利用優化算法可求得最優解x*。

(18)

(19)

使用式(19)更新x類似于使用最快下降方法。

Φ(xk+1)=Φ(xk-tktkΦ(xk))

(20)

在滿足式(20)的基礎上，受文獻[18]的啟發，使用式(21)來尋找最優步長tk。

(21)

因此式(16)可更新為：

xk+1=Sv°h(zk)=sgn(zk-τg(zk))⊙max{|zk- τg(zk)|-τμ,0}

(22)

由于閾值v=τμ影響了不動點迭代式(21)的收斂速度，v越大，收斂速度越快。則只要使得τ，μ的取值盡量大，就可以加快不動點迭代式(22)的收斂速度。使用BB(Barzilai和Borwein)步長更新參數τ：

(23)

對于正則化參數μ，其作用是平衡二次函數f(x)和l1范數‖x‖1的比重。為使式(17)側重于保證項f(x)最小，通常選取μ=δ·max(ATb)(δ是大于0的常數)作為初始值。在迭代過程中，為了使x快速稀疏，對μ作適當收縮，令μ=αμ(其中α是收縮因子，0<α<1)，平衡二次函數f(x)和l1范數‖x‖1在迭代過程中的比重。

快速不動點迭代方法的迭代停止條件是由x的兩次相鄰迭代的相對誤差決定的。

(24)

終止條件為xtol和gtol，當滿足上述終止條件時，停止迭代。

3.2 FFPC方法的收斂性證明

(25)

‖h(x)-h(x')‖≤‖x-x'‖

(26)

此外，當g(x)=g(x')時，式(26)依然成立。

由引理1可知，算子h(·)是非擴張的，根據FPC算法的q1階線性收斂性質，可以判定文中FFPC的迭代式(22)是全局收斂的。

引理2：對于k>1，FFPC算法產生的序列{xk,zk}滿足：

‖xk+1-xk‖≤‖xk-xk-1‖,‖zk+1-zk‖≤ ‖zk-zk-1‖,x*=z*

(27)

‖S(zk+1)-S(zk)‖≤‖zk-zk-1‖

(28)

又由式(22)可知zk+1=S(zk+1)，故

‖zk+1-zk‖=‖S(zk)-S(zk-1)‖≤‖zk-zk-1‖

(29)

證畢。

3.3 算法描述

FFPC算法步驟如下：

Step1：令信號在小波域的變換稀疏為x0=0，初始化迭代次數k=1,t1=1,z1=0。

Step2：利用式(16)計算xk。

Step3：計算tk+1，根據式(19)對t進行更新，利用式(17)計算zk。

Step4：按照式(22)計算迭代終止函數值Gk(xk,xk-1)，如果滿足迭代終止條件，則令x*=xk，否則執行Step5。

Step5：擴張正則化參數μ=αμ，更新迭代次數k=k+1，更新τ，將zk帶入Step2，重復上述過程。

迭代結束后，得到的迭代結果x*即是對原始信號的估計值。

3.4 除 偏

FFPC算法重構的信號存在一些誤差，采用除偏(Debiase)方法來去除誤差比較大的元素，使得非零的系數個數不超過m。FFPC算法和FPC算法類似，當輸入信號絕對稀疏時，使用除偏過程能夠使得算法FFPC重構信號的精度更高。

Debiase算法：

輸入參數：FFPC算法中的測量矩陣A，測量信號b和原始信號x。

若1≤|S|≤m，那么

xz=0

否則，停止計算。

4 仿真實驗和結果分析

為了說明提出算法的優越性，使用Matlab對提出的快速不動點迭代方法進行實驗。為了比較客觀地說明FFPC算法的有效性，將FFPC的實驗數據與IST算法、FIST算法、貪婪算法CoSaMP、子空間追蹤SP算法以及不動點連續方法的結果進行比較，分別從信號重構時間、相對誤差和峰值信噪比三個方面進行比較。

圖1(a)為各個算法重構時間隨采樣率的變化曲線。從中可見，文中提出的FFPC算法，重構Camera圖像的速度最快，充分體現了FFPC算法的速度及穩定性。此外，圖1(b)和圖1(c)則展示了這5種算法重構信號的質量，圖1(b)中不動點系列算法的相對誤差都較小，FFPC算法的準確性和FPC算法接近，而圖1(c)中FFPC算法重構出來的信號的信噪比比較高。

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

Camera圖像處理結果如表1所示。

如表1所示，在重構Camera圖像所用的時間上，FFPC算法的重構速度最快。例如，在采樣率為0.5時，FFPC算法比FIST和FPC算法分別快了4s和0.781 3s；在重構誤差方面，FFPC算法的效果也很好，在采樣率為0.25和0.75時，重構誤差均最小，其他情況下，誤差值均與FPC算法接近；在圖像重建質量方面，FFPC重構信號的峰值信號比也比IST、FIST和CoSaMP高出很多，信號重建質量與FPC算法相近。

表1 Camera圖像處理結果

圖2給出了使用FFPC算法在采樣率為0.25,0.5和0.75時對自然圖像的重構效果。

圖2 FFPC算法對自然圖像的重構效果

FFPC算法在采樣率為0.25時，重構出的圖像中噪點較多。當采樣率達到0.5時，重構出來的圖像信號都比較清晰，噪點較少，視覺效果相對很好。

由于FPC和FFPC算法在求解大規模問題時，往往得到的稀疏解中非零系數的個數偏差較大，所以文中采用除偏的方式來處理FPC和FFPC算法得到的粗糙解，結果如表2所示。

與原來的重構結果相比，除偏后圖像的峰值信噪比均有所提高。當采樣率為0.25時，經過除偏操作后，FFPC算法重構自然圖像的峰值信噪比和原來相比提高了1.843 6dB。

表2 圖像除偏結果

圖3給出了經過除偏操作后，自然圖像Camera的重構效果。

圖3 自然圖像的Debiase結果圖

可以看出，除偏后，圖像的清晰度和對比度明顯提高，噪點也明顯減少。

5 結束語

基于傳統的不動點迭代方法，文中提出了一種新的快速不動點迭代方法。該算法通過引入軟閾值和正則化參數的雙收縮，提高了算法的收斂速度和信號重構質量。通過在不同壓縮比下比較各算法的重構性能，同時還比較了在相同壓縮比下各算法的圖像重構效果。仿真結果表明，所提的快速不動點算法較傳統的不動點迭代方法性能更優。

[1]KashinBS,TemlyakovVN.Aremarkoncompressedsensing[J].MathematicalNotes,2007,82(5-6):748-755.

[2] 焦李成.自然計算、機器學習與圖像理解前沿[M].西安:西安電子科技大學出版社,2008.

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

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

[5]CandesE.Ridgelets:theoryandapplications[D].Stanford:StanfordUniversity,1998.

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

[7]TroppJA.Justrelax:convexprogrammingmethodsforidentifyingsparsesignalsinnoise[J].IEEETransactionsonInformationTheory,2006,52(3):1030-1051.

[8]WakinMB,LaskaJN,DuarteMF,etal.Anarchitectureforcompressiveimaging[C]//IEEEinternationalconferenceonimageprocessing.[s.l.]:IEEE,2006:1273-1276.

[9]WakinMB,LaskaJN,DuarteMF,etal.Compressiveimagingforvideorepresentationandcoding[C]//Proceedingsofthepicturecodingsymposium.Beijing,China:[s.n.],2006.

[10]LaskaJN,WakinMB,DuarteMF,etal.Anewcompressiveimagingcameraarchitectureusingoptical-domaincompression[C]//ProceedingsofSPIE.[s.l.]:[s.n.],2010:43-52.

[11]LustigM,DonohoD,PaulyJM.SparseMRI:theapplicationofcompressedsensingforrapidMRimaging[J].MagneticResonanceinMedicine,2007,58(6):1182-1195.

[12]TroppJA,WakinMB,DuarteMF,etal.Randomfiltersforcompressivesamplingandreconstruction[C]//IEEEinternationalconferenceonacoustics,speechandsignalprocessing.[s.l.]:IEEE,2006:14-19.

[13]KirolosS,LaskaJ,WakinM,etal.Analog-to-informationconversionviarandomdemodulation[C]//IEEEDallas/CASworkshopondesign,applications,integrationandsoftware.[s.l.]:IEEE,2006:71-74.

[14]LaskaJ,KirolosS,MassoudY,etal.Randomsamplingforanalog-to-informationconversionofwidebandsignals[C]//IEEEDallas/CASworkshopondesign,applications,integrationandsoftware.[s.l.]:IEEE,2006:119-122.

[15]LaskaJN,KirolosS,DuarteMF,etal.Theoryandimplementationofananalog-to-informationconverterusingrandomdemodulation[C]//IEEEinternationalsymposiumoncircuitsandsystems.[s.l.]:IEEE,2007:1959-1962.

[16]YangJ,ZhangY,YinW.AfastalternatingdirectionmethodforTVL1-L2signalreconstructionfrompartialFourierdata[J].IEEEJournalofSelectedTopicsinSignalProcessing,2010,4(2):288-297.

[17] 劉曉曼,叢 佳,朱永貴.不動點方法及其在壓縮感知核磁共振成像中的應用[J].中國傳媒大學學報:自然科學版,2014,21(1):28-34.

[18] 段世芳,馬社祥.圖像壓縮感知的雙收縮快速迭代算法[J].計算機工程,2012,38(19):226-228.

[19]HaleET,YinW,ZhangY.Afixed-pointcontinuationmethodfor'1-regularizedminimizationwithapplicationstocompressedsensing[R].[s.l.]:[s.n.],2007.

Research on Iteration Algorithm Based on a Fast Fixed Point in Compressed Sensing

LIU Yan,SONG Huan-huan,LI Lei

(Unstructured Data Calculation Theory and Application Research Center,Nanjing University of Posts and Telecommunications,Nanjing 210046,China)

Due to the low convergence rate of traditional iterative methods for solving large-scale problems,a fast fixed point continuation method is proposed after introducing the reconstructed models and the traditional fixed point continuation methods.This method,which brings in soft threshold shrinkage and regularization parameter shrinkage,restores image signals by gradual iteration in order to speed up the convergence rate and improve the quality of restored images.Simulation results show that compared with traditional fixed point continuation methods,it makes Peak Signal to Noise Ratio (PSNR) of the reconstructed image higher and the relative error smaller,and reduces running time when the sampling rate is low.

Compressed Sensing (CS);image reconstruction;fixed point continuation method;fast fixed point continuation method;convergence speed;quality of reconstructed

2016-04-21

2016-08-11

時間：2017-02-17

國家自然科學基金資助項目(61070234,61071167,61373137,61501251);江蘇省普通高校研究生科研創新計劃資助項目(KYZZ15_0236)；南京郵電大學引進人才科研啟動基金資助項目(214191)

劉 艷(1991-)，女，碩士，研究方向為非線性分析及其應用；李 雷，教授，研究方向為智能信號處理和非線性科學及其在通信中的應用。

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

TP301.6

A

1673-629X(2017)03-0052-05

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