基于懲罰參數(shù)自適應(yīng)選擇原理的穩(wěn)健交替方向乘子法

基于懲罰參數(shù)自適應(yīng)選擇原理的穩(wěn)健交替方向乘子法

圖像恢復(fù)是一個經(jīng)典的線性問題。其中:x是原圖像,即目標(biāo)圖像;A是線性算子的矩陣表示,一般為模糊矩陣;y為觀測圖像,即需要修復(fù)的圖像;n則為噪聲。眾所周知,從y中修復(fù)出x是一個欠定問題,即存在多個解。幸運的是,如果x是稀疏的或在某個特定的域里稀疏,可以利用壓縮感知(compressedsensing)理論對于圖像來說,x表示的是各個像素點的灰度值,因此x不是稀疏變量。但是圖像在某些特定的小波或框架(一般假設(shè)為緊框架)中表示的系數(shù)是稀疏的。文獻[3]提供了這兩種表示方法———分析(analysis)和合成(synthesis)方法。對于前者來說,其模型為:其中,λ為正則化參數(shù),P為分析算子,則Px表示的是在小波基或緊框架下的稀疏系數(shù)其中,W為框架矩陣,則圖像x=Ws,其中s為相應(yīng)的稀疏系數(shù)。注意式(2)和式(3)都是凸優(yōu)化問題,其正則化項l解決問題(2)~(3)最經(jīng)典的方法是迭代閾值收縮(IterativeShrinkage/Thresholding,IST)算法,其核心是所謂的閾值收縮函數(shù),也被稱為Moreau近似映射或去噪函數(shù),定義為:當(dāng)f(x)為l但是當(dāng)矩陣A處在病態(tài)條件下,IST算法在解決問題(2)~(3)時會變得很慢。為了克服這一點,許多加速版本的IST算法被提出來了。例如,TwIST(TwostepIST)近幾年來,除了以上的IST系列算法,交替方向乘子法(AlternatingDirectionsMethodofMultipliers,ADMM)盡管SALSA相對于其他的算法表現(xiàn)出了很大的優(yōu)勢,但是它在具體實施中怎樣選擇懲罰參數(shù)是一個難題。事實上,SALSA的結(jié)果對懲罰參數(shù)的選擇非常敏感,為了達到滿意的結(jié)果,在實施中不得不做大量的嘗試以選擇最合適的懲罰參數(shù)。本文正是為了克服這一難題,利用懲罰參數(shù)自適應(yīng)選擇原理1admm算法的結(jié)構(gòu)1.1優(yōu)化問題和admm算法首先考慮下面的非約束優(yōu)化問題:而ADMM1.2ecskte和bertsekas定理1、2.對于問題(7)和相應(yīng)的ADMM算法(算法2),Eckstein和Bertsekas定理1假設(shè)1:B∈R假設(shè)2:f,g是正常的閉凸函數(shù);那么,如果問題(7)有解,序列(x1.3篩選條件中vv對于問題(7),其優(yōu)化的充分必要條件如下。假設(shè)x其對偶可行性有的優(yōu)化解,因此分別比較式(10)和式(14),式(9)和式(13),不難發(fā)現(xiàn)v被當(dāng)成是式(13)的剩余值,也稱為第k+1迭代步時的對偶剩余值(dualresidual)。而被稱為原始剩余值(primalresidual)?？傊?ADMM算法的優(yōu)化條件是式(8)、式(9)和式(10)。式(10)在迭代過程中總是滿足的,而原始和對偶剩余值:pr2穩(wěn)定admm算法的結(jié)構(gòu)基于上面的ADMM算法框架,可以結(jié)合基于原始和對偶剩余值的懲罰參數(shù)μ自適應(yīng)選擇原理2.1懲罰參數(shù)的自適應(yīng)選擇原則為了加快ADMM算法的收斂速度,可以考慮每一個迭代中采用不同的懲罰參數(shù)μ值得一提的是,在ADMM算法中懲罰參數(shù)μ2.2穩(wěn)定admm算法結(jié)合算法1,式(15)、式(16)和式(18),可以得到基于懲罰參數(shù)自適應(yīng)選擇的RADMM算法,見算法2。2.3salsa算法無論如何,RADMM都可以看作是:在前面有限迭代中通過調(diào)整懲罰參數(shù)μ來控制原始和對偶剩余值,然后停止使用懲罰參數(shù)自適應(yīng)選擇,從而退化成SALSA算法?；诖?如果SALSA收斂,則RADMM收斂。而1.2節(jié)保證了SALSA的收斂,從而保證了RADMM的收斂。下面將利用RADMM進行圖像恢復(fù)。3算法2中各計算復(fù)雜度這一部分采用式(3)作為優(yōu)化模型對圖像進行修復(fù),并進一步假設(shè)A為塊輪換卷積矩陣(block-circulantconvolutionmatrix),W為標(biāo)準(zhǔn)化緊框架矩陣(即Parseval緊框架),則有:其中,W對于式(20),算法2中的Step2~3變?yōu)?簡單分析可知,在式(21)中,通過設(shè)置目標(biāo)函數(shù)的導(dǎo)數(shù)為0,可以得到:其中,ω在式(23)中,根據(jù)Sherman-MorrisonWoodbury矩陣求逆公式,有其中:U為酉(unitary)矩陣(即有U如果直接用FFT算法來表示式(27),則有:其中:“ue0c9”和“·—”分別表示點乘和點除,即對應(yīng)的元素相乘和相除;F表示FFT算法,則F值得一提的是,由于采取的是設(shè)置方案(20),因此在算法2中相應(yīng)的B=I。算法2中計算復(fù)雜度最大的兩步是Step2和Step3,為O(NlogN),其他迭代步驟的計算復(fù)雜度為O(N)或O(1)。因此,總體計算復(fù)雜度為O(NlogN)。4高斯噪聲n本實驗中,對于模型(1),原始圖像x選用圖像“Lena”(見圖1,512×512像素),A對應(yīng)9×9的均勻模糊算子,其通過構(gòu)造相應(yīng)的循環(huán)矩陣并進行FFT變換得到,n為高斯噪聲。y為模糊和加噪聲后的觀測圖像,例如,信噪比(SignaltoNoiseRatio,SNR)為40dB的模糊圖片見圖2。4.1radm和其他算法從表1可以看出,在不同噪聲水平下,對于指標(biāo):時間、迭代數(shù)、MSE和ISNR,RADMM都好于SALSA,并遠遠優(yōu)于其他熱門的算法。4.2比較radm和salsa4.2.1salsa對的選擇SALSA算法具體實施的一個難點就是選擇合適的懲罰參數(shù)μ,這也給算法的結(jié)果帶來很多不確定性。而RADMM則很好地克服了這個問題。為了驗證這一點,在4.1節(jié)的實驗設(shè)置中改變μ從10從圖8可以看出,SALSA得到的ISNR對μ的選擇非常敏感,當(dāng)μ=0.01左右時,SALSA取得較好的ISNR(這也是4.1節(jié)設(shè)置μ為0.01的原因),但當(dāng)隨著μ減少或增大時,ISNR急劇減少,因此SALSA需要不斷地嘗試μ才能得到滿意的結(jié)果。與之形成對比的是,RADMM得到的ISNR對μ的選擇很穩(wěn)健,所以在使用RADMM時,對μ的選擇相對隨意。同理,依照圖9,SALSA得到的MSE對μ的選擇非常敏感,當(dāng)μ=0.01左右時,SALSA得到較小的MSE,而當(dāng)隨著μ減少或增大時,MSE急劇增大;但是RADMM卻表現(xiàn)出了相當(dāng)好的穩(wěn)健性。4.2.2原始剩余值和對偶剩余值除了把停止條件只限定為迭代數(shù)Iterations≤500,其他的實驗設(shè)置和4.1節(jié)相同。對圖像“Lena”實驗得到的原始和對偶剩余值的演變過程如圖10所示。注意,由于SALSA只是RADMM的一個特殊情況,因此SALSA的原始剩余值pr和對偶剩余值dr可由在RADMM中設(shè)置α=β=1得到。RADMM中原始和對偶剩余值分別為pr從圖10不難看出,隨著迭代的進行,RADMM使pr和dr收斂到同一水平。根據(jù)2.1節(jié)的分析,這非常有利于算法快速地收斂到全局最優(yōu)解。而SALSA中由于沒有在迭代過程中對懲罰參數(shù)μ進行控制,導(dǎo)致pr和dr各行其道,不利于其收斂到全局最優(yōu)解,這也是4.1節(jié)所顯示出SALSA劣于RADMM的原因。4.2.3算法的收斂性RADMM和SALSA中的第k步迭代擾動被定義為:從定義可以看出,迭代擾動衡量的是每一個迭代中,不同分裂變量之間的差異。其一定程度上反映了算法的收斂狀況,因為在算法的不斷迭代過程中,不同的分裂變量會最終收斂到全局最優(yōu)解。這里仍然設(shè)定算法停止條件為Iterations≤500,并取μ=0.1、0.01和0.001,則相應(yīng)的RADMM和SALSA的迭代擾動如圖11所示。分析圖11可以得出:RADMM的迭代擾動總是低于SALSA,并且隨著μ的減少(增大),這兩種算法迭代擾動的差距增大(減少)。這也從側(cè)面反映出RADMM性能上的優(yōu)勢。5穩(wěn)健交替方向乘子法為了取得良好的效果,交替方向乘子法在實際應(yīng)用中不得不做大量的嘗試,以選擇合適的懲罰參數(shù)。針對其對懲罰參數(shù)這一較差的穩(wěn)健性,提出了穩(wěn)健交替方向乘子法。正是采用了懲罰參數(shù)自適應(yīng)選擇原理,對原始和對偶剩余值進行綁定,使兩者同步和同水平減少,不但使收斂加快,并且提高了結(jié)果的精度。在基于緊框架的圖像恢復(fù)應(yīng)用中,穩(wěn)健交替方向乘子法不但對懲罰參數(shù)的選擇表現(xiàn)出良好的穩(wěn)健性,而且