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

郭青青，李　雷

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

?

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

郭青青，李雷

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

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

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

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

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

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

1　壓縮感知

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

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

(1)

(2)

(3)

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

1.2不動(dòng)點(diǎn)迭代連續(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：對(duì)于特定的τ>0，假設(shè)X*是式(3)的最優(yōu)解集，則x*∈X*當(dāng)且僅當(dāng)

(6)

于是，不動(dòng)點(diǎn)迭代公式可表示為

(7)

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

(8)

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

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

2.1快速不動(dòng)點(diǎn)連續(xù)算法

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

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

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

(9)

對(duì)于FIST算法，序列{tn}的選擇有兩類(lèi)形式[12]：

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

通過(guò)FFPC算法求解問(wèn)題(3)的迭代公式如下

(10)

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

(11)

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

算法1：快速不動(dòng)點(diǎn)連續(xù)(FFPC)算法

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

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

(1)檢查零解。

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

①計(jì)算v=τ/μ,yk=xk-1-τ·xk-1。

③更新tk，計(jì)算α0。

④計(jì)算系數(shù)τ。

4)輸出：重構(gòu)信號(hào)x*，算法時(shí)長(zhǎng)time，信噪比SNR。

2.2不動(dòng)點(diǎn)連續(xù)算法的性質(zhì)

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

(12)

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

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

(13)

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

(14)

當(dāng)且僅當(dāng)g(x)=g(x′)時(shí)，等號(hào)成立。另外，引理1和2的證明過(guò)程見(jiàn)文獻(xiàn)[11]。

(15)

證明

(16)

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

證明：

(17)

最終，定理證畢[11]。

3　仿真實(shí)驗(yàn)

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

3.1收斂性實(shí)驗(yàn)

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

(18)

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

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

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

3.2視頻幀重構(gòu)實(shí)驗(yàn)

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

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

deltaITSFPCFFPC-2FFPC-30.3568540390.5394431320.728372120

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

表2不同測(cè)量率下算法重構(gòu)的所耗時(shí)長(zhǎng)和PSNR值

算法delta=0.3delta=0.5delta=0.7時(shí)長(zhǎng)/sPSNR/dB時(shí)長(zhǎng)/sPSNR/dB時(shí)長(zhǎng)/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　測(cè)量率delta=0.5時(shí)的視頻幀重構(gòu)效果對(duì)比圖

4　小結(jié)

在壓縮感知重構(gòu)算法中，不動(dòng)點(diǎn)連續(xù)(FPC)算法的收斂速度較慢，為解決這個(gè)問(wèn)題，本文引入線性搜索步長(zhǎng)，選擇步長(zhǎng)參數(shù)序列{tn}，利用前兩次迭代結(jié)果的特定線性組合值來(lái)計(jì)算當(dāng)前的迭代值，加速算法的收斂速度，從而提出了一種快速不動(dòng)點(diǎn)連續(xù)(FFPC)算法。然后，通過(guò)對(duì)一維信號(hào)進(jìn)行仿真實(shí)驗(yàn)，驗(yàn)證了FFPC算法的收斂性。另外，對(duì)于視頻幀進(jìn)行重構(gòu)的對(duì)比實(shí)驗(yàn)結(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]盧雁，吳盛教，趙文強(qiáng). 壓縮感知理論綜述[J]. 計(jì)算機(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]謝志鵬. 基于前向后向算子分裂的稀疏信號(hào)重構(gòu)[J]. 南京大學(xué)學(xué)報(bào)(自然科學(xué)版)，2012，48(4)：7-15.

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

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

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

責(zé)任編輯：時(shí)雯

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

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

2016-02-26

文獻(xiàn)引用格式：郭青青，李雷.基于快速不動(dòng)點(diǎn)連續(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.