黃文麗, 唐玉超, 文 萌
(1. 南昌大學(xué)數(shù)學(xué)系,南昌 330031; 2. 西安工程大學(xué)理學(xué)院,西安 710048)
信號和圖像處理[1]、醫(yī)學(xué)圖像重建[2]和機(jī)器學(xué)習(xí)[3]等中的許多問題都可以歸結(jié)為求解下列形式的優(yōu)化問題
事實上,迭代序列(4)恢復(fù)了Micchelli 等人[14]提出的不動點鄰近點算法(Fixed Point Algorithm Based on Proximity Operator, FP2O)?;谖墨I(xiàn)[14]的理論結(jié)果,可知由(4)式定義的迭代序列{xk}在有限維Hilbert 空間中收斂到如下優(yōu)化問題的解
另一方面,Condat[24]提出并研究了如下更加一般的三個凸函數(shù)和的優(yōu)化問題
其中f、φ和L同問題(1),h:H →(?∞,+∞]是正則下半連續(xù)凸函數(shù)。易見,當(dāng)h(x)=0 時,問題(6)退化為(1)。為求解問題(6),Condat 提出了一種原始對偶分裂算法,并基于向前向后算子分裂算法框架,證明了所提算法的收斂性。在這里,我們給出當(dāng)h(x)=0 時,Condat 所提出的原始對偶分裂算法格式
本文工作創(chuàng)新點歸納如下:
1) 建立求解優(yōu)化問題(1)的不動點方程。通過構(gòu)造合適的范數(shù),證明該不動點方程中的算子是平均的。從而提出具有超松弛的原始對偶不動點算法;
2) 基于現(xiàn)有不動點結(jié)論,證明所提算法的收斂性。同時,我們分析算法的遍歷收斂率,所得結(jié)果對于PDFP2O 算法是新的。進(jìn)一步,在對目標(biāo)函數(shù)較強(qiáng)假設(shè)條件下,證明所提算法的線性收斂率;
3) 通過將所提算法應(yīng)用于圖像復(fù)原模型,數(shù)值結(jié)果表明,當(dāng)步長參數(shù)γ固定時,松弛參數(shù){αk}越大,算法收斂越快。本文所提算法所需迭代次數(shù)少于ADMM 算法[21]、PDS 算法[24]和PDFP2O 迭代算法[7]。雖然在某些情形下,所提算法的迭代次數(shù)多于PDFP2O AM 算法[19],但后者需要假設(shè)圖像邊界條件是周期的,而所提算法適合于任何邊界條件的圖像復(fù)原問題,從而應(yīng)用范圍更廣。
本文具體安排如下,在第1 節(jié)中,我們給出一些證明所提算法收斂性需要的定義和引理。第2 節(jié)提出一種超松弛原始對偶不動點算法求解問題(1),同時分析和證明所提算法的收斂性和遍歷收斂率,以及線性收斂率。第3 節(jié)將算法應(yīng)用于求解全變分圖像復(fù)原模型,以驗證算法的有效性和優(yōu)越性。最后,我們對全文進(jìn)行小結(jié)。
在本節(jié)中,我們將回顧一些基本定義和引理,這些可參見文獻(xiàn)[35—36]等。設(shè)H是實Hilbert 空間,定義在H上的內(nèi)積為〈·,·〉和范數(shù)為//·//。設(shè)L:H →G是非零有界線性算子,其中G是實Hilbert 空間。L?:G →H表示L的伴隨算子,滿足〈y,Lx〉=〈L?y,x〉, ?x,y ∈H。
設(shè)A:H →2H是一集值算子,我們分別用graA={(x,u)∈H×H:u ∈Ax}和ranA={u ∈H:?x ∈H,u ∈Ax}表示A的圖和值域。算子A稱為單調(diào)的,如果〈x ?y,u ?v〉 ≥0, ?(x,u),(y,v)∈graA。A稱為極大單調(diào)的,如果A是單調(diào)的且不存在單調(diào)算子B,使得B的圖包含A的圖。A稱為τ-強(qiáng)單調(diào)的,τ>0,如果
下面,我們回顧非擴(kuò)張等算子定義。
定義1[35]設(shè)C是H的一個非空子集,T:C →H,則:
1)T稱為κ-Lipschitz 連續(xù)的,如果
特別κ=1 時,T稱為非擴(kuò)張的;κ ∈(0,1),T稱為壓縮的;
2)T稱為σ-余強(qiáng)制的,σ>0,如果
特別當(dāng)σ=1 時,T稱為固定非擴(kuò)張的;
3)T稱為α-平均的,α ∈(0,1),如果存在非擴(kuò)張算子S,使得
f的次微分?f定義為
設(shè)f ∈Γ0(H), λ>0, λf的鄰近算子定義為
則有如下結(jié)論成立:
1){xk}關(guān)于Fix(T)是Fej′er 單調(diào)的,即//xk+1?x?//≤//xk ?x?//, ?x?∈Fix(T);
2){Txk ?xk}強(qiáng)收斂于0;
3){xk}弱收斂于Fix(T)。
為建立本文算法的線性收斂率,我們將利用經(jīng)典的Banach 壓縮映射原理。
引理3(Banach 壓縮映射原理)[35]設(shè)(X,d)是完備度量空間,設(shè)T:X →X是θ-Lipschitz 連續(xù)算子,其中θ ∈(0,1)。定義Picard 迭代序列如下:任取x0∈X,定義xk+1=Txk,則存在x?∈X,使得以下結(jié)論成立:
和余弦等式
以及K是H上的一自伴隨強(qiáng)正算子。
這兩個結(jié)論在我們的證明中同樣起著重要的作用。
為了求解問題(1),我們首先給出超松弛原始對偶不動點算法的算法格式如下。
算法1 超松弛原始對偶不動點算法(Or PDFP2O)
Require: 任取x0 ∈H, v0 ∈G,選取λ ∈(0, 1//L//2),γ ∈(0,2β),以及αk ∈[0, 4β?γ 2β ]。當(dāng)k =0,1,2,···,計算(i) ~vk+1 =prox λγ φ?((I ?λLL?)vk+ λγ L(xk ?γ?f(xk)));(ii) ~xk+1 =xk ?γ?f(xk)?γL?~vk+1.(iii) vk+1 =(1 ?αk)vk+αk~vk+1;(iv) xk+1 =(1 ?αk)xk+αk~xk+1.當(dāng)滿足給定終止條件時,停止;否則,繼續(xù)。Ensure: xk+1, vk+1.
根據(jù)Moreau 恒等式,設(shè)f ∈Γ0(H),對任意λ>0 和x ∈H,有
我們可知算法1 中(i)等價于
以及算法1 中(ii)等價于
定義T2:G×H →H為
進(jìn)一步,定義算子T:G×H →G×H為
引理4 設(shè)λ> 0, γ> 0,若(v?,x?)是算子T的不動點,則x?是問題(1)的解。反之,若x?是問題(1)的解,則存在v?∈G,使得(v?,x?)是T的不動點。
證明 由T的定義知,若(v?,x?)是T的不動點,那么有
根據(jù)(13)式和(14)式,我們可得
于是,我們有
即x?滿足問題(1)的一階優(yōu)化條件,從而是該問題的解。
反過來,若x?是問題(1)的解,由一階優(yōu)化條件,我們有
根據(jù)(20)式,有v?=T1(v?,x?),進(jìn)一步用T1(v?,x?)替代(18)式中v?,則有x?=T2(v?,x?),從而(v?,x?)是T的不動點。
下面,我們通過在G×H空間中定義合適的范數(shù),證明由(12)式定義的算子T不僅是非擴(kuò)張的,并且是一個平均算子。為了表達(dá)簡潔,我們引進(jìn)和定義一些符號,記
根據(jù)(12)式,并結(jié)合(24)式和(25)式,可得
又
其中(28)式中第一個不等式由?f是β-余強(qiáng)制算子得到,第二個不等式由Young 不等式得到。將(28)式代入(27)式,我們有
下面,我們證明算法1 的收斂性。
設(shè)序列{vk}和{xk}由算法1 生成,(v?,x?)∈Fix(T),則有下列結(jié)論成立:
證明 根據(jù)算子T的定義,我們可知由算法1 定義的迭代序列{vk}和{xk}等價于
從而,根據(jù)引理2,我們可得結(jié)論1)~3)成立。
在本小節(jié)中,我們將分析算法1 的遍歷收斂率和線性收斂率。首先我們證明遍歷收斂率。為此,我們給出優(yōu)化問題(1)的鞍點問題形式如下
由G(x,v)關(guān)于x的凸性和v的凹性,并結(jié)合Jensen 不等式,即得(34)式。
自然地
那么(34)式成立。
由(39)式,我們可得
根據(jù)Young 不等式,我們有
將(41)式代入(40)式,可得
(42)式中第二個不等號由?f是β-余強(qiáng)制的推得,第三個不等號由條件(A1)和(A2)推得。因此
根據(jù)定理3 的結(jié)論,顯然有ρ< 1,也就是說算子T是壓縮的。下面,我們給出算法1 的線性收斂率結(jié)果。
在本節(jié)中,我們應(yīng)用所提出的算法1 求解經(jīng)典的L2+TV圖像復(fù)原模型
其中K ∈Rm×n表示模糊核矩陣,b ∈Rm×n表示觀測圖像,μ> 0 表示正則參數(shù),以及//x//T V表示全變分。注意到全變分//x//T V可以表示為一凸函數(shù)φ和差分矩陣L復(fù)合的形式,即//x//T V=φ(Lx),詳細(xì)可參見文獻(xiàn)[14,38]等。從而模型(44)是問題(1)的特殊情形。
本節(jié)所有的實驗是在聯(lián)想筆記本E4430 完成的,其中CPU 2.3GHZ 和內(nèi)存4GB。實驗編程軟件為Matlab R2014a。我們應(yīng)用Matlab 函數(shù)fspecial 和imfilter 生成模糊圖像,具體定義如下
其中η表示加入高斯噪聲的標(biāo)準(zhǔn)差,alpha 表示平均核的大小,x表示原始圖像,以及b表示觀測圖像,實驗測試圖像見圖1。
圖1 測試圖像
實驗1 在實驗1 中,我們說明松弛參數(shù)對算法1 收斂速度的影響。對比原始PDFP2O算法2,本文提出的算法1 提供了更大的松弛參數(shù)選擇范圍。特別地,算法1 允許松弛參數(shù)大于1。因此,在接下來的實驗中,我們通過固定步長參數(shù)γ,根據(jù)松弛參數(shù)αk的取值范圍,選擇不同αk,報告所得數(shù)值結(jié)果,詳細(xì)參數(shù)選取規(guī)則見表1。
表1 算法1 中步長參數(shù)γ 和松弛參數(shù)αk 的選取
根據(jù)文獻(xiàn)[14],對于全變分一階差分矩陣L,知//L//2≈8,因此,我們?nèi)ˇ?。此外,在本實驗中β=1。我們選取圖1中的文本圖像作為測試圖像。在實驗中,我們?nèi)∑骄说拇笮ˇ? 3 以及η= 0.01。我們選取正則參數(shù)μ= 0.001。為評估復(fù)原圖像的質(zhì)量,我們選擇信噪比(SNR)作為評價指標(biāo),其定義如下
這里x和xr分別表示原始圖像和恢復(fù)所得圖像。同時,我們給定算法的迭代停止準(zhǔn)則為
這里ε是一給定正數(shù),所得數(shù)值結(jié)果見表2。
表2 不同步長參數(shù)γ 和松弛參數(shù)αk 的數(shù)值結(jié)果
續(xù)表
從表2 可以看出,當(dāng)步長參數(shù)γ固定,松弛參數(shù)越大,算法收斂越快。當(dāng)γ取值較保守時(γ ≤1),松弛參數(shù)αk> 1(超松弛情形)顯然比松弛參數(shù)αk< 1 算法收斂更快。當(dāng)γ接近理論上界時,隨著求解精度的增高,超松弛參數(shù)算法所需迭代次數(shù)少于松弛參數(shù)αk=1 的情形。因此,在接下來的實驗中,我們選取γ=1.9 和αk=1.04。
實驗2 在實驗2 中,我們比較所提迭代算法1 與現(xiàn)有其他算法,包括ADMM 算法[21]、PDS 算法[24]、PDFP2O 算法[7]和PDFP2O AM 算法[19]。我們選取圖1 中的四幅圖像作為測試圖像,我們?nèi)煞N不同大小的平均核分別是α= 3 和α= 7,并對每幅相應(yīng)圖像分別添加均值為零,標(biāo)準(zhǔn)差為0.01 和0.05 的高斯噪聲。我們假定邊界條件為周期邊界條件,這時,對于ADMM 算法和PDFP2O AM 算法中矩陣的逆,可以通過快速Fourier 變換計算。我們調(diào)整正則參數(shù)μ以期達(dá)到最佳的圖像復(fù)原結(jié)果,相應(yīng)正則參數(shù)選取規(guī)則見表3。除了信噪比(SNR)以外,我們使用結(jié)構(gòu)相似性指數(shù)(SSIM)[39]來評估恢復(fù)圖像質(zhì)量,SSIM 具體定義如下
表3 不同噪聲水平下,最佳正則參數(shù)μ的選取規(guī)則
其中μx和μxr分別表示原始圖像和恢復(fù)所得圖像的平均灰度值,σx和σxr表示的是兩幅圖像的標(biāo)準(zhǔn)差,C1和C2為給定的非零常數(shù)。所得數(shù)值結(jié)果見表4 和表5。
從表4 和表5 可以看出,當(dāng)ε=10?8時,分別取兩種不同的平均核α=3, α=7 和噪聲水平η= 0.01,對于風(fēng)景和靜物的測試圖像,本文所提算法(算法1)比其他算法所需迭代次數(shù)更少。在其他情形下,算法1 僅次于PDFP2O AM 算法。由于PDFP2O AM 算法只在周期邊界條件下才能執(zhí)行,而本文所提算法與PDS 算法以及PDFP2O 算法可以適合于任何邊界條件的圖像復(fù)原問題,從而更具有廣泛的應(yīng)用性。為了更加直觀觀察恢復(fù)圖像,圖2 至圖5 分別展示了當(dāng)ε=10?8時,五種算法恢復(fù)所得圖像。
表4 平均核α=3 時,比較不同迭代算法所得數(shù)值結(jié)果
續(xù)表
表5 平均核α=7 時,比較不同迭代算法所得數(shù)值結(jié)果
續(xù)表
圖2 至圖5 中的第一行是模糊和噪聲圖像;第二行是由ADMM 恢復(fù)的圖像;第三行是由PDS 恢復(fù)的圖像;第四行是由PDFP2O 恢復(fù)的圖像;第五行是由PDFP2O AM 恢復(fù)的圖像;第六行是由算法1 恢復(fù)的圖像。
圖2 模糊和噪聲圖像(文本)
圖5 模糊和噪聲圖像(靜物)
圖3 模糊和噪聲圖像(人像)
圖4 模糊和噪聲圖像(風(fēng)景)
本文提出了一種超松弛原始對偶不動點算法求解兩個凸函數(shù)和的優(yōu)化問題(1)。相比于現(xiàn)有的原始對偶不動點算法(2),本文的算法允許松弛參數(shù)大于1,從而擴(kuò)大了原算法的松弛參數(shù)的選擇范圍。通過構(gòu)造合適的范數(shù),基于不動點理論,我們證明了所提算法的收斂性,同時證明了算法的遍歷收斂率。進(jìn)一步,在對目標(biāo)函數(shù)較強(qiáng)假設(shè)條件下,我們證明了算法的線性收斂率。為驗證算法的有效性和優(yōu)越性,我們應(yīng)用于求解全變分圖像復(fù)原模型(44),數(shù)值實驗結(jié)果表明,超松弛參數(shù)算法優(yōu)于松弛參數(shù)小于等于1 的情形。
無論是PDFP2O 算法,還是本文提出的超松弛PDFP2O 算法(算法1),算法的步長參數(shù)依賴于目標(biāo)函數(shù)梯度的Lipschitz 常數(shù),當(dāng)該常數(shù)未知時,只能憑經(jīng)驗選取步長。因此如何克服這個不足,使得算法更加方便執(zhí)行,這將是我們接下來研究的問題。