閆喜紅，任曉嶸

(太原師范學(xué)院 數(shù)學(xué)系，山西 晉中 030619)

0 引言

矩陣填充在機器學(xué)習(xí)[1-5]、信號處理[6-7]、多標簽分類[8-10]等領(lǐng)域發(fā)揮著重要的作用，是近幾年研究的熱點之一.在現(xiàn)實生活中，我們面臨的許多問題的數(shù)據(jù)都是以矩陣的形式呈現(xiàn)的，但由于種種原因，我們常常面臨某個矩陣無法得到全部元素值的問題.如何合理、準確地對這些缺失數(shù)據(jù)進行填充即為矩陣填充.如果不加其他的約束，僅由部分少量的矩陣元素來恢復(fù)出整個矩陣，則矩陣填充是一個非適定性問題.然而事實上眾多實際問題中的數(shù)據(jù)之間往往存在著某種關(guān)聯(lián)性，使需要填充的矩陣具有低秩或近似低秩結(jié)構(gòu).為此，矩陣填充模型為:

s.t.PΩ(Z)=PΩ(Z0)

(1)

其中Z∈Rm×n，Z0∈Rm×n且Z0是采樣矩陣，Ω為已知的樣本元素下標集，并且PΩ為Ω的正交投影.由于秩函數(shù)的非凸性，模型(1)是非凸規(guī)劃，這通常是一個NP-Hard問題.最廣泛研究的方法之一是根據(jù)矩陣的秩與非零奇異值的個數(shù)相同將秩函數(shù)凸松弛到核范數(shù)，該研究方法由Candès和Recht首次提出[11]，將問題(1)轉(zhuǎn)化為如下優(yōu)化問題：

s.t.PΩ(Z)=PΩ(Z0)

(2)

其中‖Z‖*表示矩陣Z的核范數(shù)，是奇異值的和.基于凸模型(1)，目前已有很多算法[12]，例如SDPT[13]、SeDumi[14]、奇異值閾值算法[15](Singular Value Thresholding 簡稱：SVT)，增廣拉格朗日乘子法[16](Augmented Lagrange Multiplier簡稱：ALM)，加速近端梯度算法[17](Accelerated Proximal Gradient 簡稱：APG)等.但這些算法的實現(xiàn)需要在每次迭代中計算部分奇異值分解(SVD)，SVD計算量非常大，因此這些算法不適用于求解大規(guī)模矩陣填充問題.為了避免SVD的高計算量，Haldar[18]和Wen[19]提出如下分解模型:

(3)

其中，Z=XY，X∈Rm×r，Y∈Rr×n，確保滿足低秩要求.求解非凸模型(3)有許多算法，主要思想是基于低秩矩陣分解[20]，由于該類算法不需要奇異值分解SVD，因此在求解大型矩陣填充問題是非常有效的.Jared[21]提出的交替最速下降法(ASD)和改進的交替最速下降法(SCASD)就屬于該類算法，能有效求解上述模型.但ASD算法和SCASD算法在每一步都需要計算精確步長，計算量較大，因而采用非精確的BB步長法進行改進，降低計算量，最后給出數(shù)值實驗證明新算法的可行性和有效性.

文章結(jié)構(gòu)如下：在第1節(jié)中介紹預(yù)備知識；第2節(jié)提出并詳細介紹一種帶有BB步長的交替最速下降算法(BB-ASD和BB-SCASD)；第3節(jié)將提出的BB-ASD算法和ASD進行了數(shù)值實驗，并進行了比較，驗證了交替帶有BB步長的最速下降算法的有效性.

1 預(yù)備知識

本節(jié)介紹相關(guān)工作，首先對模型(2)的下降方向及其相應(yīng)的步長進行介紹，然后對BB步長進行簡單的介紹，最后介紹文獻[21]中兩個相關(guān)的算法.

1.1 下降方向及其相應(yīng)的步長

模型(2)是一個二次規(guī)劃問題，其針對X和Y的梯度方向和步長分別為

?fY(X)=-(PΩ(Z0)-PΩ(XY))YΤ，?fX(Y)=-XΤ(PΩ(Z0)-PΩ(XY))，

1.2 BB步長法

隨著Barzilai-Borwein(BB)步長法的出現(xiàn)，無約束優(yōu)化問題越來越受到研究者的重視.它被廣泛應(yīng)用于各個領(lǐng)域.BB法的基本思想是在計算當(dāng)前迭代步長時充分利用前一步信息，使矩陣在最小二乘的意義下滿足擬牛頓關(guān)系式，從而達到較好地逼近目標函數(shù)在xk點的Hesse矩陣?2f(xk)的效果.其格式為：

其中sk-1=xk-xk-1，yk-1=?f(xk)-?f(xk-1).BB法對嚴格凸二次函數(shù)的全局收斂性已經(jīng)被證明.雖然BB步長不能保證目標函數(shù)在每一個迭代步都是單調(diào)下降的，但是其計算效果較好.

1.3 相關(guān)算法介紹

為了便于后續(xù)改進，在此對文獻[21]中的交替最速下降法(ASD)和改進交替最速下降法(SCASD)進行相關(guān)介紹.交替最速下降法(ASD)對(2)中關(guān)于X和Y進行最速梯度下降，即將1.1提出的下降方向和步長應(yīng)用到該方法中.

算法1交替最速下降法(ASD)

步1：給定初始矩陣PΩ(Z0)，X0∈Rm×r，Y0∈Rr×n；

步2：重復(fù)計算以下步驟：

Xi+1=Xi-txi?fYi(Xi)，

接下來將介紹算法1的改進版本.在上述算法中，X和Y的梯度下降方向是最速下降方向.眾所周知，牛頓方向比最速下降方向更有效，因此在文獻[21]中對上述算法進行了改進，選擇了牛頓方向(Z0-XY)YΤ(YYΤ)-1和(XΤX)-1XΤ(Z0-XY)作為X和Y的梯度方向.具體計算步驟如下：

算法2改進交替最速下降法(SCASD)

步1：給定初始矩陣PΩ(Z0)，X0∈Rm×r，Y0∈Rr×n；

步2：重復(fù)計算以下步驟：

Xi+1=Xi+txidxi，

Yi+1=Yi+tyidyi；

2 一種帶有BB步長的交替下降法

由于ASD算法和SCASD算法在每一步都需要計算精確步長，計算量較大，我們也知道在優(yōu)化中BB步長效果很好，所以針對算法1和算法2加入BB步長得到算法3和算法4.

算法3BB-ASD算法

步1：給定初始矩陣PΩ(Z0),X0∈Rm×r，Y0∈Rr×n；

X1=X0-tx0?fY0(X0)，

Y1=Y0-tY0?fX1(Y0)，

步3：重復(fù)計算以下步驟：

?fYi(Xi)=-(PΩ(Z0)-PΩ(XiYi))YiΤ，

xk=Xk(:)，?fYi(xk)=?fYi(Xk)(:)，

Xi+1=Xi-txi?fYi(Xi)，

yk=Yk(:)，?fXi(yk)=?fXi(Yk)(:)，

Yi+1=Yi-tyi?fXi+1(Yi)，

算法4BB-SCASD算法

步1：給定初始矩陣PΩ(Z0)，X0∈Rm×r，Y0∈Rr×n；

本文探討了濕熱處理對不同直鏈淀粉含量大米淀粉消化性能及鏈結(jié)構(gòu)、層狀結(jié)構(gòu)、結(jié)晶結(jié)構(gòu)、螺旋結(jié)構(gòu)等多尺度結(jié)構(gòu)變化的影響。研究發(fā)現(xiàn)濕熱處理對淀粉結(jié)構(gòu)有一定的破壞作用，使得分子鏈發(fā)生斷裂，淀粉的雙螺旋含量減少，結(jié)晶度降低，且直鏈淀粉含量越低的淀粉抵抗?jié)駸崽幚砥茐淖饔玫哪芰υ饺酢Ｍ瑫r，濕熱處理可促進分子間的取向重排，形成新的單螺旋結(jié)構(gòu)，提高了淀粉顆粒的穩(wěn)定性，從而增強大米淀粉淀粉的慢消化和抗消化性能。本研究的結(jié)果為加工獲得不同消化性能的新型淀粉基食品提供理論指導(dǎo)。

步2：求?fY0(X0)=-(PΩ(Z0)-PΩ(X0Y0))Y0Τ，

X1=X0+tx0dx0，

Y1=Y0+ty0dy0；

?fYi(Xi)=-(PΩ(Z0)-PΩ(XiYi))YiΤ，

dxi=-?fYi(Xi)(YiYiΤ)-1，

xk=Xk(:)，?fYi(xk)=?fYi(Xk)(:)，

Xi+1=Xi+txidxi,

yk=Yk(:)，?fXi(yk)=?fXi(Yk)(:)，

Yi+1=Yi+tyidyi,

XK(:)表示矩陣XK對應(yīng)的列向量，即將矩陣XK中的每一列都按列依次排開.

3 數(shù)值實驗

由于BB-ASD與BB-SCASD數(shù)值結(jié)果相同，因此在本節(jié)中，只展示了BB-ASD與ASD的數(shù)值比較.通過數(shù)值實驗比較BB-ASD算法和ASD算法，這里所有的數(shù)值實驗均是在MATLAB(R2013a)中進行的，且機器精度為10-64，機器類型為英特爾核2.4GB.本實驗中最大次數(shù)是3 000，精度是10-4.在相同的環(huán)境下，矩陣是隨機產(chǎn)生的，矩陣的維數(shù)從100到1 000，秩是從10到30，具體實驗結(jié)果見表1.

表1 算法BB-ASD和算法ASD的比較

從表1中可以看出，BB-ASD對大部分問題來說，迭代次數(shù)更少，尤其是對大規(guī)模問題來說，但時間會長一些，其原因可能是過程中需要的每一步的計算時間更長.

4 結(jié)論

我們提出了一種求解矩陣填充問題的帶有BB步長的下降法，針對矩陣填充這個研究熱點，提出了一種交替帶有BB步長的最速下降算法，并把此算法應(yīng)用到隨機產(chǎn)生的低秩矩陣填充問題中.由于一般矩陣填充的ASD算法在每一步都需要計算精確的步長，計算量較大，所以采用非精確的BB步長法進行改進，降低計算量.通過數(shù)值實驗也驗證了算法的可行性和有效性，尤其是對于大規(guī)模問題，迭代次數(shù)大幅減少.