论文部分内容阅读
低秩矩阵补全是机器学习领域的一个重要问题，目的是利用矩阵中的一部分观测元素恢复大量的缺失信息。当前的低秩矩阵补全方法主要分为两类:第一类方法是基于核范数或加权核范数最小化的矩阵补全方法，比如截断核范数正则化方法(TNNR)以及迭代重加权核范数最小化方法(IRNN);第二类方法是基于矩阵分解的快速低秩矩阵补全方法，比如低秩矩阵拟合方法(LMaFit)、基于矩阵三分解的矩阵补全方法(FTF)以及基于矩阵双分解的矩阵补全方法(MBF)。这些低秩矩阵补全方法在收敛速度和收敛精度这两方面很难同时具有较好的性能。本文主要针对这一问题，在保证收敛精度的前提下，提出四种快速的矩阵补全方法: (1)为了降低截断核范数正则化方法(TNNR)的迭代次数，提出了一种基于加权残差和截断核范数正则化方法的矩阵补全方法(TNNR-WRE)以及该方法的扩展方法(ETNNR-WRE)。通过为残差矩阵的每一行分配不同的权值，TNNR-WRE方法能够优先恢复矩阵中缺失元素较少的行。实验结果表明，TNNR-WRE方法比TNNR方法具有更少的迭代次数;ETNNR-WRE不仅具有较快的收敛速度，而且具有很好的收敛精度以及参数鲁棒性。 (2)研究了QR分解和SVD分解的内在联系并提出了一种利用QR分解迭代求解矩阵奇异值以及奇异向量的方法CSVD-QR。该方法可以有选择的计算矩阵的前几个较大的奇异值。然后，提出了两种不依赖于SVD分解的快速矩阵补全方法:一种方法是基于QR分解和L2,1范数(矩阵所有行的F范数之和)最小化的矩阵补全方法(LNM-QR);另一种方法是基于QR分解和迭代重加权L2,1范数最小化的矩阵补全方法(IRLNM-QR)。这两种方法都使用CSVD-QR一次迭代所得的结果来恢复缺失信息。与传统方法相比，LNM-QR与IRLNM-QR具有更快的收敛速度。此外，理论分析以及相关实验结果均表明，IRLNM-QR方法中的迭代重加权L2,1范数最终收敛到IRNN方法中的迭代重加权核范数。因此，IRLNM-QR与IRNN具有相同的收敛精度。 (3)在矩阵双分解的框架下，提出了一种基于迭代重加权L2,1范数最小化的矩阵补全方法(MBF-IRLN)。该方法首先利用QR分解提取矩阵的列正交基;然后通过求解一个迭代重加权L2,1范数最小化问题以恢复矩阵中缺失的信息。与IRLNM-QR方法不同的是，MBF-IRLN方法在每一次迭代中的计算量要小很多。因此，MBF-IRLN方法具有更快的收敛速度。此外，理论分析表明MBF-IRLN方法的收敛精度与IRNN方法也基本相当。 (4)在ETNNR-WRE方法的基础上，提出了一种基于加权残差和截断L2,1范数最小化的矩阵补全方法(TLN-WRE)。首先在矩阵双分解的框架下提出截断L2,1范数;然后利用QR分解计算模型求解所需的搜索方向。大量实验结果表明，TLN-WRE方法与第二章的ETNNR-WRE方法具有相似的收敛精度以及参数鲁棒性。然而，其收敛速度明显优于ETNNR-WRE以及其他基于SVD的矩阵补全方法。