(長江大學(xué)信息與數(shù)學(xué)學(xué)院，湖北 荊州 434023)

稀疏重構(gòu)模型在圖像處理、機(jī)器學(xué)習(xí)、統(tǒng)計學(xué)中有著廣泛的應(yīng)用，其研究的主要內(nèi)容為尋找欠定線性方程組Ax=y的稀疏解x[1]。其模型描述如下：

(1)

式中：A∈Rm×n；y∈Rm；x∈Rn且m

分割Bregman迭代算法是Osher等在研究圖像去噪時提出的一種高效的迭代方法[2]，該算法只需要利用目標(biāo)函數(shù)的一階導(dǎo)數(shù)信息，適用于大規(guī)模計算，被廣泛的應(yīng)用于圖像去噪、圖像去模糊等圖像領(lǐng)域[3,4]。但這類方法僅具有線性收斂速率，在實際應(yīng)用中求解速度較慢，這也就成為制約迭代算法應(yīng)用的瓶頸。

1 算法步驟

Bregman迭代算法求解問題(1)的主要步驟如下：通過引入一個輔助變量z=x，將式(1)轉(zhuǎn)化為：

s.tz=x

(2)

將其進(jìn)一步化為非約束優(yōu)化問題：

(3)

式中：μ>0，且為一個常數(shù)。

(4)

可以直接利用文獻(xiàn)[3]和[4]中給出的Bregman迭代算法來求解問題(4)，算法主要步驟如下：

(5)

式(5)中的第1個最小化問題可以分別對2個子問題xk+1和zk+1進(jìn)行優(yōu)化，即：

(6)

對子問題xk+1的求解可采用多種方法。當(dāng)問題規(guī)模不大時，對式(6)第1個式子的x進(jìn)行求導(dǎo)并令導(dǎo)數(shù)等于0，可得：

(λATA+μI)x=λATy+μ(zk-bk)

(7)

此時可以直接得到x精確的解析解：

xk+1=(λATA+μI)-1(λATy+μ(zk-bk))

(8)

式(8)中涉及到求逆運(yùn)算，計算復(fù)雜度較高。

當(dāng)問題規(guī)模較大時，矩陣求逆將耗費(fèi)大量時間。此時可以采用Gauss-seidel法、傅里葉變換及共軛梯度法等得到式(6)的迭代解[4，12～15]。筆者采用梯度下降法得到x的近似解，x可以通過如下迭代得到：

xk+1=xk-τ▽J(xk)

式中：▽J(xk)=λAT(Axk-y)-μ(zk-xk-bk)是目標(biāo)函數(shù)在xk處的梯度。

子問題zk+1是一個稍微復(fù)雜的組合性問題，可直接利用收縮算子(軟閾值)法[16]得到最優(yōu)解，其表達(dá)式如下：

(9)

式中:

(10)

式(6)第2個式子是直接對b進(jìn)行更新，將Nesterov加速梯度機(jī)制應(yīng)用到b的更新上，得到新的b的迭代過程如下：

(11)

綜合式(7)～(11)，加速分割Bregman迭代算法步驟如下：

輸入：A,y;

當(dāng)“不滿足收斂性條件”，重復(fù)執(zhí)行:

①根據(jù)式(7)或式(8)更新x;

②根據(jù)式(9)更新z;

⑥k=k+1;

⑦輸出x。

2 仿真試驗

將提出的加速分割Bregman迭代算法利用Matlab編程實現(xiàn)，并分別在無噪聲和有噪聲條件下驗證算法的有效性。為更好地展現(xiàn)加速分割Bregman迭代算法的加速性能，還將該算法與未加速的分割Bregman迭代算法和線性Bregman迭代算法進(jìn)行比較，同時也與目前已有的加速算法——加速線性Bregman迭代算法[8]進(jìn)行比較。試驗中，模型的各個參數(shù)選擇如下：稀疏信號x的長度n=1000，其稀疏度(非零元的個數(shù))k=100，稀疏元的位置隨機(jī)均勻選取，稀疏元的大小分2種情況選?。孩匐S機(jī)選取為1或者-1；②服從標(biāo)準(zhǔn)正態(tài)分布。觀測矩陣A由如下方式產(chǎn)生：首先生成一個500×1000的隨機(jī)矩陣，然后將矩陣的每一列規(guī)范化，使矩陣的每一列的范數(shù)為1。

觀測信號y由y=Ax+n得到，其中n為服從標(biāo)準(zhǔn)正態(tài)分布N(0,σ2)的高斯白噪聲，試驗中取σ=0.1。

圖1 算法重構(gòu)性能比較

圖1展示了當(dāng)稀疏信號的大小隨機(jī)選取為1或者-1以及服從標(biāo)準(zhǔn)正態(tài)分布時4種算法的重構(gòu)性能。從圖1(a)可以看出，線性Bregman迭代算法和分割Bregman迭代算法大約需要70次以上的迭代才能使得重構(gòu)的相對誤差達(dá)到指定精度；加速線性Bregman迭代算法所需的迭代次數(shù)大約在40次左右，加速分割Bregman迭代算法所需的迭代次數(shù)大約在30次左右，經(jīng)過加速后算法的迭代次數(shù)約是不加速算法的一半，加速效果明顯。加速分割Bregman迭代算法只需要30次左右的迭代即可達(dá)到所需精度，是所有算法中所需的迭代次數(shù)最少的。從圖1(b)可以看出，此時各個算法所需的迭代次數(shù)較第1種情況均有較大的上升，但總體趨勢并沒有較大變化，加速分割Bregman迭代算法只需要120次左右的迭代，遠(yuǎn)低于其他3種算法。

3 結(jié)語