一種求解Lasso問(wèn)題的不精確鄰近梯度算法

謝秋玲, 徐宇淼, 胡清潔

(桂林電子科技大學(xué) 數(shù)學(xué)與計(jì)算科學(xué)學(xué)院,廣西 桂林 541004)

最小絕對(duì)值收縮和選擇算子(least absolute shrinkage and selection operator,簡(jiǎn)稱Lasso)問(wèn)題由Tibshirani[1]提出,即利用l1正則化項(xiàng)求解線性回歸問(wèn)題的稀疏解。Lasso問(wèn)題在稀疏規(guī)劃和信號(hào)處理領(lǐng)域起著非常重要的作用,其應(yīng)用包括稀疏信號(hào)修復(fù)、稀疏圖回歸、稀疏逆協(xié)方差、稀疏字典學(xué)習(xí)、圖像修復(fù)、圖像去噪和去模糊等[2]。因此,在理論和算法上深化和完善對(duì)該問(wèn)題的研究,具有重要的理論意義和廣泛的應(yīng)用前景。

Lasso問(wèn)題模型如下:

在利用鄰近梯度法求解問(wèn)題(1)時(shí),需計(jì)算鄰近算子[7]:在很多情況下,鄰近子問(wèn)題(2)無(wú)解析解或者精確求解的計(jì)算量較大,需考慮近似求解鄰近算子。鑒于此,提出了一種帶有鄰近算子誤差和梯度計(jì)算誤差的不精確鄰近梯度算法,并給出該算法的收斂速度分析和相應(yīng)的數(shù)值實(shí)驗(yàn)。

1 不精確鄰近梯度算法

與文獻(xiàn)[5]中提出的FISTA-BKTR 算法相比,為了加速收斂,本算法在步驟5)中計(jì)算不精確鄰近算子,即考慮在問(wèn)題(1)中光滑項(xiàng)梯度計(jì)算和求解鄰近子問(wèn)題時(shí)存在誤差。

根據(jù)算法中的步驟2),若選擇的μ-k、μ0k分別滿足μ0>1/L(f)、μk≥μk-1,則對(duì)?k,有μk≥β/L(f)。若μ0>1/L(f),因此有

2 算法的有關(guān)性質(zhì)

性質(zhì)1[7]若

引理3 若對(duì)任意的y∈Rn,μ>0,使得

類似于文獻(xiàn)[7],可得如下關(guān)于不精確鄰近梯度算法的2個(gè)關(guān)鍵引理。

引理5 若假設(shè)算法中滿足

3 收斂速度分析

為了得到形如

定理1 若上述假設(shè)成立,則在算法的第k次迭代中,

其中,

即

由引理6可得

其中:

從而定理得證。

4 數(shù)值實(shí)驗(yàn)

分別用FISTA[4](加速鄰近梯度算法)、INEXACT FISTA (不精確加速鄰近梯度算法)、RS-FISTA[8](重啟的加速鄰近梯度法)、FISTA-BKTR(線搜索加速鄰近梯度算法)、INEXACT FISTA-BKTR[5](不精確線搜索加速鄰近梯度算法)求解Lasso問(wèn)題,全部數(shù)值實(shí)驗(yàn)使用MATLAB語(yǔ)言編程,并在MATLAB R2016a中運(yùn)行,測(cè)試環(huán)境為Window 7操作系統(tǒng),Inter(R)Core(TM)i5-6500 CPU@3.20 GHz、8.00 GiB RAM。

在INEXACT FISTA 及INEXACT FISTABKTR算法中利用RCD[10](隨機(jī)坐標(biāo)下降算法)求解不精確鄰近算子,即滿足式(3)。然而,在這2種算法中,使用了文獻(xiàn)[10]提出的內(nèi)部停止條件,該停止條件保證了不精確算法可以達(dá)到快速局部收斂。梯度誤差為e k=(0.001)k e,其中e=(1,0,…,0)T。經(jīng)測(cè)試,將最高的迭代次數(shù)設(shè)置為500次。在問(wèn)題(1)中,數(shù)據(jù)生成方法如下:

2)b∶=Ax++N(0,10-3),其中x+為利用標(biāo)準(zhǔn)高斯分布生成的s-稀疏向量。

令p=200,n=350,s=100,ρ=0.1。算法運(yùn)行結(jié)果如圖1、2和表1所示。

表1 算法比較結(jié)果

圖1 5種算法目標(biāo)函數(shù)值相對(duì)誤差變化圖

由上述實(shí)驗(yàn)結(jié)果可知,FISTA 和INEXACT FISTA算法在停止迭代時(shí),INEXACT FISTA 得到的誤差更小。FISTA-BKTR 和INEXACT FISTABKTR算法在滿足停止條件時(shí),INEXACT FISTABKTR所需的迭代次數(shù)更少。因此,與FISTA、FIS TA-BKTR相比,帶有不精確鄰近算子的INEXACT FISTA 和INEXACT FISTA-BKTR 的結(jié)果較好。通過(guò)對(duì)比可知,求解Lasso問(wèn)題時(shí),在相同條件下達(dá)到停止條件,INEXACT FISTA-BKTR 所需的迭代次數(shù)最少。

圖2 5種算法迭代序列相對(duì)誤差變化圖

5 結(jié)束語(yǔ)

提出了求解Lasso問(wèn)題的帶完全回溯技術(shù)的不精確鄰近梯度算法?？紤]在鄰近梯度法中光滑項(xiàng)梯度及鄰近算子的計(jì)算存在誤差,證明了如果這些誤差以適當(dāng)?shù)乃俣认陆?不精確鄰近梯度法可達(dá)到與無(wú)誤差時(shí)的收斂速度一致,即該算法具有O(1/k2)的收斂速度。數(shù)值實(shí)驗(yàn)表明,不精確鄰近算法求解Lasso問(wèn)題是有效的。