郭青青，李　雷

(南京郵電大學　視覺認知計算與應用中心，江蘇 南京 210046)

?

基于快速不動點連續(xù)的壓縮感知重構(gòu)算法

郭青青，李雷

(南京郵電大學視覺認知計算與應用中心，江蘇 南京 210046)

不動點連續(xù)(FPC)算法是一種凸優(yōu)化算法，針對該算法收斂速度較慢的現(xiàn)象，提出了一種快速的不動點連續(xù)(FFPC)算法，算法引入線性搜索步長，選擇合理的步長參數(shù)，利用前兩次迭代結(jié)果的特殊線性組合值作為下次迭代的初始值，提高每次迭代的精度，從而加快收斂速度。FFPC算法的收斂性在實驗中得到了驗證，同時，仿真實驗表明，F(xiàn)FPC算法的收斂速度有所提高，重構(gòu)質(zhì)量也比其他算法更好。

凸優(yōu)化算法；壓縮感知；快速不動點連續(xù)

在信號采樣和處理的過程中，壓縮感知(Compressed Sensing，CS)[1]被視為是一種很具發(fā)展前景的理論框架， 它打破了傳統(tǒng)香農(nóng)采樣定理的限制，成為一種新型的信號采樣和處理的理論，主要涉及3個問題：信號的稀疏表示、觀測矩陣的設(shè)計和信號重構(gòu)算法的設(shè)計[2]。CS理論指出，具有稀疏性或可壓縮性的信號可通過求解不適定的數(shù)學反問題，由少量的觀測值完成對原始信號的精確重構(gòu)。

壓縮感知的重構(gòu)算法主要分為3類[3]：1)貪婪算法，例如匹配追蹤(Matching Pursuit，MP)系列；2)凸優(yōu)化算法，例如內(nèi)點法(Interior-Point Algorithm，IPA)，梯度投影算法(Gradient Projection Algorithm，GA)，迭代收縮閾值算法(Iterative Shrinkage-Thresholding Algorithm，IST)[4]和不動點方法(Fixed-Point Continuation Method，F(xiàn)PC)[5]；3)組合算法。這些算法各有利弊，其中，對凸優(yōu)化算法的研究比較完善，其相關(guān)定理也有明確的界定。

目前，凸優(yōu)化算法中應用最為廣泛的是IST方法及其改進方法，例如：兩步迭代收縮閾值(Two-step IST，TwIST)[6]快速迭代閾值(Fast IST，F(xiàn)IST)方法[7]。另一方面，不動點連續(xù)性(Fixed Point Continuation，F(xiàn)PC)方法作為一種新型方法被提出[8]，該方法從算子分裂技術(shù)的角度可以看作是IST的改進模型，其利用不動點定理實現(xiàn)迭代，應用的范圍更為寬泛，并且，其不需要計算二階Hessian陣，大大降低了計算復雜度，同時，對FPC方法的研究具有一定的意義和價值。本文將提出一種快速的FPC算法，在不失原算法重構(gòu)性能的前提下，實現(xiàn)更快速和高效的重構(gòu)效果。

1　壓縮感知

1.1壓縮感知的重構(gòu)模型

根據(jù)CS理論，假設(shè)是x∈Rn是K階稀疏信號，A∈Rm×n是感知矩陣，則通過求解下面l0最小化問題，可從少量不完整的觀測值b=Ax中恢復出原始信號

(1)

(2)

(3)

式中：μ>0，是懲罰項系數(shù)。當μ趨于0時，式(3)的解便趨于式(2)的解[10]。

1.2不動點迭代連續(xù)(Fixed Point Continuation Algorithm，F(xiàn)PC)算法

0∈T(x)0∈(x+τT1(x))-(x-τT2(x))

(I+τT1)x∈(I-τT2)x

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

(4)

因此，F(xiàn)(x)的最小解迭代公式為

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

(5)

命題1：對于特定的τ>0，假設(shè)X*是式(3)的最優(yōu)解集，則x*∈X*當且僅當

(6)

于是，不動點迭代公式可表示為

(7)

sv(·)=sgn(·)max{|·|-v,0}

(8)

另一方面，考慮連續(xù)性，文獻[11]中設(shè)計了一組遞增的序列{μi}，依次取μi+1進行每輪迭代，本文的改進算法均是基于此不動點連續(xù)(Fixed-Point Continuation，F(xiàn)PC)算法進行的。

2　快速不動點連續(xù)算法(Fast FPC，F(xiàn)FPC)

2.1快速不動點連續(xù)算法

FPC算法的主迭代主要包含兩步：梯度下降步和閾值收縮步。算法迭代步驟簡單，但收斂速度較慢，有待進一步提升。本文根據(jù)快速迭代收縮閾值(FIST)算法的改進思想，引入合理的參數(shù)t，計算出下降步長的搜索系數(shù)，然后利用前兩次迭代結(jié)果的特殊線性組合計算下次迭代值，從而提高迭代收斂速度，減少迭代的次數(shù)。

FFPC算法通過選取合理的序列{tn}來計算迭代系數(shù)αn，從而更新每次迭代的公式

yn=xn+αn(xn-xn-1)

(9)

對于FIST算法，序列{tn}的選擇有兩類形式[12]：

在一定的條件下，兩種選擇方式的收斂性均已從理論和實驗兩方面得到了證明。鑒于IST和FPC算法一樣的理論框架和迭代原理，選擇這兩種序列均具有一定的可行性，但序列1更不失一般性，因此，本文將采用序列1的系數(shù)形式。另外，后文將設(shè)計相應的仿真實驗來驗證算法的收斂性和可行性。

通過FFPC算法求解問題(3)的迭代公式如下

(10)

yn=xn+αn(xn-xn-1)

(11)

在不動點算法中，參數(shù)τ的取值對迭代收斂速率有著重要的作用，其值越大收斂越快，故本文算法將通過Barzilai-Borwein(BB)步來計算參數(shù)τ的值，同時，為收斂平穩(wěn)，在BB方法下選用非單調(diào)線性搜索(Nonmonotone Line Search，NMLS)來更新下降步長[11]。于是，快速不動點連續(xù)算法步驟如下。

算法1：快速不動點連續(xù)(FFPC)算法

2)初始化：感知矩陣A，觀測值x0，噪聲sig，μ0，τ0，t0和α0。

3)執(zhí)行：μ=μi+1，重復如下步驟直至收斂。

(1)檢查零解。

(2)主迭代：執(zhí)行k=k+1，重復如下步驟直至滿足收斂條件或k≥Imax。

①計算v=τ/μ,yk=xk-1-τ·xk-1。

③更新tk，計算α0。

④計算系數(shù)τ。

4)輸出：重構(gòu)信號x*，算法時長time，信噪比SNR。

2.2不動點連續(xù)算法的性質(zhì)

定義1：設(shè)X是式(3)問題的一個最優(yōu)解集，且X≠φ，定義集合Ω，使集合中元素滿足下列條件

(12)

式中：x*∈X,ρ>0。

引理1：收縮算子sv(·)是非擴張的，即?x1,x2∈Rn，有以下不等式成立

(13)

引理2：算子hτ(·)是非擴張的，即?x,x′∈Ω，有以下不等式成立

(14)

當且僅當g(x)=g(x′)時，等號成立。另外，引理1和2的證明過程見文獻[11]。

(15)

證明

(16)

定理2：對于式(3)問題，假設(shè)x0∈Ω是不動點迭代的初始點，序列{xn}是迭代值，那么該序列最終會收斂于x*，且x*∈X*∩Ω。

證明：

(17)

最終，定理證畢[11]。

3　仿真實驗

本節(jié)實驗均是在2 Gbyte內(nèi)存2.53主頻的便攜式計算機上進行，軟件版本是MATLAB 7.0。

3.1收斂性實驗

實驗將不同參數(shù)下，分別計算出迭代步數(shù)和每步重構(gòu)值與原始信號之間的相對誤差rerr，相對誤差公式如下

(18)

式中：x是每次迭代的重構(gòu)值；xs是原始值。則從開始迭代到算法終止，相對誤差值的變化曲線如圖1所示。

圖1　重構(gòu)值與原始信號間相對誤差隨迭代步數(shù)增加時的變化曲線

從圖1可以看出，F(xiàn)FPC算法和原FPC算法的相對誤差值均隨迭代步數(shù)的不斷增加而逐漸減小，并且逐步趨近于零，這表明FFPC算法與原算法一樣是收斂的，并且，也說明FFPC算法具有可行性和一定的穩(wěn)定性。另一方面，在相同的實驗條件下，F(xiàn)FPC算法相比原算法所需的迭代步數(shù)更少，這間接說明FFPC的收斂速度更快。因此，數(shù)值實驗驗證了FFPC算法的收斂性，同時收斂性能也有所提升。

3.2視頻幀重構(gòu)實驗

各算法是按列對視頻信號進行重構(gòu)的，故每次實驗需要N輪迭代過程。分別利用各算法進行15次重構(gòu)實驗，統(tǒng)計所用實驗收斂時的迭代步數(shù)，然后計算出每輪迭代步數(shù)的平均值，即表1所列數(shù)據(jù)。表1中數(shù)據(jù)顯示，在不同測量率下，F(xiàn)FPC算法的平均迭代步數(shù)均比其他少，這些數(shù)值說明FFPC算法的收斂速度有所提高，尤其是當采樣率較低的情況下，提高較為明顯。

表1不同算法在不同測量率下每輪迭代步數(shù)的平均值

deltaITSFPCFFPC-2FFPC-30.3568540390.5394431320.728372120

另外，實驗中對各算法的重構(gòu)時間和峰值信噪比(PSNR)進行了計算和統(tǒng)計，具體數(shù)據(jù)見表2。這兩項指標反映了各算法重構(gòu)速率和質(zhì)量的性能。數(shù)據(jù)表明FFPC算法的重構(gòu)速率比其他算法都快，尤其與原FPC算法相比。另一方面，F(xiàn)FPC算法在重構(gòu)質(zhì)量上相比原FPC有所提升，且較ITS算法也有一定的優(yōu)勢。因此，F(xiàn)FPC算法不僅加快了重構(gòu)速率，而且提高了重構(gòu)質(zhì)量，比其他算法更高效地實現(xiàn)了重構(gòu)。為更直觀地觀察各算法的重構(gòu)效果，本節(jié)給出各算法在測量率delta=0.5時的重構(gòu)對比圖像，如圖2所示。

表2不同測量率下算法重構(gòu)的所耗時長和PSNR值

算法delta=0.3delta=0.5delta=0.7時長/sPSNR/dB時長/sPSNR/dB時長/sPSNR/dBITS6.810323.98745.082129.02434.280130.0007FPC10.717322.79945.985628.01034.789229.9778FFPC-25.396024.93354.511630.66354.031631.4201FFPC-35.130824.11354.427230.57674.067231.0078

圖2　測量率delta=0.5時的視頻幀重構(gòu)效果對比圖

4　小結(jié)

在壓縮感知重構(gòu)算法中，不動點連續(xù)(FPC)算法的收斂速度較慢，為解決這個問題，本文引入線性搜索步長，選擇步長參數(shù)序列{tn}，利用前兩次迭代結(jié)果的特定線性組合值來計算當前的迭代值，加速算法的收斂速度，從而提出了一種快速不動點連續(xù)(FFPC)算法。然后，通過對一維信號進行仿真實驗，驗證了FFPC算法的收斂性。另外，對于視頻幀進行重構(gòu)的對比實驗結(jié)果，一方面表明FFPC算法提高了收斂速度，另一方面表明FFPC算法的重構(gòu)速率明顯加快，重構(gòu)質(zhì)量也有所提升。因此，F(xiàn)FPC算法是一種快速高效的重構(gòu)算法。

[1]DONOHODL.Compressedsensing[J].IEEEtransationsoninformationtheory，2006，52(4)：1289-1306.

[2]盧雁，吳盛教，趙文強. 壓縮感知理論綜述[J]. 計算機與數(shù)字工程，2012，40(8)：12-14.

[3]NEEDELLD，TROPPJA.CoSaMP：iterativesignalrecoveryfromincompleteandinaccuratesamples[J].Applied&computationalharmonicanalysis，2008，26(12)：93-100.

[4]BLUMENSATHT，DAVIESME.Iterativethresholdingforsparseapproximations[J].Journaloffourieranalysis&applications，2008，14(5)：629-654.

[5]HALEET，YINW，ZHANGY.Fixed-pointcontinuationforl1-minimization：methodologyandconvergence[J].Siopt，2008，19(3)：1107-1130.

[6]BIOUCAS-DIASJM，F(xiàn)IGUEIREDOMAT.AnewtwIst：two-stepiterativeshrinkage/thresholdingalgorithmsforimagerestoration[J].IEEEtransactionsonimageprocessing，2007，16(12)：2992-3004.

[7]NESTEROVY.Gradientmethodsforminimizingcompositefunctions[J].Mathematicalprogramming，2013，140(3)：768-785.

[8]YAMAGISHIM，YAMADAI.Over-relaxationofthefastiterativeshrinkage-thresholdingalgorithmwithvariablestepsize[J].Inverseproblems，2011，27(10)：8-22.

[9]CANDESEJ，ROMBERGJ.Quantitativerobustuncertaintyprinciplesandoptimallysparsedecompositions[J].Foundationsofcomputationalmathematics，2006，6(2)：227-254.

[10]YINW，OSHERS，GOLDFARBD，etal.BregmaniterativealgorithmsforL1-minimizationwithapplicationstocompressedsensing[J].Siamjournalonimagingsciences，2008(1)：143-168.

[11]HALEET，YINW，ZHANGY.Afixed-pointcontinuationmethodfor'1-regularizedminimizationwithapplicationstocompressedsensing[J].CaamTr，2007(1)：1-43.

[12]CHAMBOLLEA，DOSSALC.Ontheconvergenceoftheiteratesofthe“fastiterativeshrinkage/thresholdingalgorithm”[J].Journalofoptimizationtheory&applications，2015(6)：1-15.

[13]謝志鵬. 基于前向后向算子分裂的稀疏信號重構(gòu)[J]. 南京大學學報(自然科學版)，2012，48(4)：7-15.

[14]WUG，LUOS.Adaptivefixed-pointiterativeshrinkage/thresholdingalgorithmforMRimagingreconstructionusingcompressedsensing[J].Magneticresonanceimaging，2014，32(4)：372-378.

郭青青(1991— )，女，碩士生，主研壓縮感知重構(gòu)算法及其應用，為本文通信作者；

李雷(1958— )，碩士生導師，教授，主研壓縮感知稀疏和重構(gòu)算法、深度學習等。

責任編輯：時雯

Reconstruction algorithm of compressed sensing based on fast fixed point continuation

GUO Qingqing，LI Lei

(CenterofComputingandApplicationforVisualCognitive，NanjingUniversityofPostsandTelecommunications，Nanjing210046，China)

Fixed Point Continuation (FPC) algorithm is a developed version of convex optimization algorithm，which is an important research method for reconstruction of Compressed Sensing (CS). In this paper，a fast FPC (FFPC) algorithm is proposed to accelerate the convergence speed of FPC algorithm. A linear search step is introduced，and then an efficient coefficient of shifting step is chosen，finally current iteration is updated by using special linear combination of two previous iterations，so the accuracy of each iteration is improved， and hence the convergence speed is accelerated. On the one hand，the convergence of FFPC algorithm has been proved in the experiment， on the other hand，the simulation experiments show that the convergence speed of FFPC algorithm is obviously improved，and the reconstruction quality is better than other algorithms.

convex optimization algorithm；compressed sensing；fast fixed point continuation

TN911

ADOI：10.16280/j.videoe.2016.10.002

國家自然科學基金項目(61501251；61071167)；江蘇省普通高校研究生科研創(chuàng)新計劃項目(KYZZ15_0236)；南京郵電大學引進人才科研啟動基金項目(NY214191)

2016-02-26

文獻引用格式：郭青青，李雷.基于快速不動點連續(xù)的壓縮感知重構(gòu)算法[J].電視技術(shù)，2016，40(10)：6-10.

GUO Q Q，LI L.Reconstruction algorithm of compressed sensing based on fast fixed point continuation[J].Video engineering，2016,40(10)：6-10.