基于快速不動點連續的壓縮感知重構算法

郭青青，李　雷

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

?

基于快速不動點連續的壓縮感知重構算法

郭青青，李雷

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

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

凸優化算法；壓縮感知；快速不動點連續

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

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

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

1　壓縮感知

1.1壓縮感知的重構模型

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

(1)

(2)

(3)

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

1.2不動點迭代連續(Fixed Point Continuation Algorithm，FPC)算法

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(x)的最小解迭代公式為

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

(5)

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

(6)

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

(7)

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

(8)

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

2　快速不動點連續算法(Fast FPC，FFPC)

2.1快速不動點連續算法

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

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

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

(9)

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

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

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

(10)

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

(11)

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

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

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

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

(1)檢查零解。

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

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

③更新tk，計算α0。

④計算系數τ。

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

2.2不動點連續算法的性質

定義1：設X是式(3)問題的一個最優解集，且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)問題，假設x0∈Ω是不動點迭代的初始點，序列{xn}是迭代值，那么該序列最終會收斂于x*，且x*∈X*∩Ω。

證明：

(17)

最終，定理證畢[11]。

3　仿真實驗

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

3.1收斂性實驗

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

(18)

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

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

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

3.2視頻幀重構實驗

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

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

deltaITSFPCFFPC-2FFPC-30.3568540390.5394431320.728372120

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

表2不同測量率下算法重構的所耗時長和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時的視頻幀重構效果對比圖

4　小結

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

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

[2]盧雁，吳盛教，趙文強. 壓縮感知理論綜述[J]. 計算機與數字工程，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，FIGUEIREDOMAT.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]謝志鵬. 基于前向后向算子分裂的稀疏信號重構[J]. 南京大學學報(自然科學版)，2012，48(4)：7-15.

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

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

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

責任編輯：時雯

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)；江蘇省普通高校研究生科研創新計劃項目(KYZZ15_0236)；南京郵電大學引進人才科研啟動基金項目(NY214191)

2016-02-26

文獻引用格式：郭青青，李雷.基于快速不動點連續的壓縮感知重構算法[J].電視技術，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.