-
开放科学（资源服务）标识码（OSID）：
-
在诸如协同过滤[1-2]、降维处理[3]、子空间聚类[4]、图像和信号处理[5-6]等机器学习或数据分析领域，人们通常需要求解如下优化问题
其中：M∈
$\mathbb{R}$ m×n为仅知道部分观察元素的待恢复矩阵，X∈$\mathbb{R}$ m×n为目标矩阵，Ω表示已知的观察元素的位置，
求解优化问题(1)的主要任务是寻找一个最小秩矩阵X*∈
$\mathbb{R}$ m×n，使其满足
这里‖·‖F表示F范数，λ＞0为正则化参数.
然而，由于秩函数rank(X)具有非凸和不连续的特性，优化问题(1)和(3)是NP难的[7]，无法在多项式时间内求得有效解.为了解决这一难题，一个广泛使用的策略是将秩函数rank(X)极小化问题松弛为核范数极小化问题.当满足一定的条件[8]，如|Ω|≥O(N1.2rlogN)(N= max(m，n)，r=rank(X))时，通过求解核范数极小化问题可以高概率近乎完美地恢复原始矩阵M中缺失的元素.一般来说，核范数正则化问题可以被看作为半定规划问题(semi-definite program，SDP)[9].但是，这种策略仅对m，n≤100的矩阵有效.为了有效地求解这一问题，大量的一阶梯度算法被提出.这些方法包括：SVT (singular value thresho-lding)算法[10]和APGL (accelerated proximal gradient with linesearch)算法[11].SVT和APGL算法在通常情况下能够得到较为满意的解且有严格的理论保证，但是它们在每次迭代过程中需要进行费时的SVD (singular value decomposition)分解，这限制了它们在大规模矩阵上的应用.为了缓解这一缺陷，FPCA (fixed point continuation with approximate)算法[12]被提出求解和APGL算法相同的优化问题.由于在FPCA算法中引入了快速蒙特卡罗算法来近似求解SVD，它的效率得到了极大的提升.另一个被广泛关注的算法是Soft-Impute算法[13]，该方法利用求解过程存在“低秩+稀疏”的特性，同时结合SVT算法，达到在每次迭代中快速进行SVD分解的目的.最近，通过引入Nesterov优化理论，使得Soft-Impute算法的计算时间复杂度由
$O\left(\frac{1}{T}\right)$ 提升为$O\left(\frac{1}{T^{2}}\right)$ ，其中T为迭代次数[14].核范数正则化方法作为一个强大的工具已广泛地应用于求解低秩矩阵补全问题，然而正如文献[15]所述，该方法同等对待目标矩阵中的所有奇异值，从而导致过度惩罚较大奇异值.换句话说，核范数正则化方法在大多数时得到的解严重偏离真实解.为了使得较大奇异值得到更少的惩罚，大量的非凸函数被提出用于替代秩函数rank(X)，例如Capped-l1，LSP(log-sum penalty)，TNN(truncated nuclear norm)，SCAD(smoothly clipped absolute deviation)和MCP(minimax concave penalty).在文献[16]中，基于Capped-l1的目标优化函数利用多步的凸松弛策略得以求解；在文献[17]中，理论和实验表明，基于TNN的低秩矩阵补全模型能更佳地逼近目标矩阵的秩函数；在文献[18]中，一个快速、连续和精确的算法被提出用于求解高维线性回归问题.另一类在低秩矩阵补全领域得到广泛关注的策略是，利用Schatten-q(0＜q≤1)拟范数来逼近目标矩阵的秩函数rank(X).然而，基于该策略得到的非凸lq正则化优化问题较难被求解.为了解决这一问题，lqPG(lq-Proximal-Gradient)算法被提出用于求解该非凸lq正则化优化问题.在lqPG算法的每次迭代过程中包含不精确的近似求解和费时的SVD，这严重制约了算法的应用范围.基于此，文献[19]和文献[20]分别提出利用Schatten-
$\frac{1}{2}$ 和Schatten-$\frac{2}{3}$ 拟范数来逼近目标矩阵的秩函数rank(X).同时，提出基于半阈值算子和$\frac{2}{3}$ 阈值算子的不动点算法.对比lqPG算法，基于Schatten-$\frac{1}{2}$ 和Schatten-$\frac{2}{3}$ 拟范数的阈值函数具有闭式解，因此得到的解更精确.所有实验结果表明，相比核范数正则化方法，这些非凸正则化方法性能更佳.基于非凸正则化方法的优良性能，本文对基于加权核范数正则化模型进行进一步的分析和探讨，并借鉴Soft-Impute算法的思想提出一个拥有更快收敛速率和能够得到更高精度解的低秩矩阵补全算法.在本文提出WNNM-Impute(weighted nuclear norm minimization impute)算法的迭代过程中，需要进行费时的SVD分解.针对这一问题，通过引入不精确的近邻算子极大地降低WNNM-Impute算法的时间复杂度，从而使得算法收敛更快.同时，在算法中引入Nesterov加速策略，使得算法的总体迭代次数进一步减少.本文提出的算法基于Soft-Impute算法，但是实验结果表明，它比Soft-Impute算法收敛更快且得到的解的精度更高.因此，本文提出的算法适合用于求解大规模低秩矩阵补全问题.
HTML
-
当使用核范数去松弛秩函数rank(X)时，数学上可将低秩矩阵补全问题建模为
这里‖X‖*表示核范数，定义为
其中r=min(m，n)，σi(X)为矩阵X的第i个奇异值.
模型(4)能够被SVT等算法快速求解.在SVT算法中，需要求解如下奇异值阈值算子
该算子的求解需要如下引理.
引理1 若记矩阵Y的SVD分解为Y=UΣVT，则(6)式的最优解为
其中
从上述引理可以看出，主要的计算集中在求解矩阵Y的SVD分解，其时间复杂度为O(mn2)，因此它不适合求解大规模矩阵补全问题.针对这一问题，文献[13]注意到
其中：Xk为第k次迭代值，
该算法的详细步骤如算法1所示.
算法1 Soft-Impute算法[13]
输入：部分观察矩阵M，参数λ＞0
输出：秩为r的矩阵X
1) 初始化X1=0；
2) for k=1，2，… do
3)
4)
5) end for
6) return Xk+1
然而，在核范数极小化模型中，它同等对待目标矩阵的所有奇异值，这导致该模型不能很好地刻画矩阵的低秩结构.为了解决这一困难，近年来加权核范数[21]被提出来用于更好地刻画目标矩阵的低秩结构.对目标低秩矩阵，加权核范数模型尽可能地对较大奇异值进行较小惩罚，而对较小奇异值进行较大惩罚.对于任一矩阵X∈
$\mathbb{R}$ m×n，加权核范数可定义为其中w=[w1，w2，…，wr]T和wi≥0为分配给σi(X)的非负加权.核范数极小化方法为了刻画矩阵的低秩结构同等对待目标矩阵的奇异值，而(10)式考虑对较小奇异值进行更多惩罚，而较大的奇异值得到更少惩罚.基于此，利用(10)式去松弛秩函数rank(X)，将原始低秩矩阵补全问题建模为
模型(11)比模型(4)能够更好地刻画目标矩阵的低秩结构，但是由于加权核范数的引入，得到非凸、非光滑的优化问题，使得对该问题的求解变得非常困难.传统的针对核范数正则化模型的求解方法不能直接用于求解非凸正则化模型.因此，如何设计出快速、稳健、可扩展和可靠的算法是一个至关重要的挑战.本文针对这一问题，利用Soft-Impute的求解思想，融入不精准近邻算法和Nesterov优化理论，提出一个快速高效的低秩矩阵补全算法用于求解模型(11)，理论和实验结果都表明所提出的算法能够得到更快的收敛速率和更高精度的解.
-
受到Soft-Impute算法的启发，本节将融入不精准近邻算法和Nesterov优化理论，构建用于求解优化模型(11)的一阶梯度算法.然而，由于加权核范数的引入，优化模型(11)是非凸和非光滑的.因此，为了得到该模型的闭式解，需要求解如下加权核范数近邻算子.
下面的定理表明，加权核范数近邻问题(12)可转化为线性约束的二次规划问题，从而得到它的闭式解.
定理1 对任意给定矩阵M∈
$\mathbb{R}$ m×n且其SVD分解为M=UΣVT，其中$\boldsymbol{\varSigma}=\left(\begin{array}{l}\operatorname{diag}\left(\sigma_{1}, \sigma_{2}, \cdots, \sigma_{r}\right) \\ 0\end{array}\right) \in \mathbb{R}^{m \times n}$ .则加权核范数近邻问题(12)的全局最优解为其中
$\stackrel{\wedge}{\boldsymbol{D}}=\left(\begin{array}{c}\operatorname{diag}\left(d_{1}, d_{2}, \cdots, d_{r}\right) \\ 0\end{array}\right)$ ，(d1，d2，…，dr)是如下凸优化问题的最优解该定理的证明见文献[21].基于定理1，如取w1≤w2≤···≤wr，可以得到如下推论.
推论1 对任意给定λ＞0，Y∈
$\mathbb{R}$ m×n且其SVD分解为Y=UΣVT，w1≤w2≤···≤wr，r为矩阵Y的秩，则极小化问题的最优解为
其中Dii=max(Σii-λwi，0).
该推论的证明见文献[21].该推论表明，虽然极小化问题(15)是非凸和非光滑的，但是它仍然存在全局最优闭式解.利用定理1和推论1的结论，我们提出如下算法用于求解优化模型(11).
算法2 WNNM-Impute算法
输入：部分观察矩阵M，参数λ＞0；给定
$\mu \in\left(0, \frac{1}{L}\right), \bar{\lambda}=10^{-6}$ ，δ＞0和η∈(0，1)输出：秩为r的矩阵
${\overset{\wedge }{\mathop{\boldsymbol{X}}}}$ 1) 初始化V1，V2∈
$\mathbb{R}$ m×n为随机的高斯矩阵，X0=X1=0，Y1=X0，
2) for k=1，2，…，T do
3) Rk=QR([Vk，Vk-1])//QR()表示QR分解
4)
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)
10)
$\stackrel{\vee}{\boldsymbol{Z}}=\boldsymbol{QUDV}^{\mathrm{T}}$ 11) if
$F(\stackrel{\vee}{\boldsymbol{Z}}) \leqslant F\left(\boldsymbol{X}_{k}\right)-\frac{\delta}{2}\left\|\stackrel{\vee}{\boldsymbol{Z}}-\boldsymbol{X}_{k}\right\|_{F}^{2}$ 12)
$\boldsymbol{X}_{k+1}=\stackrel{\vee}{\boldsymbol{Z}}$ 13) else
14) Xk+1=Yk
15) end if
16)
$\theta_{k}=\frac{1+\sqrt{1+4 \theta_{k-1}^{2}}}{2}$ 17)
$\boldsymbol{Y}_{k+1}=\boldsymbol{X}_{k+1}+\left(\frac{\theta_{k-1}}{\theta_{k}}\right)\left(\stackrel{\vee}{\boldsymbol{Z}}-\boldsymbol{X}_{k+1}\right)+\left(\frac{\theta_{k-1}-1}{\theta_{k}}\right)\left(\boldsymbol{X}_{k+1}-\boldsymbol{X}_{k}\right)$ 18)
$\lambda_{k}=\left\{\bar{\lambda}, \eta \lambda_{k-1}\right\}$ 19) if λk==λ
20) break
21) end if
22) Vk+1=V
23) end for
24) return Xk+1
从定理2和推论1可以看出，在对极小化模型(11)的求解过程中，需要对观察矩阵Y∈
$\mathbb{R}$ m×n做SVD分解，它的时间复杂度为O(mn2).因此，当矩阵的规模较大时，这是相当费时的.为此，在算法2中，我们引入PowerMethod算法得到一个正交矩阵Q∈$\mathbb{R}$ m×t，其中t＞r且t≪n.这样，对矩阵G的SVD分解可以转为对矩阵QTG的SVD分解.但是，QTG的规模仅为m×t，远小于矩阵G的规模m×n.从而，时间复杂度降为O(mt2).该过程可概述为如下引理.引理2 假定矩阵G∈
$\mathbb{R}$ m×n有r个奇异值大于λw，G=QQTG，其中Q∈$\mathbb{R}$ m×t为正交矩阵且t＞r，则1) range(G)⊆range(Q)；
2)
该引理的证明过程与文献[22]中的引理1类似，这里省略.需要指出的是，引理2是处理的加权核范数正则子，而非核范数正则子.
由于PowerMethod算法[22]的引入，得到阈值算子的值将是不精确的.因此，需要判断当前值是否可行.于是，在算法2中，我们采用如下式子来确保目标函数F是单调递减的，从而保证目标函数收敛到某一稳定点：
为了提升算法的收敛速率，在算法2中引入Nesterov加速准则，该准则被广泛地应用于机器学习算法中，如nmAPG，FaNCL-acc，niAPG等.基于此，在算法2中采用如下加速策略
实验部分将进一步表明，由于(18)和(19)式加速策略的引入，使得算法2的收敛速率得到大幅地提高.
众所周知，正则化参数λ在算法中扮演非常重要的角色，因此如何设定该参数将直接影响到算法的准确性.幸运的是，这一问题在文献[12, 20]中得到很好地研究.在算法2中，引入连续化技术，该技术被广泛地应用在众多一阶优化算法中.连续化技术的核心思想是引入一个单调递减的序列λk：λ1＞λ2＞…＞λ＞0，这里λ为任意小的正实数.在第k次迭代中，令λ=λk.基于该思想，在算法2中，采用如下策略
这里0＜η＜1.
在算法2的迭代过程中，得到的解Xk不断地逼近真实解，且目标函数F单调递减，直到收敛到某一稳定点.下面的定理保证了算法2的收敛性，该定理的证明参照文献[20].
定理2 假定{Xk}为算法2在迭代过程中产生的解序列，则
1) {Xk}有界且至少存在一个聚点，即
$\lim\limits_{k \rightarrow \infty} \boldsymbol{X}_{k}=\boldsymbol{X}^{*}$ ；2) 目标函数F单调递减，且收敛到F(X*)，这里X*为序列{Xk}的任一聚点；
3) {Xk}渐进正则，即
$\lim\limits_{k \rightarrow \infty}\left\|\boldsymbol{X}_{k+1}-\boldsymbol{X}_{k}\right\|_{F}^{2}=0$ .
-
为了测试WNNM-Impute算法的效率和准确性，本节将在模拟数据集和真实数据集上进行一系列的对比实验.在接下来的实验中，将包括如下经典或最新算法.
1) SVT算法：经典的、被广泛应用于低秩矩阵补全问题中的方法，它将线性Bregman迭代用于求解低秩矩阵优化问题；
2) APG算法：基于核范数的低秩矩阵补全方法，是快速迭代收缩阈值算法的矩阵版本；
3) R1MP算法：该方法是将正交匹配追踪算法用于求解低秩矩阵补全问题；
4) Soft-Impute算法：该方法是在SVT方法的基础上，利用迭代过程存在“低秩+稀疏”的特性，达到快速求解低秩补全问题的目的；
5) WNNM算法：基于加权核范数的低秩矩阵补全方法.
在接下来的实验中，各个算法的参数设置为对应文章提供的推荐设置.WNNM-Impute算法的参数设置为：λ=10-6，μ=1.6，η=0.75.此外，当前后两次迭代得到的解没有显著变化，即
$\left\|\boldsymbol{X}_{k+1}-\boldsymbol{X}_{k}\right\|_{F}^{2}< 10^{-5}$ 时算法停止.所有算法采用MATLAB R2014编程，实验环境为Intel Xeon E5-2680-v4处理器(3核，2.4GHz)，256GB内存，Windows server 2008操作系统.本文的第一组实验为在模拟数据集上的低秩补全.首先，随机生成矩阵ML∈
$\mathbb{R}$ m×r和MR∈$\mathbb{R}$ r×n，令M=MLMR+N，其中矩阵ML，MR和N中的每个元素为独立高斯随机变量，N为方差为0.1的高斯白噪音矩阵.不失一般性，这里令m=n和r=5.随后，从观测矩阵M中随机均匀采样得到若干观测值，使用$\mathrm{SR}=\frac{10 m \log m}{m^{2}}$ 表示采样率.本文采用如下方式来评估所有算法的性能：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所示，每张图片的大小为512×512.
在实验中，我们直接对原始图像进行处理.由于原始图像可能不是严格低秩的，因此使用秩为50的矩阵去近似原始图像.对于每一张图像，随机地去掉图像中50%的数据，余下的数据作为观察值.在本组实验中，采用如下方式来评估所有算法的性能：
1) PSNR(peak signal-to-noise ratio)；
2) 运行时间t.
从表 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网站.
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和表 5可以看出，在6个协调过滤数据集上WNNM-Impute算法几乎总能得到最小的RMSE值，在效率方面仅比R1MP慢一点.在实验中发现SVT，WNNM和WNNM-Impute算法能够得到秩更低的解，而APG，R1MP和Soft-Impute算法不能得到近似低秩矩阵解.该组实验进一步说了，WNNM-Impute算法在真实协调过滤数据集上是高效的.
-
本文利用加权核范数去松弛原始低秩极小化问题，得到一个非凸非光滑的优化问题.为了高效地求解该问题，文中利用Soft-Impute的算法思想，融入不精确近邻算子和Nesterov优化理论，提出了一个快速、准确的低秩矩阵补全算法.实验结果表明，在不同规模和不同采样率的模拟数据集上WNNM-Impute算法能够得到更加精确的解且效率更高；在采样率相同和不同规模的协同过滤数据集上WNNM-Impute算法能够得到秩更低且更好质量的解.因此，本文提出的WNNM-Impute算法是一个具有较强竞争力的低秩矩阵补全算法.
DownLoad: