论文总字数：12777字

摘 要

本文主要对求解矩阵填充问题的奇异值阈值算法进行研究，该算法广泛地应用于数据信息处理、个性化服务、图像去噪等领域。该技术的主要原理是通过构建奇异值阈值算子进行优化迭代来求解核范数最小化问题，从而能够很好的解决大型矩阵的填充问题。但由于该算法存在计算量大、迭代时间长等缺陷，如今已难以满足日益增长的信息需求。为改善迭代算法的不足，本文从迭代算法中参数的角度出发，将该参数与迭代次数绑定进行重构建，进而完善相应的算法运算结果。

依据高斯分布所拟合的数据集对该算法进行实验性论证，实验结果表明该算法与传统奇异值阈值算法相比在运算速度及迭代精度上均提高了20%左右。这表明该算法在一定程度上提高了原算法的运算速度，具有较好的性能。

关键词：奇异值阈值分解；矩阵填充；核范数最小化；

Abstract

This paper mainly studies the singular value thresholding algorithm for solving the matrix filling problem, which is widely used in data information processing, personalized service, image denoising and other fields. The main principle of this technique is to solve the kernel norm minimization problem by constructing a singular value thresholding operator for optimization iteration, which can solve the problem of large matrices filling well. However, due to the shortcomings of large calculation amount and long iteration time, the algorithm has been unable to meet the increasing information demand. In order to improve the deficiencies of the iterative algorithm, this paper starts from the perspective of the parameters in the iterative algorithm, binds the parameter with the number of iterations to reconstruct, and then improves the corresponding algorithm operation results.

Based on the data set fitted by the Gaussian distribution, the algorithm is experimentally demonstrated. The experimental results show that the algorithm has improved the speed and iteration accuracy by about 20% compared with the traditional singular value thresholding algorithm. This shows that the algorithm improves the calculation speed of the original algorithm to a certain extent, and has better performance.

Key Words: singular value thresholding; matrix filling; kernel norm minimization

目录

目录 1

第1章 绪论 1

1.1 研究背景及意义 1

1.2国内外研究进展状况 1

1.3 论文的主要内容及安排 2

第2章 问题的分析及构建 3

2.1 核范数最小化问题 3

2.2 核范数最小化问题的解存在性 4

第3章 SVT算法 5

3.1模型的构造 5

3.2迭代算法 6

3.3算法细节补充 8

3.3.1 算法的步长 8

3.3.2 暂停标准 8

第4章 算法的改进 10

4.1 SVTC算法 10

4.2实验结果 11

第5章 总结与期望 13

5.1 总结 13

5.2 期望 13

参考文献 14

致谢 15

第1章 绪论

1.1 研究背景及意义

随着时代的进步与发展，互联网逐渐充斥着我们的生活。2019年8月30日中国互联网中心(CNNIC)在京发布第44次《中国互联网络发展状况统计报告》，报告表明，截止2019年6月，我国网民规模达到8.54亿，手机网络规模达8.47亿，互联网普及率达61.2%。中国互联网用户的不断增长及中国互联网的持续发展与创新，造就了中国经济的蓬勃发展。

用户的增长，伴随着海量信息在网络上流通。但由于数据量过大，用户往往很难从大量数据中检索出对自己有用的信息，这严重地降低了用户在生产、生活中效率。我们希望设计相应的功能，将人们从其中解放出来，而“个性化推荐”便是解决该问题的一种手段，其定义是——基于用户的海量信息^[1]进行数据化处理，模拟用户相应的意向及个性化需求，为用户提供精准、有效的信息，其在电商领域，社交领域都取得了不错的成效。在推荐算法的效率问题上，Emmanuel^[2]做出了开创性贡献，提出低秩矩阵的奇异值分解算法，该方法是通过构建奇异值阈值算子进行优化迭代来求解核范数最小化问题，能够很好提高算法的推荐效率。

现如今，不少提高推荐算法效率的研究仍从低秩矩阵的奇异值分解方法角度入手，因此对该算法的研究是一项十分重要，很有意义的事情。

1.2国内外研究进展状况

低秩矩阵的奇异值分解的研究起因于Netflix^[3]为提高推荐算法的效率而提出的百万奖金的问题。Emmanuel所发表的结果，引发了相关研究的热潮。其中就恢复完整矩阵数据量的问题引发了不断的探究,见^{[4],[5],[6],[7]}。Emmanuel和Tao^[5]指出若原矩阵满足低秩，且具有低相干性条件下，恢复出原来矩阵仅需数据量为。Recht^[7]将该量减少到。

2011年，陈峰峰^[8] 针对奇异值阈值在Netflix问题中的研究，通过均值偏移改善填充精度，提出了平衡模型逼近与误差降低的可变阈值方法。

2012年，Liu Jun^[9]基于Nesterov方法，采用自适应策略，将奇异值阈值算法的收敛性由原来的提高到。

2014年，王平^[10]改进Liu Jun的研究，提出加速的Nemirovski算法，算法收敛程度有所提高。

2015年，王娜^[11]提出了Nesterov线搜索的迭代阈值算法和自适应Nemirovski线搜索的迭代阈值算法。

2017年，Nematollah^[12]提出对每一次迭代的阈值进行适应性改变的适应性阈值算法。

2017年，Yaohang Li^[13]提出对每次迭代的左奇异值作近似求解的R4SVD算法。

2018年，李艳^[14]提出对观测数据基于奇异值分解的随机正交方法迭代计算。

2020年，Angang Cui^[15] 提出对正则化变换仿射矩阵的自适应迭代奇异值阈值算法，解决参数和参数的选择问题。

1.3 论文的主要内容及安排

本文主要是对奇异值阈值算法的模型来源、模型构建进行描述，并针对奇异值阈值算法所存在的问题进行相应改进。其主要方法是将软阈值算法中的进行适当偏移，同时为解决算法在该情况所产生的不稳定性，将参数与迭代次数绑定，从而降低了改进的不稳定性，并解决原有算法存在迭代次数高，计算精度低的问题。

全文的结构如下：

第一章，绪论。阐述本文的研究背景及其意义并介绍该算法在国内外的研究进展，同时论述该文的主要内容并安排全文的组织结构框架。

第二章，问题的分析及构建。从Netflix百万奖金的例子出发，对该问题进行模型的构建，并对该模型的可行性进行剖析。

第三章，SVT算法。简单论述该算法模型的构建过程及模型算法证明的过程，对模型中的细节进行了相应补充。

第四章，算法的改进。论述改进算法的方法，对改进算法的运算速度及结果的精度进行了实验性验证。

第五章，总结与展望。对本文研究成果进行总结并提出相应的不足之处，为今后研究人员的研究方向开拓思路。

第2章 问题的分析及构建

我们已经阐述了研究矩阵填充问题的原因，接下来我们将基于个性化推荐系统的背景，讨论如何把该类问题转化为矩阵填充问题的模型，并对该问题的模型进行可行性分析。

请支付后下载全文，论文总字数：12777字