汪麗琴，喻高航，張亮亮

(杭州電子科技大學理學院，浙江 杭州 310018)

0 引 言

1 低秩矩陣填充模型

(1)

式中，δ表示對Z的秩的假設(shè)置信度，通常取某個正整數(shù)。模型(1)綜合考慮了無噪音和有噪音的情況。由于秩函數(shù)是非凸且非連續(xù)的，計算模型(1)十分困難。Fazel[5]證明核范數(shù)在單元球上是秩的最緊凸松弛替代，隨后，Candès和Recht[6]提出使用矩陣核范數(shù)代替秩來解矩陣填充問題，得到模型：

(2)

2 Frank-Wolfe算法

(3)

給出Frank-Wolfe算法。

算法1 用于解決問題(3)的標準Frank-Wolfe算法輸入:x0∈,最大迭代步數(shù)K 當k=1,2,…,K時,(1)計算sk-1=argmins∈(2)搜索方向dfw=sk-1-xk-1(3)更新xk=xk-1+γdfw,其中γ∈[0,1]輸出:xK

針對步驟3中步長的選取，本文使用精確線搜索策略，即γ=argminγ∈[0,1]f(xk+γdfw)。

由于核范數(shù)的對偶范數(shù)是算子范數(shù)，即‖Y‖=max‖X‖*≤1〈X,Y〉，因此最優(yōu)化問題

minX〈X,Y〉 s.t.‖X‖*≤1

2.1 CGS算法

Lan等[8]使用Nesterov加速方法，提出FW算法的改進算法CGS。

算法2 FW算法的變體CGS算法輸入:x0∈,最大迭代步數(shù)K 取βk∈R++,γk∈[0,1],和ηk∈R+,k=1,2,…,令y0=x0 當k=1,2,…,K時,(1)計算zk=(1-γk)yk-1+γkxk-1(2)計算xk=CndG f'(zk),xk-1,βk,ηk (3)更新yk=(1-γk)yk-1+γkxk輸出:yK 子程序xk=CndG f'(zk),xk-1,βk,ηk 的步驟如下:(1)初始化g=f'(zk),u=xk-1,β=βk,η=ηk(2)令u1=u和t=1(3)令vt為子問題Vg,u,β(ut)maxx∈的最優(yōu)解(4)如果Vg,u,β(ut)≤η,則令xk=ut,并跳轉(zhuǎn)到步驟7,否則,進入步驟5(5)令ut+1=(1-αt)ut+αtυt,其中αt=min1,<β(u-ut)-g,υt-ut>β‖υt-ut‖2 (6)令t=t+1,并跳轉(zhuǎn)到步驟3(7)返回xk

2.2 In-Face步驟

對于矩陣填充問題，F(xiàn)W算法的一個不足之處在于其中間解決方案的秩通常穩(wěn)定增長，并在終止時產(chǎn)生一個高秩的解決方案，這對于大規(guī)模問題[13]可能在時間和空間成本上非常昂貴。

隨后，F(xiàn)reund等[9]提出加In-Face步驟的拓展FW算法IF-(0,∞)，In-Face步驟是遠離步驟的推廣，遠離步驟的具體細節(jié)見文獻[14-15]。In-Face步驟沿著包含當前迭代的最小面選擇最佳下降方向，通過沿著最小面移動到可行域的邊界以達到低維面。該算法保持了低秩結(jié)構(gòu)，且不會影響收斂。對于問題(2)，如文獻[9]所述，包含點Xk核范數(shù)球NN(0,δ)的最小面由下列集合給出：

其中，Xk具有秩為r的薄SVDUΣVT，M為滿足tr(M)=δ的半正定矩陣。薄SVD表示具有嚴格正奇異值的SVD，即，如果A=UΣVT是薄SVD且rank(A)=r，則U∈Rm×r，Σ∈Rr×r，V∈Rn×r。

本文考慮文獻[9]中描述的由遠離策略得到的In-Face步驟，它使用的方向如下：

3 自適應(yīng)FW算法及其收斂性分析

為了提高FW算法的收斂率并降低迭代過程中的計算成本，本文提出嵌入秩下降步驟的矩陣填充問題的IF-CGS算法。

算法3 IF-CGS算法輸入:初始迭代點x0∈,超參數(shù)c>0,最大迭代步數(shù)K 取βk∈R++,γk∈[0,1],和ηk∈R+,k=1,2,…,令y0=x0 當k=1,2,…,K時,(1)當yk-1在NN(0,δ-c)內(nèi)部時,計算CGS:zk=(1-γk)yk-1+γkxk-1xk=CndG f'(zk),xk-1,βk,ηk yk=(1-γk)yk-1+γkxk(2)當yk-1在NN(0,δ-c)外部時,計算遠離方向滿足yk-1+dk∈Aff D(yk-1) 和?f(yk-1)Tdk<0如果dk不存在,則跳轉(zhuǎn)到步驟1,計算CGS,否則,進入步驟3(3)αstopk=argmaxα{α︰yk-1+αdk∈D(yk-1)}yAk-1yk-1+αstopkdk(4)如果f(yAk-1)≤f(yk-1),則進入步驟5,否則,跳轉(zhuǎn)到步驟1(5)更新yk=yAk-1輸出:yK

步驟1進行CGS計算，當秩增長到一定程度時執(zhí)行步驟2，計算In-Face步驟下的迭代點更新，并在In-Face步驟和CGS步驟進行選擇，若In-Face步驟下的目標值小于上一次迭代的目標值，則執(zhí)行In-Face步驟，否則執(zhí)行CGS步驟。在加In-Face步驟的CGS算法的框架下，接受任何不增加目標函數(shù)值的降秩步驟，允許算法維持較低秩的SVD，并且允許算法跳過不必要的CGS計算。

對{βk}，{γk}和{ηk}提供一種參數(shù)設(shè)置，得到其收斂性結(jié)果。

定理1如果IF-CGS算法中的參數(shù){βk}，{γk}和{ηk}設(shè)置如下：

證明當下一個迭代點由步驟1選取，則有

4 數(shù)值實驗與分析

分別使用FW，IF-(0,∞)，CGS，IF-CGS算法進行數(shù)值實驗，從數(shù)據(jù)恢復精度和運行時間進行性能分析。

4.1 合成數(shù)據(jù)

表1 中大型規(guī)模合成數(shù)據(jù)的參數(shù)設(shè)置

抽取觀察數(shù)據(jù)的50%作為訓練集，剩下的50%作測試集，例1運行150 s，例2 運行250 s，例3 運行500 s，超參數(shù)c設(shè)置為0.5，使用目標值和測試均方根誤差(Root Mean Squared Error，RMSE)作為評估標準，用于衡量預測值與真實值之間的偏差，

實驗結(jié)果如圖1和圖2所示。

圖1 不同算法目標值隨運行時間變化的情況

圖2 不同算法測試RMSE隨運行時間變化的情況

從圖1和圖2可以看出，IF-CGS算法降低目標值和測試RMSE的速度比其他方法快，解的精度也高于其他方法。在初始迭代階段，IF-CGS算法迭代點在NN(0,δ-c)內(nèi)部執(zhí)行CGS計算，所以IF-CGS算法與CGS算法基本是同步的，當IF-CGS算法迭代點達到NN(0,δ-c)外部時，開始在In-Face步驟與CGS步驟中進行選擇，執(zhí)行In-Face步驟能夠減少迭代成本，所以，相比CGS算法，IF-CGS算法的收斂速度更快。

4.2 Movielens-10M數(shù)據(jù)集

表3 Movielens-10M數(shù)據(jù)集實驗中，不同算法的性能指標

5 結(jié)束語

Frank-Wolfe算法的變體CGS算法解矩陣填充問題的一個不足之處在于其中間解的秩通常會穩(wěn)定增長，并在終止時達到高秩的解。本文針對這個不足，嵌入秩下降步驟，提出求解低秩矩陣填充問題的IF-CGS算法。所提算法在保持線性收斂的同時減少迭代成本，有效解決了大規(guī)模的低秩矩陣填充問題。但是，In-Face步驟確定最大可行步長時需要進行多次SVD更新，導致昂貴的中間迭代，針對秩下降步驟的選取問題展開進一步研究是有意義的。