投影梯度算法求解非線性反問題的αl1-βl2正則化

趙祝光，丁 亮

(東北林業(yè)大學(xué))

0 引言

該文考慮求解(1)式的非線性算子方程

A(x)=y,

(1)

其中x是稀疏的，A:l2→Y是l2和Y之間的非線性映射，Y為Banach空間，其范數(shù)為‖·‖Y.在實(shí)際問題中，由于誤差的存在，精確數(shù)據(jù)y不能預(yù)先得到，所觀測(cè)的數(shù)據(jù)yδ往往帶有擾動(dòng)或噪聲，y與yδ滿足‖y-yδ‖≤δ，其中δ為噪聲水平.通常求解(1)的方法有l(wèi)p(p≥1)稀疏正則化[1-4].然而lp(p≥1)正則化有時(shí)無法提供最稀疏的解，因此提出非凸lp(0≤p<1)稀疏正則化作為其替代方法.關(guān)于l0稀疏正則化，可參考文獻(xiàn)[5-8].在最近5年里，αl1-βl2正則化在稀疏恢復(fù)領(lǐng)域已經(jīng)引起了很大關(guān)注[9-13].作為lp(0≤p<1)的一種替代，函數(shù)

α‖·‖l1-β‖·‖l2(α≥β≥0)

具有較好的性質(zhì)，它是l0-范數(shù)一種較理想的近似.從計(jì)算的角度來看，該函數(shù)具有比l0更簡(jiǎn)單的結(jié)構(gòu).在文獻(xiàn)[9]中，作者研究了形式為

(2)

的正則化的適定性和收斂速度，其中A是有界線性算子，

Rα,β(x)=α‖x‖l1-β‖x‖l2,α≥β≥0,q≥1.

其中，

Rη(x)=‖x‖l1-η‖x‖l2,α>0,1≥η≥0.

特別地，當(dāng)q=2，文獻(xiàn)[9]提出了求解問題(2)的ST-(αl1-βl2)算法：

(3)

其中，sk為步長(zhǎng)，λ>0.與經(jīng)典的迭代軟閾值算法類似，ST-(αl1-βl2)算法結(jié)構(gòu)簡(jiǎn)單，容易實(shí)現(xiàn).然而，ST-(αl1-βl2)算法可以任意慢，因此構(gòu)建ST-(αl1-βl2)算法的加速方法是有意義的.文獻(xiàn)[14]通過拓展投影梯度算法求解問題(2)，提出了算法(3)的兩個(gè)加速替代方法，分別為基于廣義條件梯度方法的投影梯度算法和基于替代函數(shù)的投影梯度算法.而該文的主要目的是將前一種投影梯度算法進(jìn)行推廣.用基于廣義條件梯度方法的投影梯度算法求解非線性不適定反問題的非凸αl1-βl2稀疏正則化.該文選擇投影梯度方法有兩個(gè)原因，首先，它的表達(dá)式簡(jiǎn)單并且容易實(shí)現(xiàn)，另一個(gè)原因是它收斂得相當(dāng)快，因此足以解決大規(guī)模不適定問題.

該文結(jié)構(gòu)為：第一節(jié)為預(yù)備知識(shí).在第二節(jié)中給出求解αl1-βl2稀疏正則化的基于廣義條件梯度方法的投影梯度算法.第三節(jié)給出確定l1-球約束半徑R的方法，并證明算法的穩(wěn)定性.

1 預(yù)備知識(shí)

該文主要通過下列正則化方法來求解非線性不適定反問題(1)：

α‖x‖l1-β‖x‖l2,α≥β≥0 .

(4)

定義

(5)

假設(shè)1 令非線性算子A:l2→Y滿足如下條件：

(1)A是有界的.

(2)A有連續(xù)的Fréchet導(dǎo)數(shù).

(3)A′(nn)*y→A′(x*)*y對(duì)于所有的y成立.

定義1 如果x?∈l2滿足

A(x?)=y,

Rη(x?)=min{Rη(x)|x∈l2,A(x)=y},

則x?稱為問題(1)的Rη-最小范數(shù)解.

定義2 如果supp(x)={i∈N|xi≠0}，則x∈l2稱為稀疏的，其中xi是x的第i個(gè)分量.對(duì)于s∈N，如果‖supp(x)‖0=s，則x∈l2為s-稀疏.

定義3 (Morozov偏差原則)對(duì)于1<τ1≤τ2，選擇α=α(δ,yδ)>0使得

定義4 對(duì)于給定的α>0，軟閾值算子被定義為

其中ei=(0,…,0,1,0,…)，xi是x的第i個(gè)分量，并且

定義5 在l1-球上的投影定義為

接下來回顧文獻(xiàn)[15]中關(guān)于軟閾值算子和投影算子之間關(guān)系的兩個(gè)結(jié)果，關(guān)于參數(shù)α和R的關(guān)系，參考文獻(xiàn)[15，F(xiàn)ig.2].

引理1 對(duì)于可數(shù)指標(biāo)集Λ，記lp=lp(Λ)，1≤p<∞.對(duì)于任意固定的a∈l2(Λ)并且α>0,‖Sα(a)‖l1是一個(gè)分段線性的、連續(xù)的、關(guān)于α的遞減函數(shù).此外，如果a∈l1(Λ)，則‖S0(a)‖l1=‖a‖l1，并且當(dāng)α≥maxi|ai|時(shí)，有‖S0(a)‖l1=0.

引理2 如果‖a‖l1>R，則a在半徑為R的l1-球上的l2投影PR(a)=Sα(a)，其中選擇α使得‖Sα(a)‖l1=R成立.如果‖a‖l1≤R，則PR(a)=S0(a)=a.

引理4 設(shè)H是內(nèi)積為〈·,·〉、范數(shù)為‖·‖H的希爾伯特空間，對(duì)于任意x∈H，PR(x)被刻畫為H中的唯一向量，使得

〈w-PR(x),x-PR(x)〉≤0,?w∈BR.

此外，投影PR是非擴(kuò)展的，即

?x′,x″∈H.

2 基于廣義條件梯度方法的投影梯度算法

其中

Φ(x)=Θ(x)+α‖x‖l1-β‖x‖l2,

算法1陳述了ST-(αl1-βl2)算法，算法1的收斂性見定理1，其詳細(xì)證明可見文獻(xiàn)[16，定理4.8].

算法1 (有限維空間中問題(4)的ST-(αl1-βl2)算法)

(1)選擇x0∈Rn，并且設(shè)k=0.

(2)如果xk=0，那么

(3)否則，確定下降方向zk，使其滿足

(4)確定步長(zhǎng)sk，使其滿足

(5)令xk+1=xk+sk(zk-xk)，k=k+1，返回第三步.

接下來給出問題(4)的一階優(yōu)化條件.

成立，上式等價(jià)于

對(duì)于所有z∈l2，t∈[0,1]成立.因此可以得到

當(dāng)t→0+時(shí)，引理得證.

算法1中關(guān)鍵的一步是zk的獲取，使其滿足

(6)

文獻(xiàn)[2]通過下列式子求解問題(6)：

(7)

然而，(7)收斂地任意慢，為了加速ST-(αl1-βl2)算法，該文將(6)轉(zhuǎn)化為下列形式的約束優(yōu)化問題：

(8)

(9)

(10)

對(duì)于任意λ>0成立，(10)等價(jià)于

(11)

且f′(0+)≥0與(11)是等價(jià)的.

接下來給出具體的投影梯度算法.

算法2 (問題(4)的投影梯度算法)

(1)選擇x0∈Rn，并且設(shè)k=0.

(2)如果xk=0，那么

(3)否則，確定下降方向zk，使其滿足

yδ)).

(4)確定步長(zhǎng)sk，使其滿足

(5)令xk+1=xk+sk(zk-xk)，k=k+1，返回第三步.

3 半徑R的確定

從前面的討論可以知道，對(duì)于某個(gè)R，問題(6)和(8)是等價(jià)的.在開始迭代(9)之前，需要選擇一個(gè)恰當(dāng)?shù)腞，特別在實(shí)際應(yīng)用中，R的選取對(duì)于計(jì)算是十分重要的.該節(jié)通過Morozov偏差原則給出一個(gè)確定l1-球約束半徑R的方法.

所以一個(gè)關(guān)鍵的問題是如何檢查問題(8)中的R是否合適.因?yàn)榇嬖谝粋€(gè)與R相關(guān)的正則化參數(shù)α，使得(6)與(8)等價(jià)，所以確定一個(gè)恰當(dāng)?shù)腞，需要檢驗(yàn)與之對(duì)應(yīng)的正則化參數(shù)α取值是否正確.通過引理1與引理2，只知道α是一個(gè)分段線性、連續(xù)、關(guān)于R的遞減函數(shù)，并且α與R之間沒有顯式公式，所以不能直接從R的值得到α的取值，因此無法確定R是否正確.

另一種方法是考慮Morozov偏差原則.對(duì)于任意給定的R，可以檢驗(yàn)正則化參數(shù)α是否滿足定義3，即

算法3 (在Morozov偏差原則下，問題(4)的投影梯度算法)

(1)選擇x0∈Rn，R0∈R+，并且設(shè)j=0，

k=0.

(2)如果xk=0，那么

(3)否則，確定下降方向zk，使其滿足

(4)確定步長(zhǎng)sk，使其滿足

(5)令xk+1=xk+sk(zk-xk),k=k+1.

(6)如果xk滿足Morozov偏差原則(定義3)，設(shè)Rj+1=Rj+c,c>1，否則停止迭代.

(7)j=j+1，返回第三步.

最后在Rn中考慮算法3的穩(wěn)定性.

即

(12)

4 結(jié)論

該文針對(duì)非線性不適定問題，研究了αl1-βl2,α≥β≥0型罰項(xiàng)的非凸稀疏正則化問題：

α‖x‖l1-β‖x‖l2.