一種求解稀疏重構問題的加速分割Bregman迭代算法

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

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

(1)

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

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

1 算法步驟

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

s.tz=x

(2)

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

(3)

式中：μ>0，且為一個常數。

(4)

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

(5)

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

(6)

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

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

(7)

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

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

(8)

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

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

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

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

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

(9)

式中:

(10)

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

(11)

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

輸入：A,y;

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

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

②根據式(9)更新z;

⑥k=k+1;

⑦輸出x。

2 仿真試驗

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

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

圖1 算法重構性能比較

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

3 結語