一种求解矩阵填充问题的带有BB步长的交替下降法

闫喜红，任晓嵘

(太原师范学院 数学系，山西 晋中 030619)

0 引言

矩阵填充在机器学习[1-5]、信号处理[6-7]、多标签分类[8-10]等领域发挥着重要的作用，是近几年研究的热点之一.在现实生活中，我们面临的许多问题的数据都是以矩阵的形式呈现的，但由于种种原因，我们常常面临某个矩阵无法得到全部元素值的问题.如何合理、准确地对这些缺失数据进行填充即为矩阵填充.如果不加其他的约束，仅由部分少量的矩阵元素来恢复出整个矩阵，则矩阵填充是一个非适定性问题.然而事实上众多实际问题中的数据之间往往存在着某种关联性，使需要填充的矩阵具有低秩或近似低秩结构.为此，矩阵填充模型为:

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

(1)

其中Z∈Rm×n，Z0∈Rm×n且Z0是采样矩阵，Ω为已知的样本元素下标集，并且PΩ为Ω的正交投影.由于秩函数的非凸性，模型(1)是非凸规划，这通常是一个NP-Hard问题.最广泛研究的方法之一是根据矩阵的秩与非零奇异值的个数相同将秩函数凸松弛到核范数，该研究方法由Candès和Recht首次提出[11]，将问题(1)转化为如下优化问题：

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

(2)

其中‖Z‖*表示矩阵Z的核范数，是奇异值的和.基于凸模型(1)，目前已有很多算法[12]，例如SDPT[13]、SeDumi[14]、奇异值阈值算法[15](Singular Value Thresholding 简称：SVT)，增广拉格朗日乘子法[16](Augmented Lagrange Multiplier简称：ALM)，加速近端梯度算法[17](Accelerated Proximal Gradient 简称：APG)等.但这些算法的实现需要在每次迭代中计算部分奇异值分解(SVD)，SVD计算量非常大，因此这些算法不适用于求解大规模矩阵填充问题.为了避免SVD的高计算量，Haldar[18]和Wen[19]提出如下分解模型:

(3)

其中，Z=XY，X∈Rm×r，Y∈Rr×n，确保满足低秩要求.求解非凸模型(3)有许多算法，主要思想是基于低秩矩阵分解[20]，由于该类算法不需要奇异值分解SVD，因此在求解大型矩阵填充问题是非常有效的.Jared[21]提出的交替最速下降法(ASD)和改进的交替最速下降法(SCASD)就属于该类算法，能有效求解上述模型.但ASD算法和SCASD算法在每一步都需要计算精确步长，计算量较大，因而采用非精确的BB步长法进行改进，降低计算量，最后给出数值实验证明新算法的可行性和有效性.

文章结构如下：在第1节中介绍预备知识；第2节提出并详细介绍一种带有BB步长的交替最速下降算法(BB-ASD和BB-SCASD)；第3节将提出的BB-ASD算法和ASD进行了数值实验，并进行了比较，验证了交替带有BB步长的最速下降算法的有效性.

1 预备知识

本节介绍相关工作，首先对模型(2)的下降方向及其相应的步长进行介绍，然后对BB步长进行简单的介绍，最后介绍文献[21]中两个相关的算法.

1.1 下降方向及其相应的步长

模型(2)是一个二次规划问题，其针对X和Y的梯度方向和步长分别为

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

1.2 BB步长法

随着Barzilai-Borwein(BB)步长法的出现，无约束优化问题越来越受到研究者的重视.它被广泛应用于各个领域.BB法的基本思想是在计算当前迭代步长时充分利用前一步信息，使矩阵在最小二乘的意义下满足拟牛顿关系式，从而达到较好地逼近目标函数在xk点的Hesse矩阵∇2f(xk)的效果.其格式为：

其中sk-1=xk-xk-1，yk-1=∇f(xk)-∇f(xk-1).BB法对严格凸二次函数的全局收敛性已经被证明.虽然BB步长不能保证目标函数在每一个迭代步都是单调下降的，但是其计算效果较好.

1.3 相关算法介绍

为了便于后续改进，在此对文献[21]中的交替最速下降法(ASD)和改进交替最速下降法(SCASD)进行相关介绍.交替最速下降法(ASD)对(2)中关于X和Y进行最速梯度下降，即将1.1提出的下降方向和步长应用到该方法中.

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

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

步2：重复计算以下步骤：

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：重复计算以下步骤：

Xi+1=Xi+txidxi，

Yi+1=Yi+tyidyi；

2 一种带有BB步长的交替下降法

由于ASD算法和SCASD算法在每一步都需要计算精确步长，计算量较大，我们也知道在优化中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：重复计算以下步骤：

∇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；

本文探讨了湿热处理对不同直链淀粉含量大米淀粉消化性能及链结构、层状结构、结晶结构、螺旋结构等多尺度结构变化的影响。研究发现湿热处理对淀粉结构有一定的破坏作用，使得分子链发生断裂，淀粉的双螺旋含量减少，结晶度降低，且直链淀粉含量越低的淀粉抵抗湿热处理破坏作用的能力越弱。同时，湿热处理可促进分子间的取向重排，形成新的单螺旋结构，提高了淀粉颗粒的稳定性，从而增强大米淀粉淀粉的慢消化和抗消化性能。本研究的结果为加工获得不同消化性能的新型淀粉基食品提供理论指导。

步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对应的列向量，即将矩阵XK中的每一列都按列依次排开.

3 数值实验

由于BB-ASD与BB-SCASD数值结果相同，因此在本节中，只展示了BB-ASD与ASD的数值比较.通过数值实验比较BB-ASD算法和ASD算法，这里所有的数值实验均是在MATLAB(R2013a)中进行的，且机器精度为10-64，机器类型为英特尔核2.4GB.本实验中最大次数是3 000，精度是10-4.在相同的环境下，矩阵是随机产生的，矩阵的维数从100到1 000，秩是从10到30，具体实验结果见表1.

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

从表1中可以看出，BB-ASD对大部分问题来说，迭代次数更少，尤其是对大规模问题来说，但时间会长一些，其原因可能是过程中需要的每一步的计算时间更长.

4 结论

我们提出了一种求解矩阵填充问题的带有BB步长的下降法，针对矩阵填充这个研究热点，提出了一种交替带有BB步长的最速下降算法，并把此算法应用到随机产生的低秩矩阵填充问题中.由于一般矩阵填充的ASD算法在每一步都需要计算精确的步长，计算量较大，所以采用非精确的BB步长法进行改进，降低计算量.通过数值实验也验证了算法的可行性和有效性，尤其是对于大规模问题，迭代次数大幅减少.