求解大型線性方程組的帶動量貪婪隨機Kaczmarz方法

王 雨 晴

(東華理工大學理學院，330013，南昌)

0 引言

機器學習、人工智能、信號處理和數據分析等眾多工程應用中常常需要求解大型相容線性方程組

Ax=b，

(1)

其中系數矩陣A∈m×n，b∈m和未知向量x∈n。Kaczmarz方法[1]是求解大型線性方程組(1)的一個經典行啟發式方法[2]，該方法由Kaczmarz在1937年提出。Kaczmarz方法在理論、應用和算法推廣都有很多進展，具體參閱文[3]及其參考文獻。2009年，Strohmer和Vershynin[4]引入隨機技術，提出了隨機Kaczmarz(RK)方法，并證明RK方法具有線性收斂速率。此工作使得RK方法成為數值代數領域的研究熱點。RK方法重新引起了人們對求解大型線性方程組(1)Kaczmarz類方法的興趣，提出了很多改進方法，具體內容參閱文獻[5-14]及其相關文獻。最近，基于一種不同但更有效的概率準則，白和巫[15]提出了求解大型線性方程組(1)的貪婪隨機Kaczmarz(GRK)方法。理論分析和數值結果表明，GRK方法的收斂速度快于RK方法。使用不同的概率準則，白和巫[16]建立了一類松弛貪婪隨機Kaczmarz方法，張[17]發展了一個新的貪婪Kaczmarz方法。

Heavy-Ball型動量方法是加速梯度類型方法收斂速率的經典技術，該方法最早由Polyak[18]提出。眾多研究人員對Heavy-Ball型動量方法進行了拓展研究，詳見文獻[19-20]。與Heavy-Ball型動量方法相比，Heavy-Ball型動量方法的隨機變形在理論開發工作較少，例如在深度學習[21]中得到廣泛應用的帶動量隨機梯度下降法(mSGD)。通過選擇適當的sketch矩陣，RK方法可以看成SGD方法的一種特例[8]。受文獻[18,22-23]的啟發，本文結合隨機逼近和Heavy-Ball型動量技術，構造了帶動量的GRK方法(mGRK)。理論上證明了mGRK方法的全局線性收斂結果。數值實驗進一步表明mGRK方法求解大型線性方程(1)時比GRK方法收斂性能更優。

本文結構安排如下：第1節建立mGRK方法并研究其線性收斂理論；第2節通過一些數值算例來驗證mGRK方法的有效性；第3節總結全文。

1 帶動量貪婪隨機Kaczmarz方法

通過引入動量項γ(xk-xk-1)，Polyak[18]提出了帶有動量的梯度下降法(mGD)，該方法也被稱為Heavy-Ball型動量方法，即

xk+1=xk-αk?f(xk)+γ(xk-xk-1)，

(2)

其中αk和γ分別表示步長和動量權重系數，?f(xk)表示目標函數的梯度。若令g表示梯度?f(xk)的無偏估計量，則可得到帶動量的隨機梯度下降方法(mSGD)

xk+1=xk-αkg(xk)+γ(xk-xk-1)

(3)

選擇適當的動量參數矩陣，mSGD方法可以退化為動量RK方法(mRK)。mRK方法的迭代形式為：

(4)

其中αk=1。

類似mRK方法，通過在GRK方法迭代步中嵌入動量項γ(xk-xk-1)，建立了帶動量的GRK方法(mGRK)。mGRK方法的偽代碼見算法1。易知，當參數β=0時mGRK方法退化為GRK方法。

算法1：mGRK算法。

輸入：A,b,l,x0,γ，fork=0,1,...,l-1do

計算：

(5)

確定指標集合：

(6)

end for。

下面給出mGRK方法的全局線性收斂性理論。在建立定理1之前，首先描述如下2個引理。

引理1(文獻[14]中的引理9)：令F1=F0≥0，且非負實數序列{Fk}k≥0滿足

Fk+1≤a1Fk+a2Fk-1，?k≥1，

(7)

q≥a1+a2，

(8)

當且僅當a2=0(q=a1，δ=0)等號成立。

引理2：設a,b,c∈n，則下列等式恒成立

證明：經簡單計算，易知

2〈a-c,c-b〉=2(a-c)*(c-b)=2a*c-2a*b+2c*b-2c*c

(9)

和

(10)

從而引理2得證。

(11)

證明：由算法1的迭代步驟7可以得到

(12)

下面分別考慮①，②和③3個式子。從式子①中可得

(13)

從式子③中可得

③

(14)

利用引理2，易計算

(15)

將式(15)代入式(14)中，可得

(16)

從式子②中，易推出

(17)

聯合式(13)、式(14)和式(17)，可得

(18)

結合不等式(18)，有

(19)

其中

經過簡單計算，易得以下不等式

〈?f(xk),xk-1-xk〉≤f(xk-1)-f(xk)。(20)

把式(20)代入式(19)可得

(21)

對f(xk)和f(xk-1)，可得

(22)

(23)

因此，聯合式(22)和式(23)，可得

(24)

Fk+1=a1Fk+a2Fk-1。

(25)

由式(24)，易知a2≥0和a1+a2<1。故結合式(25)和引理1，可得

綜上，定理1得證。

2 數值實驗

令右端向量b=Ax*，其中x*∈n由MATLAB函數randn隨機生成。測試矩陣為高斯矩陣或從Tim Davis稀疏矩陣集[24]選擇的實矩陣。設置中，mGRK方法中采用的動量參數β是通過實驗找到的最小化迭代步數的參數。GRK方法相對mGRK方法的加速度定義為：

高斯矩陣由MATLAB函數randn隨機生成，數值結果由表1和表2給出。

表1 A=randn(m,n)時，GRK方法和mGRK方法的數值實驗結果

表2 A=rand(m,n)時，GRK方法和mGRK方法的數值實驗結果

由表1和表2的數值結果，可得以下結論：1)GRK方法和mGRK方法求解相容線性方程組都是有效的；2)從迭代步驟和CPU時間看，mGRK方法均快于GRK方法，即增加動量項會給GRK方法的收斂特性帶來有效的改進；3)當m

從Tim Davis稀疏矩陣集[24]選擇12個具有代表性的系數矩陣，其矩陣性質見表3。相應數值結果見表4。

表3 12個實矩陣的性質

表4 A為實矩陣時，GRK方法和mGRK方法的數值實驗結果

從表4中的實驗結果可得GRK方法和mGRK方法呈現出與表1和表2中類似的數值結果。對矩陣Stranke94而言，mGRK方法在Speed-up方面取得最好的加速效果，加速值為6.75。除矩陣df2177、nemsafm、iiasa、Trec8和Stranke94外，在其他測試矩陣中動量參數β=0.3或β=0.4都是不錯的選擇。

3 總結

本文提出了求解大型相容線性方程組(1)的帶Heavy-Ball型動量的GRK方法，并研究了其收斂理論。數值結果表明，mGRK方法均優于GRK方法。針對實際問題，如何選擇最優且實用的動量參數，將另文進行研究。

致謝：感謝張建華導師的悉心指導下完成了理論推導、數值實驗等工作！