低秩矩阵近似理论与应用

1、University of Science and Technology of China硕士学位论文论文题目 低秩.矩 阵近仞理论与应 用作者姓名仲小伟学科专业计算机应用技术导师姓名徐林菊副教授完成时间二。一六年五月中10绊苍城*大净硕士学位论文低秩矩阵近似理论与应用作者姓名:仲小伟学科专业：计算机应用技术导师姓名：徐林莉副教授二。一六年四月完成时间：University of Science and Technology of ChinaA dissertation for masters degreeLow Rank Matrix ApproximationTheory and Appl

2、icationAuthor :Xiaowei ZhongSpeciality : Computer Application Technology Supervisor :Prof. Linli XuFinished Time :April, 2016中国科学技术大学学位论文原创性声明本人声明所呈交的学位论文，是本人在导师指导下进行研究工作所取得的成 果。除已特别加以标注和致谢的地方外，论文中不包含任何他人巳经发表或撰 写过的研究成果。与我一同工作的同志对本研究所做的贡献均已在论文中作了 明确的说明。作者签名:签字日期：痢中国科学技术大学学位论文授权使用声明作为申请学位的条件之一，学位论文著作权

3、拥有者授权中国科学技术大学 拥有学位论文的部分使用权，即：学校有权按有关规定向国家有关部门或机构 送交论文的复印件和电子版，允许论文被查阅和借阅，可以将学位论文编入 中国学位论文全文数据库等有关数据库进行检索，可以采用影印、缩印或扫 描等复制手段保存、汇编学位论文。本人提交的电子文档的内容和纸质论文的 内容相一致。保密的学位论文在解密后也遵守此规定。口保密作者签名:签字日期:导师签名:签字日期：w&e摘要低秩矩阵近似，是机器学习、数值优化、理论计算机科学等领域的重要研 究方向。它既有严格的理论基础，在实际问题中，也有着广泛的应用。低秩矩 阵近似的本质是利用高维空间中的低维结构，寻找一个合适的低

4、秩矩阵来近似 原来的复杂矩阵，使得低秩矩阵既能够较好地保持原来复杂矩阵的诸多性质, 又能够有效地减少冗余信息和噪声，从而降低存储空间和计算量。近年来，使 用非凸松弛的方法来求解低秩矩阵近似问题受到越来越多的关注。一些理论 分析和实验验证表明，相比于凸松弛方法，非凸松弛可以对实际问题有着更好 的近似，能够更好地刻画实际问题的本质属性。然而，非凸优化问题具有很高 的复杂性，设计快速高效的优化算法去求解非凸优化问题是一项巨大的挑战。 本文使用更加简单、直观、灵活的非凸加权核范数作为低秩惩罚项，并提出一 种解决低秩矩阵近似问题的统一的、非凸的框架。同时，本文提出一种叫做 迭代收缩阈值与权值再分配算法(

5、ISTRA),来求解上述非凸的低秩矩阵近似问 题。在理论方面，本文证明了在一定假设下，ISTRA算法能够有效地收敛到目 标函数的局部最优解，即稳定点，并有次线性的收敛速度。在合成数据和实际 图像数据上的矩阵补全实验表明，本文提出的迭代收缩阕值与权值再分配算法 (ISTRA)能够有效地恢复低秩矩阵，在精确度和速度上，都能超过当前最好的 低秩矩阵恢复算法。关键词：低秩矩阵近似，非凸松弛，非凸优化，矩阵补全，加权核范数，迭代 收缩阈值与权值再分配算法ABSTRACTABSTRACTLow rank matrix approximation is an important topic in machi

6、ne learning, numerical optimization and theoretical computer science. It has both rigorous theoretical foundations and wide applications in practice. The essence of low rank matrix approximation is to exploit low-dimensional structure in high-dimensional space. It intends to find a proper low rank m

7、atrix to approximate the original complex matrix. The low rank matrix will preserve most properties of the original matrix, and it can also reduce the redundant information and noise, which will decrease the memory and computational cost. Recently, solving low rank matrix approximation problems by l

8、everaging noncon- vex relaxation has received more and more attentions. Some theoretical analyses and practical experiments show that it can approximate the original problem and capture the nature of the problem better than convex relaxation. However, nonconvex optimization problems are generally co

9、mplex and can hardly be solved efficiently. In this paper, we use the weighted nuclear norm that is simple, intuitive and flexible as a low rank penalty. based on which, we propose a unified nonconvex framework to solve the low rank matrix approximation problem. And we propose an Iterative Shrinkage

10、 Thresholding and Reweighted Algorithm (ISTRA) to solve the nonconvex problem. In theory; we prove that under certain assumptions the proposed ISTRA algorithm can converge to the critical point that is local optimal solution efficiently with sublinear convergence rate. In practice, matrix completion

11、 experiments on synthetic data and real image data demonstrate the accuracy and efficiency of the proposed ISTRA algorithm, which can ouiperfbrni state-of-the-art methods.Keywords: Low Rank Matrix Approximation, Nonconvex Relaxation. Nonconvex Optimization. Matrix Completion. Weighted Nuclear Norm,

12、ISTRA目录 TOC o 1-5 h z HYPERLINK l bookmark14 o Current Document 摘要 I HYPERLINK l bookmark17 o Current Document ABSTRACT Ill HYPERLINK l bookmark20 o Current Document 目录V HYPERLINK l bookmark23 o Current Document 主要符号对照表VII HYPERLINK l bookmark26 o Current Document 第一章绪论1 HYPERLINK l bookmark29 o Cur

13、rent Document 1.1弓I言 I HYPERLINK l bookmark32 o Current Document 1.2研究背景与意义I HYPERLINK l bookmark35 o Current Document 1.3国内外研究现状2 HYPERLINK l bookmark38 o Current Document 1.4本文主要工作与贡献3 HYPERLINK l bookmark45 o Current Document 1.5本文组织结构4 HYPERLINK l bookmark48 o Current Document 第二章低秩矩阵近似相关工作概述7 H

14、YPERLINK l bookmark51 o Current Document 2.1低秩矩阵近似的理论研究7 HYPERLINK l bookmark54 o Current Document 2.1.1低秩矩阵近似的问题定义7 HYPERLINK l bookmark57 o Current Document 2.1.2低秩矩阵近似的凸松弛方法82.1.3低秩矩阵近似与稀疏优化的联系 10 HYPERLINK l bookmark62 o Current Document 2.1.4低秩矩阵近似的非凸松弛方法 11 HYPERLINK l bookmark65 o Current Doc

15、ument 2.1.5基于矩阵分解的方法13 HYPERLINK l bookmark68 o Current Document 2.2低秩矩阵近似的应用13 HYPERLINK l bookmark71 o Current Document 2.2.1推荐系统13 HYPERLINK l bookmark74 o Current Document 2.2.2兽棒主成分分析142.2.3其它应用16 HYPERLINK l bookmark98 o Current Document 2.3本章小结16 HYPERLINK l bookmark77 o Current Document 第三章

16、低秩矩阵近似问题的优化算法17 HYPERLINK l bookmark80 o Current Document 3凸优化方法17 HYPERLINK l bookmark83 o Current Document 3.1.1半定规划方法 173.1.2 Proximal 梯度法 17 HYPERLINK l bookmark86 o Current Document 3.2非凸优化方法19 HYPERLINK l bookmark89 o Current Document 3.2.1交替优化方法20 HYPERLINK l bookmark92 o Current Document 3.2

17、.2交替方向乘子法203.3本章小结22目录 TOC o 1-5 h z HYPERLINK l bookmark101 o Current Document 第四章 迭代收缩阈值与权值再分配算法ISTRA 23 HYPERLINK l bookmark104 o Current Document 4.1问题定义23 HYPERLINK l bookmark107 o Current Document 4.2基本方法244.2.1 构造 Proximal 问题24 HYPERLINK l bookmark110 o Current Document 4.2.2权值再分配策略26 HYPERLI

18、NK l bookmark113 o Current Document 4.2.3迭代收缩阈值与权值再分配算法ISTRA 28 HYPERLINK l bookmark116 o Current Document 4.3收敛性分析304.3.1步长有界304.3.2收敛结果 314.3.3收敛速度334.3.4 与 Majorization Minimization 方法的联系 33 HYPERLINK l bookmark121 o Current Document 4.4实验分析344.4.1合成数据实验35 HYPERLINK l bookmark129 o Current Docume

19、nt 4.4.2实际图像数据实验37 HYPERLINK l bookmark132 o Current Document 4.5本章小结41 HYPERLINK l bookmark135 o Current Document 第五章结论与展望43 HYPERLINK l bookmark138 o Current Document 5.1工作内容总结 43 HYPERLINK l bookmark141 o Current Document 5.2下一步工作展望44 HYPERLINK l bookmark144 o Current Document 参考文献45 HYPERLINK l

20、bookmark207 o Current Document 致谢49 HYPERLINK l bookmark210 o Current Document 在读期间发表的学术论文与取得的研究成果51Ax 也町Iloilo 间hAATXk fW v/(x) rank(X) 耳(X) 如X) 心)主要符号对照表常数入向量g e Rn权值向量s,每个分量都为正数向量z的范数 向量；r的心范数 矩阵A e Rmxn 矩阵刀的转置 矩阵4的(2, j)位置上的元素 算法第A:次迭代的更新值 损失函数，自变量为矩阵X 函数/(X)在X处的梯度 矩阵X的秩函数 投影算子%()矩阵X的第七大奇异值矩阵X所有

21、的奇异值组成的向量，即(X) = i(X)气(X)T 矩阵内积，BP(A, B = tr(ATB)矩阵X的迹矩阵X的核范数矩阵X的Frobenius范数矩阵X的谱范数次梯度大。，表示渐进性第一章绪论1.1引言我们生活在一个大数据的时代，各行各业每天都在不断产生海量的数据。 如何有效地利用这些海量数据，充分挖掘海量数据中蕴含的有价值的知识与信 息，是机器学习与数据挖掘领域最重要的研究方向。例如，通过对大量用户购 物记录的分析与挖掘，购物网站可以给用户推荐更适合的商品1。通过对海量 图像的处理与学习，计算机可以很好地识别一幅具体的图像2。通过对人类 棋谱的持续学习，AlphaGo可以在围棋上战胜人

22、类3。我们希望设计高效的算 法，使得计算机在各个方面辅助人类，将人类从繁重的劳动中解放出来，这就 是人工智能的目的。而基于大数据的机器学习和数据挖掘方法，无疑是当前实 现人工智能最有效的途径。在大数据背景下，传统的机器学习和数据挖掘方法 很多将难以适用。作为机器学习和数据挖掘从业者，我们需要设计新的机器学 习和数据挖掘模型去刻画大数据的本质，需要设计高效的优化算法，能够训练 海量的数据。因此，大数据时代，充满着机遇与挑战。1.2研究背景与意义在大部分大数据问题中，都可以将数据表示成矩阵的形式。一般来说，矩 阵的每一行可以表示一个数据，相应的，矩阵的每一列可以表示数据的特征。 对于大数据而言，数

23、据的数量和特征都很大，因而表示数据的矩阵极为庞大, 也极为复杂，这既增加了数据存储的复杂性，也加大了数据处理与计算的难度。 在实际情况中，大数据通常具有非常多的冗余信息和噪声，表示成一个很复杂 的矩阵，对存储和计算都是过度的消耗。低秩矩阵近似的目的就是去除数据中 的冗余信息，同时降低噪声的影响，提炼出数据中真正有用的信息，来代替原 有的数据或恢复出原有的数据。它的本质是利用高维空间中的低维结构，即找 一个合适的低秩矩阵来近似原来的高秩矩阵，使得低秩矩阵既能够较好地保持 原来矩阵的一些性质，又能够减少冗余信息和噪声，降低存储空间。并且，在 处理低秩矩阵时，能够有效地减少计算量。鉴于低秩矩阵近似在

24、大数据处理上 有如此多的优势，其在机器学习，数据挖掘，计算机视觉，理论计算机科学, 数值优化，数值线性代数等诸多领域都有着广泛的理论研究与实际应用。随着对大数据越来越深入的研究，有一个关键哲学问题是，我们真的需要 那么多数据吗？或者更具体的，对于一个特定的问题，我们需要多少数据，就 足够解决该问题？低秩矩阵近似的研究，能够在很大程度上回答这些问题。因 为海量数据中，存在着冗余信息和噪声，低秩矩阵近似，能够很好地筛选出那 些有代表性的、对解决问题起关键作用的数据，并能够在一定程度上去掉噪声 的影响。因此，对于很多具体问题，并不需要海量的数据，要解决该问题，会 有一个需要数据量的上界。如果要完美解

25、决该问题，所需要的数据可能比较多, 但也有上界，不会无限量。而对于很多的实际问题，并不需要完美解决，只需 要求解该问题的近似解，在实际中就有很好的效果。因而，所需数据量的上界 通常和问题的解与最优解的近似程度有关。艮L如果要求得问题的解质量高, 即与最优解十分近似，则需要的数据量比较大。相反，如果只需要求得一个一 般质量的解，在实际中就有很好的效果，那么需要的数据量就会比较少。因此, 在很多实际问题中，使用一个低秩矩阵去近似原有的复杂矩阵，就足以获得该 问题的效果非常好的近似解，而并不需要过多的数据量或过于复杂的矩阵，增 大内存和计算开销。所以，通过低秩矩阵近似的研究，我们知道，并不是数据 量

26、越多越好，有时候在少量的数据上也能够取得类似于大数据的效果，甚至更 好。对于不同难度的问题，需要的数据量不相同。一个理性的机器学习和数据 挖掘研究者，应该根据实际的问题，应用合适的数据量以及合适的算法。1.3国内外研究现状近年来，随着大数据的普及，低秩矩阵近似在理论研究中取得了巨大的进 展，在实际中也有着广泛的应用。在低秩矩阵近似的理论研究方面，核心问题是：对于一个特定问题，需要 多少数据，才能够解决该问题，以及设计怎样的优化算法能够快速高效地解决 低秩矩阵近似问题。在机器学习和数据挖掘的研充中，最具有代表性的低秩矩 阵近似问题就是矩阵补全问题。对于一个给定的矩阵，实际中只观察到该矩阵 的一部

27、分元素，需要利用这些观察到的元素来恢复出原来的矩阵。矩阵补全理 论研究的核心内容是，需要观察到多少元素，即给我们多少数据，才能够完美 恢复出原来的矩阵。假设矩阵的规模为nXTi,从直观上来讲，需要观察到所有 的疽个元素，才能够完美恢复原来的矩阵。哪怕观察到疽1个元素，都难以 准确预测唯一元素的值。Candes, Tao和Recht等人从核范数角度对矩阵补全问 题进行的深入而系统的研究表明，在原来矩阵的秩,比较小，且满足低一致性 的条件时，采用低秩矩阵近似技术，只需要观察到0(nr(logn)2)的数据量，就 能够完美恢复出原来的矩阵，详见工作4, 5, 6, 7的分析。Jain和Hardt 等

28、人从另外一个角度使用交替优化求解矩阵分解问题，并进一步来研究矩 阵补全问题的性质，也能够得到类似结论，即一旦观察到的数据量达到一个上 界，使用交替优化技术，就能够完美恢复出原来的矩阵。详见工作8, 9等。 因此，在一定条件下，只需要观察到部分的数据量，就能够完美解决矩阵补全 问题。在理论计算机科学和数值线性代数的研究中，核心问题是，需要多少的 数据量，一个低秩矩阵能够对原有的矩阵达到很好的近似，以及如何快速地求 解该低秩矩阵。其中最著名的问题当属CUR矩阵分解10和Nystromll矩阵 近似。CUR矩阵分解，是对原来的矩阵按一定的概率分布抽样部分的行和列， 使用抽样获得的行和列，计算得到一个

29、低秩矩阵，并使得该低秩矩阵对原来的 矩阵有着很好的近似。Nystrom方法主要对正半定的矩阵进行低秩近似，只需 要按一定的概率分布对矩阵进行列抽样。理论研究表明，只需要随机抽样原矩 阵一部分的行和列，通过计算，就可以求得一个非常好的低秩矩阵，能够对原 矩阵有很好的近似。详细的理论工作见【12, 13, 14, 15等。在数值优化 算法的研究中，主要研究如何设计高效的优化算法去求解低秩矩阵近似问题, 分为凸问题和非凸问题。在求解凸问题方面，主要解决基于凸的核范数作为低 秩惩罚项的矩阵补全问题。这些工作包括：工作16提出SVT算法，求解基 于核范数的低秩矩阵补全问题。工作17提出ISTA和FIST

30、A算法，求解目标 函数可分的凸问题，并进行加速。工作18提出ALM算法，基于增广拉格朗 日方法。工作19提出APGL算法，对矩阵补全问题进行加速求解。在求解非 凸问题方面，主要解决使用非凸的正则化项作为低秩惩罚或基于矩阵分解的矩 阵补全问题。这些工作包括：20提出NCADMM算法，求解基于MCP范数 2i的矩阵补全问题。22提出TNNR算法，求解基于截断核范数的矩阵补全 问题o 23提出OptSpace算法，求解基于矩阵分解的矩阵补全问题。24提出 Softlmpute-ALS算法，对求解基于矩阵分解的矩阵补全问题进行加速。在理论研究取得突破的同时，低秩矩阵近似在各个领域都有着广泛的应用。 在

31、推荐系统问题中，可以把用户对部分商品的打分矩阵看成是低秩的，基于用 户己经打分的商品数据，预测用户没有打分的商品，这就是一个典型的矩阵补 全问题。通过求解该问题，可以给用户推荐那些打分比较高的商品，从而提高 商家的利润25O在鲁棒主成分分析问题中26,视频中的背景或者不同光线 下的人脸可以组成一个低秩的子空间，可以利用低秩性质来进行背景前景区分， 或者进行人脸的对齐27o在Kernel近似问题中，由于在大数据问题中，数据 形成的Kernel矩阵28的维度非常大，既难以存储，又不方便计算。因此使用 一个低秩矩阵去近似复杂的Kernel矩阵，减少存储量并减少计算开销，同时又 能够保证原来的Kern

32、el矩阵在机器学习和数据挖掘任务中的诸多性质，在实际 问题中具有非常好的效果29o在多任务学习问题中30,由于任务和特征之 间的相关性，不同的任务和特征组成的矩阵可以认为具有低秩的性质，可用来 提高学习的准确性。在子空间分割问题中31,能够学习一个对原来数据矩阵 的低秩表示，并进一步在这个低秩表示上进行聚类，能够大幅度提高聚类的准 确性。在多标签学习问题中32,使用低秩矩阵近似，能够刻画标签之间的相 似关系，从而达到更好的预测效果。在主成分分析PCA问题中33,使用低秩 矩阵去近似原来复杂的数据协方差矩阵，可以加速PCA的求解算法。1.4本文主要工作与贡献本文的主要工作与贡献主要有如下几点：本

33、文在调研低秩矩阵近似问题现有模型与算法的基础上，使用更加简单、 直观、灵活的非凸加权核范数作为低秩惩罚项，并提出一种求解低秩矩阵 近似问题的统一的、非凸的框架。本文提出迭代收缩阈值与权值再分配算法(ISTRA)来求解上述非凸的低秩 矩阵近似问题。本文从理论上证明迭代收缩阈值与权值再分配算法(ISTRA)能够有效地收 敛到目标问题的局部最优解稳定点，并且有。(1/幻的次线性收敛速 度。在合成数据和实际图像数据上的实验表明，相比于其他算法，本文提出的 迭代收缩阈值与权值再分配算法(ISTRA)在矩阵补全和图像恢复任务上, 具有更高的精度和更快的速度。1.5本文组织结构本文共五章，具体的组织结构安排

34、如下：第一章主要阐述了低秩矩阵近似研究的背景与意义，并简单介绍了低秩矩 阵近似理论与应用的国内外的研究现状，以及本文的主要工作与贡献。第二章详细调研了目前学术界在低秩矩阵近似研究中的相关工作。首先详 细阐述了低秩矩阵近似理论方面的研究工作，主要包括：低秩矩阵近似的问题 定义，使用凸松弛方法解决低秩矩阵近似的核心问题，低秩矩阵近似与稀疏优 化的联系与区别，使用非凸松弛方法解决低秩矩阵近似问题的技巧，基于矩阵 分解的方法。然后详细介绍了低秩矩阵近似的应用。主要包括低秩矩阵近似在 推荐系统方向的应用，在鲁棒主成分分析问题中的应用，以及在其他一些机器 学习、数据挖掘任务上的应用。第三章详细调研了现今广

35、泛使用的一些求解低秩矩阵近似问题的优化算法， 主要分为凸优化方法和非凸优化方法。在凸优化方面，主要介绍了半定规划 SDP方法和Proximal梯度法。在非凸优化方面，主要阐述了交替优化方法和交 替方向乘子法ADMMo第四章提出了迭代收缩阈值与权值再分配算法(ISTRA)来求解低秩矩阵近 似问题首先提出使用加权核范数作为低秩惩罚项，并提出一般性的、统一 的、灵活的、非凸的低秩矩阵近似框架。接着详细阐述使用加权核范数作为低 秩惩罚项的非凸低秩近似问题的优化算法。主要包括：如何构造一个Proximal 问题，如何设计权值再分配策略，以及整个迭代收缩阈值与权值再分配算法 (ISTRA)的详细算法流程。

36、然后对本文提出的迭代收缩阈值与权值再分配算法 (ISTRA)进行详细的收敛性分析。主要包括：证明了算法每次迭代的步长是有 界的，分析了算法的主要收敛性质，即算法能够有效地收敛到目标问题的局部 最优解稳定点，同时也分析了算法的收敛速度，即算法能够有0(1)的次 线性收敛速度。另外，阐述了在步长满足一定条件时，ISTRA算法其实是一种 特殊的Majorization Minimization方法。最后，进行实验分析。主要在合成数据 集和实际图像数据集上进行矩阵补全实验，将本文提出的迭代收缩阈值与权值 再分配算法(ISTRA)与其它5种常用的矩阵补全算法进行对比。实验表明，本 文提出的ISTRA算法

37、在矩阵补全和图像恢复任务上具有更高的精度和更快的 速度。第五章对本文的主要工作内容进行总结，并对下一步工作进行展望。第二章低秩矩阵近似相关工作概述近年来，低秩矩阵近似问题已经成为机器学习，数据挖掘，计算机视觉, 理论计算机科学，数值优化，数值线性代数等诸多领域的研究热点。本章对各 个领域的低秩矩阵近似问题的相关工作进行调研。主要关注两个重点：低秩矩 阵近似的理论研究和低秩矩阵近似的应用研究。2.1低秩矩阵近似的理论研究本节主要阐述低秩矩阵近似理论方面的研究。2.1.1低秩矩阵近似的问题定义一般的低秩矩阵近似问题可以形式化表示为:min /(X) + A . rank(X)(2.1)其中，矩阵变

38、量函数/(X)是关于变量X的损失函数。rank(X)为 矩阵X的秩，作为正则化项，保证矩阵的低秩性质。人为超参数，用来平衡损 失函数和低秩。低秩矩阵近似问题的目标就是最小化目标函数(2.1),即通过优 化算法，求解一个最优的矩阵X*,使得在给定的平衡超参数人下，损失函数 /(X*)和矩阵X*的秩都足够小。最著名的低秩矩阵问题是矩阵补全问题，损失 函数为最小二乘：min ：|&(X &|% +人.rank(X)(2.2)其中A e要恢复的矩阵，|f为Frobenius范数，0,顶)色。为观察到的矩阵元素的集合。为投影算子，即观察到的元素值保持不变，未观察到的 元素值变为0,具体形式为耳(X)待=

39、otherwise(2.3)求出一个最优的低秩矩阵X*,使得X* 最终能够预测原矩阵A缺失的元素，即矩阵补全问题就是利用低秩结构， 在观察到的位置与原矩阵A足够接近， 用低秩矩阵X*去恢复有缺失值的矩阵。由于矩阵的rank函数不连续旦非凸, 因而求解直接用rank函数作为正则化项的问题(2.1)或(2.2)是NP-Hard的。为 了在多项式时间内高效解决该问题，需要对rank函数进行松弛，即寻找一个连 续的函数来近似rank函数，作为低秩正则化项。对rank函数的低秩近似主要分 为凸松弛和非凸松弛两类方法。2.1.2低秩矩阵近似的凸松弛方法最具代表性的凸松弛方法是使用核范数来近似矩阵的rank

40、函数。核范数形 式为|X|*,表示矩阵X的所有奇异值的和，是关于矩阵X的连续凸函数。工 作6证明了核范数|X|*是秩函数rank(X)在集合X e Rmxn : |X|2 (X) = &(&其中，用核范数|X|*,来代替矩阵秩函数rank(X)。为了方便求解，可以把约 束写到目标函数上，用超参数人来平衡损失函数和正则化项，即把(2.2)中的 rank函数换成核范数，可得矩阵补全的目标函数为；mjn ：|&(X_A)|% + |X|*(2.5)(2.5)式可以看成能够刻画噪声的矩阵补全，即观察到的元素可能含有噪声， 用最小二乘来拟合，一定程度上可以降低噪声的影响，而不用(2.4)式的等式 约束。

41、矩阵补全的目标函数(2.4)或(2.5)看上去十分简单而且直观，但要从理论 上证明通过求解目标函数的最优值，能够完美恢复出原矩阵4是十分困难的。 假设观察到mxn- 1个元素，即只有一个元素没有被观察到，我们只需要通过 观察到的mxn-1个元素去预测唯一的一个未观察元素。这个问题看似十分简 单，但如果对原矩阵A没有任何先验假设，最坏情况下，那个未能够观察的元 素可以是任意值，所以通过mxn-1个元素也不能完美预测唯一一个元素。所 以不对要恢复的矩阵做任何假设的矩阵补全问题是没有意义的。如何对要恢复 的矩阵作合理的假设，是矩阵补全理论的最大难点。假设的信息如果太多，矩 阵就很容易恢复，甚至不需要

42、利用低秩性质。信息太少，最坏情况下又不可能 完美恢复。Candes和Recht做出了矩阵补全理论的开创性工作4。他们对矩阵 补全问题中要恢复的矩阵A作出了合理的假设，使低秩矩阵补全成为一个定义 完备的问题。首先定义一致性的概念，对低秩矩阵进行刻画：定义2.1.1 (详见4).设。为IT1上的子空间，维度为r, R,为正交投影算子， 可将任意一个上的向量投影到子空间U中。子空间U的一致性(Coherence) 定义为：呻)=-max Puei2(2.6)T lin其中，占是第2个元素为/,其余元素为。的基向量。假设矩阵A e Rmxn的秩为r, SVD分解为4 =外&呻，其中Ur Rmxr 列正

43、交，即U，Ut = L，为左奇异向量矩阵；K Rnxr列正交，即 为右奇异向量矩阵；e RrXr 对角阵，对角线元素(71,(72 CTr都是正数，为 矩阵0的奇异值。根据定义2.1.1,可以求出矩阵4的列空间的一致性为：P(u)= y max |e泌|2T ltm矩阵4的行空间的一致性为：W)= 7 樨芝 liKII2T ltn那些列空间和行空间都有着低一致性值的矩阵有着很好的性质，比较容易通过 低秩性质来恢复。因此，工作4对需要恢复的矩阵A作如下两个假设：矩阵4的行空间和列空间具有低一致性的性质，即存在正数向，使得 max.(U),/(U) 四。矩阵A的左右奇异向量矩阵相乘所得矩阵UVT

44、e IRmxn中每个元素的绝 对值都是有界的，即存在一个正数内，使得每个元素的绝对值都小于或等 于“1廿茶。根据上面的论述，可得如下矩阵补全的完美恢复定理：定理2.1.1 (详见4),假设矩阵A e Rmxn的秩为r, A的奇异值分解为 满足上述假设和2。不失一般性，假设m Cmax(4腐四i,/zoTH)7ir(31og7i)(2.7)其中，。2,那么以至少1 - CH项的概率，矩阵补全问题仅初的全局最优值 是唯一的，并且等于矩阵A。若矩阵A的秩做够小，满足r 则a的界可以提高为。Z。0)舟勺3 log ?1)(2.8)根据定理2.1可知，如果需要恢复的矩阵A满足行空间和列空间都有低一 致性

45、的性质，并且满足假设2,使用核范数代替矩阵秩函数的问题(2.4)将会 以很大的概率有唯一的全局最优解，并且这个全局最优解就是需要恢复的矩 阵A。因此通过求解使用核范数作为低秩惩罚项的问题(2.4),将会以很大的概 率完美恢复出原矩阵A。当然，完美恢复，需要观察到的矩阵元素的数量超过 O(n12rlogn)这个级别，如果观察的元素数量太少，是不能够完美恢复的。可 知，当矩阵4的秩厂远小于矩阵维度n时，需要观察到的矩阵元素数量大约为 0(nL2 logn),这远远小于矩阵元素的总量0(n2)0因此，在一定条件下，使用 核范数作为低秩惩罚项来代替矩阵秩函数，利用矩阵的低秩性质，通过对矩阵 部分元素的

46、观察，从理论上是可以完美恢复出所有矩阵元素的。随后，Candes 和Tao将矩阵观察到元素数量的界减少到O(nr(logn)6) 50 Recht又将该界减 少到O(nr(logn)2),这是一个近似最优的界7。使用凸松弛方法核范数求 解低秩矩阵近似问题的好处是，求解的优化问题是凸问题，比较容易求解，能 够设计许多高效的优化算法，可以收敛到全局最优解，并且有收敛性的理论保 证34o 这些方法包括 SVT16, FISTA17, ALM 18, APGL 19等等。然而，核范数是有一定缺陷的。对于矩阵补全问题(2.4)和(2.5)来说，最 小化核范数，就是同时最小化矩阵X所有奇异值的和。矩阵X不

47、同奇异值的 大小一般不同，最小化核范数，对不同奇异值的惩罚力度是一样的。我们知道, 一个矩阵的性质可以由它的所有奇异值来刻画。要用一个秩小于等于左低秩矩 阵X去近似一个一般的矩阵可以形式化为：哩 n |A X|x(2.9)s.t. rank(X) A 0 了 1,rxi岛-if 知| A7P(W)= A f 1 - t/(Xy)+dt = 22A|a；i| 肯 otherwise在此基础上，工作20定义矩阵X rxn的7-norm为：1因|, =康以 X) = M*(X)(2.12)i=l其中，缶(X)为矩阵的第2大的奇异值，(X) = mX)(X)K为矩阵X所 有奇异值组成的向量，q = m

48、in(m,n)o从式(2.12)可以看出，|X|h其实是参数 人=1，变量为矩阵X奇异值的MCP惩罚项M1i7( A,问题1mjn -A-X + XX.(2.13)的全局最优解为SzM)=必久丁甘。其中，总,了 =成Qg(&“(1)为对角阵，对角线元素为传(A)订 (A) 7&,了(相山)= a；_A/7 订人 相A) V 7(2-14)(0 if %(4) A从定理2.1.2中的(2.14)式可以看出，使用|X|,作为低秩惩罚项，求解低秩 矩阵近似问题(2.13)时，最终求得的解的奇异值具有如下性质：当原矩阵的 奇异值足够大时，保持该奇异值不变；当矩阵A的奇异值为中等规模时，减小 该奇异值；

49、当矩阵A的奇异值足够小时，将该奇异值收缩为0。因此|X|7作 为低秩惩罚项时，对大的奇异值保持不变或惩罚力度小，对小的奇异值惩罚力 度大，因而是近似无偏的。因此，类似(2.5),使用|X|h作为低秩惩罚项的矩 阵补全问题为：min局(X - 4)作 + 人片(2.15)工作22使用了另一种非凸松弛的方法，采用截断核范数作为低秩惩罚项。 矩阵X 的截断核范数Xr定义为矩阵最小的q-r个奇异值之和，即|X|=史保X)5=丁+1其中g = min(m,n)o因为只惩罚最小的那些奇异值，避免对大奇异值的惩罚， 等价于加大了对小奇异值的惩罚力度，因而截断核范数也能够克服核范数奇异 值惩罚不平衡的问题。因

50、此，类似(2.5),使用截断核范数|X|作为低秩惩罚 项的矩阵补全问题为：min ”&(X 句伤 + ilXllr(2.17)在实际问题中，非凸松弛方法通常比凸松弛方法具有更好的低秩矩阵恢复 效果，同时对噪声也有更好的鲁棒性。但是求解非凸问题是十分困难的，迭代 算法很容易陷入比较差的局部最优解或者鞍点，或者需要耗费大量的时间才能 求出比较好的局部最优解。本文第四章将会提出一种更加简单、灵活、直观的 非凸松弛方法一使用加权核范数，即矩阵所有奇异值的加权和，作为低秩惩 罚项，并提出一种简单、高效的迭代收缩阈值与权值再分配算法(ISTRA)来求 解该非凸矩阵近似问题。本文从理论上证明该算法能够快速地

51、收敛到局部最优 解稳定点。同时，实验表明使用加权核范数和ISTRA算法，在实际问题中 能够取得最好的矩阵恢复效果。2.1.5基于矩阵分解的方法基于矩阵分解的低秩矩阵近似方法主要是由Srebro等人提出的最大间隔矩 阵分解，用来处理矩阵补全问题。基本形式为：啷 珂4 刀)=：I(X - ABt) + 加|$ + |田|%)(2.18)其中，A Rmxr, B Rnxr,使用AB；去近似原矩阵X。最大间隔矩阵分解 问题(2.18)对于变量4 B来说不是联合凸的，但固定其中一个变量，对另一个 变量是凸问题。因而，可以使用交替优化的方法求解该问题，每次迭代都是求 解一个脊回归问题，不需要进行耗时的SV

52、D分解。用最大间隔矩阵分解来求解 矩阵补全问题，在实际中有更快的速度，详细的优化方法见第三章。另外，关 于使用交替优化方法求解基于矩阵分解的低秩矩阵补全问题的理论保证详见工 作8和工作9。2.2低秩矩阵近似的应用低秩矩阵近似方法在机器学习、数据挖掘、计算机视觉等领域的学术界和 工业界都有着广泛的应用。2.2.1推荐系统低秩矩阵近似在推荐系统中具有极其重要的应用。推荐系统中，最著名的 问题要属协同过滤问题39如图2.1所示，是电影的打分矩阵。矩阵的每一行代表一部电影，每一列代表一个用户，用户会对电影进行打分。因为每个用户 看过的电影有限，不可能对所有电影进行打分，因此，电影打分矩阵是一个不 完全

53、的矩阵，里面有很多的缺失值。推荐系统的目的，就是要预测那些用户没 有打分的缺失值，从而给用户更好地进行电影的推荐，即把那些预测值分数较 高的电影推荐给用户。直接对这样稀疏的矩阵进行缺失值的预测是不可行的, 必须要利用矩阵的性质。从矩阵的行来看，不同的电影其实可能具有相似的性 质。例如，两部电影质量都比较高，那么用户对这两部电影的打分应该类似。 相反，两部电影质量很低，那么用户的打分普遍应该都比较低。从矩阵的列来 看，不同的用户也可能具有相似的性质。例如，某两个用户的兴趣相似，那么 这两个用户对电影的品位也应该类似，那么对电影的打分应该相似。因此，电 影的打分矩阵包含着诸多的冗余信息，只需要一部

54、分有代表性的、差异的用户 和一部分有代表性、差异的电影就能够确定整个矩阵，因此可以假设该矩阵具 有低秩的性质。那么推荐系统中的协同过滤问题，就是一个典型的矩阵补全问 题（2.2）。基于（2.4）和（2.5）的建模，使用核范数作为正则化项，可以很容易地 求解。推荐系统中另一种方式是使用矩阵分解方法进行低秩矩阵补全。如图2.2所 示，打分矩阵的行代表用户，列代表电影，是用户对电影的评分。一个打分矩 阵可以分解为两个低秩矩阵的乘积，如图2.2所示，第一个矩阵的列代表用户， 行可以看成某个隐藏的因素，矩阵的元素代表用户对该隐藏因素的评分。第二 个矩阵的列代表电影，行代表和第一个矩阵一样的隐藏的因素，矩

55、阵的元素代 表该隐藏的因素下，对电影的评分。因此，基于低秩矩阵分解的方法来进行推 荐预测，可以看做是在学习影响用户对电影打分的隐藏因子。可以使用最大间 隔矩阵分解（2.18）来进行求解。使用基于低秩矩阵近似的方法来解决推荐系统 问题的工作详见25, 40, 39等。2.2.2鲁棒主成分分析低秩矩阵近似另一个重要的应用是鲁棒主成分分析（RobustPCA）,工作26 对Robust PCA做了详细的理论和实际应用的阐述。传统的主成分分析PCA,在 数据存在大量噪声时，准确性非常糟糕，使用RobustPCA,就是为了能够对噪 声有很好的鲁棒性。Robust PCA的主要思想就是把数据矩阵分解为一个

56、低秩矩 阵和一个稀疏矩阵相加的形式：(2-19)min |心|* +刈 S|】s.t. L + S = M其中，山为数据矩阵，每一列代表一个数据。将数据矩阵M分解为低秩矩阵 L加上稀疏矩阵S。使用核范数作为低秩惩罚项，使用&范数作为稀疏惩罚项。 因此，（2.19）是凸问题，能够求得全局最优解。users12345678910111211355425442133241234354245425434225613324-unknown rating-rating between 1 to 5图2：电影打分矩阵Movie Feature Matnx (F x M)f, -102f2 4-41022Ra

57、ting Matrix (N x M)6 即 qQ 5图2.2:电影打分矩阵的分解Robust PCA在实际中有着非常广泛的应用。在视频监控中，可以把每一帧 图片转化为向量，则整个视频所有帧的向量组成一个矩阵可以把矩阵M 分解成背景矩阵与前景矩阵的和。由于视频的连续性，视频中每一帧的背景是 极其相似的，因此背景矩阵是低秩的。在视频监控中，一旦出现了人，则作为 前景，由于长时间的视频中，人出现在每一帧图片上的位置或频次是有限的, 因此前景可以看成稀疏矩阵。使用Robust PCA (2.19),就可以将视频中的背景 与前景分开，从而达到监控的目的。在人脸识别应用中，同一幅人脸在不同的 光照下，呈

58、现不同的状态，这加大了人脸识别的难度。可以将人脸矩阵转化为 向量，在不同光照下的所有人脸就构成一个矩阵同样的，把矩阵分解为背 景矩阵与前景矩阵的和。去掉不同光照下的人脸，本质上是极其相似的，因此 构成背景矩阵，是低秩的。而不同的光照就构成了前景矩阵，是稀疏的。使用 Robust PCA能够有效地解决人脸识别中的对齐问题27o2.2.3其它应用低秩矩阵近似方法还有许多其他的应用。在多任务学习中30,不同的任 务与任务之间有着某些相似性，不同的特征与特征之间也有着关联，因此多任 务学习中的任务、特征矩阵可以认为是低秩的，能够使用低秩矩阵近似的方法 求解。在多标签学习任务中32,相似的样本可以认为具

59、有相似的标签，因此 可以认为样本的多标签矩阵是低秩的，或者认为存在个隐变量矩阵关联样本 和标签，这个隐变量矩阵是低秩的。在子空间分割问题中31,直接对样本进 行聚类通常效果不好。借鉴低秩近似的思想，可以对原数据学习出一个低秩表 示，即用一个低秩矩阵去近似原来的数据矩阵，这样不仅能够刻画原数据矩阵 的主要性质，又能够去除原数据矩阵的冗余信息达到降维的目的，还能降低原 数据矩阵中噪声的影响。在原数据矩阵的低秩表示上，进行K-Means或谱聚类, 能够达到更好的效果。2.3本章小结本章调研了低秩矩阵近似问题理论和应用方面的相关工作。在低秩矩阵近 似的理论研究方面，主要包括低秩矩阵近似问题的形式化定义

60、，凸松弛方法的 理论分析，低秩矩阵近似问题与稀疏优化问题的联系，非凸松弛方法的使用技 巧，以及基于矩阵分解的方法。在低秩矩阵近似的应用研究方面，主要介绍低 秩矩阵近似在推荐系统，鲁棒主成分分析以及其他机器学习、数据挖掘方面的 应用。第三章低秩矩阵近似问题的优化算法随着低秩矩阵近似问题成为各个领域的研究热点，学术界设计了许多求解 低秩矩阵近似问题的优化方法，这些方法各有优缺点，适用于不同的数据和问 题，并且背后都有着巧妙的设计思想和理论基础。本章主要讨论求解低秩矩阵 近似问题的优化算法及其设计思想。主要包括凸优化方法和非凸优化方法。3.1凸优化方法本节主要讨论求解低秩矩阵近似问题的凸优化方法，即