基于加权核范数的低秩矩阵补全算法研究

石莹， 黄华， 王智， 高超

1.西南大学 信息化建设办公室，重庆 400715；2.重庆工程职业技术学院，现代教育技术中心，重庆 402260；3.西南大学 计算机与信息科学学院，重庆 400715；4.西北工业大学 光电与智能研究院，西安 710072

在诸如协同过滤[1-2]、降维处理[3]、子空间聚类[4]、图像和信号处理[5-6]等机器学习或数据分析领域，人们通常需要求解如下优化问题

(1)

其中：M∈Rm×n为仅知道部分观察元素的待恢复矩阵，X∈Rm×n为目标矩阵，Ω表示已知的观察元素的位置，PΩ为正交投影算子，定义为

(2)

求解优化问题(1)的主要任务是寻找一个最小秩矩阵X*∈Rm×n，使其满足PΩ(X*)=PΩ(M)且使得秩函数rank(X)最小.利用正则化方法，问题(1)可等价地转换为如下非约束最小化问题

(3)

这里‖·‖F表示F范数，λ>0为正则化参数.

基于非凸正则化方法的优良性能，本文对基于加权核范数正则化模型进行进一步的分析和探讨，并借鉴Soft-Impute算法的思想提出一个拥有更快收敛速率和能够得到更高精度解的低秩矩阵补全算法.在本文提出WNNM-Impute(weighted nuclear norm minimization impute)算法的迭代过程中，需要进行费时的SVD分解.针对这一问题，通过引入不精确的近邻算子极大地降低WNNM-Impute算法的时间复杂度，从而使得算法收敛更快.同时，在算法中引入Nesterov加速策略，使得算法的总体迭代次数进一步减少.本文提出的算法基于Soft-Impute算法，但是实验结果表明，它比Soft-Impute算法收敛更快且得到的解的精度更高.因此，本文提出的算法适合用于求解大规模低秩矩阵补全问题.

1 基础知识

当使用核范数去松弛秩函数rank(X)时，数学上可将低秩矩阵补全问题建模为

(4)

这里‖X‖*表示核范数，定义为

(5)

其中r=min(m，n)，σi(X)为矩阵X的第i个奇异值.

模型(4)能够被SVT等算法快速求解.在SVT算法中，需要求解如下奇异值阈值算子

(6)

该算子的求解需要如下引理.

引理1若记矩阵Y的SVD分解为Y=UΣVT，则(6)式的最优解为

X*=Sλ(Y)=UDVT

(7)

其中Sλ(·)为软阈值函数，Dii=max(Σii-λ，0).

从上述引理可以看出，主要的计算集中在求解矩阵Y的SVD分解，其时间复杂度为O(mn2)，因此它不适合求解大规模矩阵补全问题.针对这一问题，文献[13]注意到

PΩ(M)+PΩ⊥(Xk)=PΩ(M-Xk)+Xk

(8)

其中：Xk为第k次迭代值，PΩ⊥(·)表示Ω的补集中的元素.显然，(8)式右边的第一部分具有稀疏的特性，第二部分具有低秩的特性.因此，利用SVT算法的思想提出了Soft-Impute算法，在第k+1次迭代时有

Xk+1=Sλ(PΩ(M)+PΩ⊥(Xk))

(9)

该算法的详细步骤如算法1所示.

算法1Soft-Impute算法[13]

输入：部分观察矩阵M，参数λ>0

输出：秩为r的矩阵X

1)初始化X1=0；

2)fork=1，2，… do

3)Y=PΩ(M)+PΩ⊥(Xk)

4)Xk+1=Sλ(Y)

5)end for

6)returnXk+1

然而，在核范数极小化模型中，它同等对待目标矩阵的所有奇异值，这导致该模型不能很好地刻画矩阵的低秩结构.为了解决这一困难，近年来加权核范数[21]被提出来用于更好地刻画目标矩阵的低秩结构.对目标低秩矩阵，加权核范数模型尽可能地对较大奇异值进行较小惩罚，而对较小奇异值进行较大惩罚.对于任一矩阵X∈Rm×n，加权核范数可定义为

(10)

其中w=[w1，w2，…，wr]T和wi≥0为分配给σi(X)的非负加权.核范数极小化方法为了刻画矩阵的低秩结构同等对待目标矩阵的奇异值，而(10)式考虑对较小奇异值进行更多惩罚，而较大的奇异值得到更少惩罚.基于此，利用(10)式去松弛秩函数rank(X)，将原始低秩矩阵补全问题建模为

(11)

模型(11)比模型(4)能够更好地刻画目标矩阵的低秩结构，但是由于加权核范数的引入，得到非凸、非光滑的优化问题，使得对该问题的求解变得非常困难.传统的针对核范数正则化模型的求解方法不能直接用于求解非凸正则化模型.因此，如何设计出快速、稳健、可扩展和可靠的算法是一个至关重要的挑战.本文针对这一问题，利用Soft-Impute的求解思想，融入不精准近邻算法和Nesterov优化理论，提出一个快速高效的低秩矩阵补全算法用于求解模型(11)，理论和实验结果都表明所提出的算法能够得到更快的收敛速率和更高精度的解.

2 WNNM-Impute算法

受到Soft-Impute算法的启发，本节将融入不精准近邻算法和Nesterov优化理论，构建用于求解优化模型(11)的一阶梯度算法.然而，由于加权核范数的引入，优化模型(11)是非凸和非光滑的.因此，为了得到该模型的闭式解，需要求解如下加权核范数近邻算子.

(12)

下面的定理表明，加权核范数近邻问题(12)可转化为线性约束的二次规划问题，从而得到它的闭式解.

(13)

(14)

s.t.d1≥d2≥…≥dr≥0

该定理的证明见文献[21].基于定理1，如取w1≤w2≤…≤wr，可以得到如下推论.

推论1对任意给定λ>0，Y∈Rm×n且其SVD分解为Y=UΣVT，w1≤w2≤…≤wr，r为矩阵Y的秩，则极小化问题

(15)

的最优解为

X*=Sλ(Y)=UDVT

(16)

其中Dii=max(Σii-λwi，0).

该推论的证明见文献[21].该推论表明，虽然极小化问题(15)是非凸和非光滑的，但是它仍然存在全局最优闭式解.利用定理1和推论1的结论，我们提出如下算法用于求解优化模型(11).

算法2WNNM-Impute算法

1)初始化V1，V2∈Rm×n为随机的高斯矩阵，X0=X1=0，Y1=X0，λ0=η‖PΩ(M)‖2，θ0=1；

2)fork=1，2，…，Tdo

3)Rk=QR([Vk，Vk-1])//QR()表示QR分解

4)G=Yk-μ(PΩ(Yk-M))

5)Q=PowerMethod(G，Rk)

6) [U，Σ，V]=SVD(QTG)

7)U={uk|Σii>λwi}

8)V={vk|Σii>λwi}

9)D={dii|max(Σii-λk-1wi，0)}

13) else

14)Xk+1=Yk

15) end if

20) break

21) end if

22)Vk+1=V

23)end for

24)returnXk+1

从定理2和推论1可以看出，在对极小化模型(11)的求解过程中，需要对观察矩阵Y∈Rm×n做SVD分解，它的时间复杂度为O(mn2).因此，当矩阵的规模较大时，这是相当费时的.为此，在算法2中，我们引入PowerMethod算法得到一个正交矩阵Q∈Rm×t，其中t>r且t≪n.这样，对矩阵G的SVD分解可以转为对矩阵QTG的SVD分解.但是，QTG的规模仅为m×t，远小于矩阵G的规模m×n.从而，时间复杂度降为O(mt2).该过程可概述为如下引理.

引理2假定矩阵G∈Rm×n有r个奇异值大于λw，G=QQTG，其中Q∈Rm×t为正交矩阵且t>r，则

1)range(G)⊆range(Q)；

2)Sλ(G)=QSλ(QTG).

该引理的证明过程与文献[22]中的引理1类似，这里省略.需要指出的是，引理2是处理的加权核范数正则子，而非核范数正则子.

由于PowerMethod算法[22]的引入，得到阈值算子的值将是不精确的.因此，需要判断当前值是否可行.于是，在算法2中，我们采用如下式子来确保目标函数F是单调递减的，从而保证目标函数收敛到某一稳定点：

(17)

为了提升算法的收敛速率，在算法2中引入Nesterov加速准则，该准则被广泛地应用于机器学习算法中，如nmAPG，FaNCL-acc，niAPG等.基于此，在算法2中采用如下加速策略

(18)

(19)

实验部分将进一步表明，由于(18)和(19)式加速策略的引入，使得算法2的收敛速率得到大幅地提高.

(20)

这里0<η<1.

在算法2的迭代过程中，得到的解Xk不断地逼近真实解，且目标函数F单调递减，直到收敛到某一稳定点.下面的定理保证了算法2的收敛性，该定理的证明参照文献[20].

定理2假定{Xk}为算法2在迭代过程中产生的解序列，则

2)目标函数F单调递减，且收敛到F(X*)，这里X*为序列{Xk}的任一聚点；

3 实验仿真

为了测试WNNM-Impute算法的效率和准确性，本节将在模拟数据集和真实数据集上进行一系列的对比实验.在接下来的实验中，将包括如下经典或最新算法.

1)SVT算法：经典的、被广泛应用于低秩矩阵补全问题中的方法，它将线性Bregman迭代用于求解低秩矩阵优化问题；

2)APG算法：基于核范数的低秩矩阵补全方法，是快速迭代收缩阈值算法的矩阵版本；

3)R1MP算法：该方法是将正交匹配追踪算法用于求解低秩矩阵补全问题；

4)Soft-Impute算法：该方法是在SVT方法的基础上，利用迭代过程存在“低秩+稀疏”的特性，达到快速求解低秩补全问题的目的；

5)WNNM算法：基于加权核范数的低秩矩阵补全方法.

1)计算

其中：X为结果矩阵，Ω⊥为除观察值以外的位置；

2)结果矩阵X的秩r；

3)运行时间t.

在实验中，我们对不同规模的矩阵进行了测试，即m∈{500，1 000，1 500，3 000}.每个算法独立运行10次，报告其平均NMSE值.

实验结果如表1所示.从表1可以看出，WNNM-Impute算法无论是精度还是效率都要优于其他算法.具体来说，WNNM-Impute算法在所有的数据集上均得到了最小的NMSE，且运行的平均时间是最短的.此外，在实验中，SVT，WNNM和WNNM-Impute算法能够得到秩为5的近似解，而APG，R1MP和Soft-Impute算法得到的近似解的秩远高于5.实验同时揭示了在WNNM-Impute算法中引入不精确的近邻算法和Nesterov加速准则能够极大地提升算法的效率.

表1 不同算法在不同规模和不同采样率下的矩阵补全结果

第二组实验为在真实图像数据集上的低秩矩阵补全.实验中所使用的图像数据如图1所示，每张图片的大小为512×512.

在实验中，我们直接对原始图像进行处理.由于原始图像可能不是严格低秩的，因此使用秩为50的矩阵去近似原始图像.对于每一张图像，随机地去掉图像中50%的数据，余下的数据作为观察值.在本组实验中，采用如下方式来评估所有算法的性能：

1)PSNR(peak signal-to-noise ratio)；

2)运行时间t.

实验结果如表2和图2所示.

图2 WNNM-Impute算法在Lena图像上的恢复结果

表2 不同算法在图像数据集上的恢复结果

从表2可以看出，在大多数测试图像数据上WNNM-Impute算法得到更大的PNSR值.进一步分析发现，虽然WNNM-Impute算法的效率略低于R1MP算法，但是本文提出的算法得到的PNSR值远好于R1MP算法.因此，综合考虑精度和效率，本次实验再一次证实本文提出的WNNM-Impute算法的有效性.

为了进一步测试WNNM-Impute算法的有效性，接下来将在真实数据集上进行实验.这些数据集包括：Jester1，Jester2，Jester3，MovieLens-100K，MovieLens-1M和MovieLens-10M.这些数据集的特性如表3所示，其中Jester数据集来源于一个笑话推荐系统，而MovieLens数据集来自于MovieLens网站.

表3 协同过滤数据集的特征

1)Jester1：包括24 983名用户对36个或更多笑话的评价；

2)Jester2：包括23 500名用户对36个或更多笑话的评价；

3)Jester3：包括24 983名用户评价了15到35个笑话；

4)MovieLens-100K：包含942名用户对1 682部影片的100 000个评价；

5)MovieLens-1M：包含6 040名用户对3 900部影片的1 000 000个评价；

6)MovieLens-10M：包含69 878名用户对10 677部影片的1 000 000个评价.

在本组实验中，采用如下方式来评估所有算法的性能：

1)计算

其中：这里Ω⊥表示测试数据集，X为结果矩阵；

2)结果矩阵的秩r；

3)运行时间t.

在实验中，随机地从每个协调过滤数据集中选取50%的数据作为观察数据，余下的为测试数据.实验结果如表4和表5所示.

表4 不同算法在Jester笑话数据集上的恢复结果

表5 不同算法在MovieLens数据集上的恢复结果

从表4和表5可以看出，在6个协调过滤数据集上WNNM-Impute算法几乎总能得到最小的RMSE值，在效率方面仅比R1MP慢一点.在实验中发现SVT，WNNM和WNNM-Impute算法能够得到秩更低的解，而APG，R1MP和Soft-Impute算法不能得到近似低秩矩阵解.该组实验进一步说了，WNNM-Impute算法在真实协调过滤数据集上是高效的.

4 结束语

本文利用加权核范数去松弛原始低秩极小化问题，得到一个非凸非光滑的优化问题.为了高效地求解该问题，文中利用Soft-Impute的算法思想，融入不精确近邻算子和Nesterov优化理论，提出了一个快速、准确的低秩矩阵补全算法.实验结果表明，在不同规模和不同采样率的模拟数据集上WNNM-Impute算法能够得到更加精确的解且效率更高；在采样率相同和不同规模的协同过滤数据集上WNNM-Impute算法能够得到秩更低且更好质量的解.因此，本文提出的WNNM-Impute算法是一个具有较强竞争力的低秩矩阵补全算法.