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

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

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

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

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

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

其中为软阈值函数，D_ii=max(Σ_ii-λ，0).

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

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

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

算法1  Soft-Impute算法^[13]

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

输出：秩为r的矩阵X

1) 初始化X₁=0；

2) for k=1，2，… do

3)     

4)     

5) end for

6) return X_k+1

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

其中w=[w₁，w₂，…，w_r]^T和w_i≥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ΣV^T，其中 $\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)$，(d₁，d₂，…，d_r)是如下凸优化问题的最优解

该定理的证明见文献[21].基于定理1，如取w₁≤w₂≤···≤w_r，可以得到如下推论.

推论1  对任意给定λ＞0，Y∈ $\mathbb{R}$^m×n且其SVD分解为Y=UΣV^T，w₁≤w₂≤···≤w_r，r为矩阵Y的秩，则极小化问题

的最优解为

其中D_ii=max(Σ_ii-λw_i，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) 初始化V₁，V₂∈ $\mathbb{R}$^m×n为随机的高斯矩阵，X₀=X₁=0，Y₁=X₀，，θ₀=1；

2) for k=1，2，…，T do

3)     R_k=QR([V_k，V_k-1])//QR()表示QR分解

4)     

5)     Q=PowerMethod(G，R_k)

6)     [U，Σ，V]=SVD(Q^TG)

7)     U={u_k|Σ_ii＞λw_i}

8)     V={v_k|Σ_ii＞λw_i}

9)     D=d_ii|max(Σ_ii-λ_k-1w_i，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)        X_k+1=Y_k

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)    V_k+1=V

23) end for

24) return X_k+1

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

引理2  假定矩阵G∈ $\mathbb{R}$^m×n有r个奇异值大于λw，G=QQ^TG，其中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：λ₁＞λ₂＞…＞λ＞0，这里λ为任意小的正实数.在第k次迭代中，令λ=λ_k.基于该思想，在算法2中，采用如下策略

这里0＜η＜1.

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

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

1) {X_k}有界且至少存在一个聚点，即 $\lim\limits_{k \rightarrow \infty} \boldsymbol{X}_{k}=\boldsymbol{X}^{*}$；

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

3) {X_k}渐进正则，即 $\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操作系统.

本文的第一组实验为在模拟数据集上的低秩补全.首先，随机生成矩阵M_L∈ $\mathbb{R}$^m×r和M_R∈ $\mathbb{R}$^r×n，令M=M_LM_R+N，其中矩阵M_L，M_R和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和图 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网站.

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算法是一个具有较强竞争力的低秩矩阵补全算法.