原创力 秩极小化：理论、算法和应用.docxVIP

PAGE PAGE # 秩极小化：理论、算法与应用本文得到国家自然科学基金资助.1对于压缩传感.卩了前面还会有一个压缩测虽矩阵.这里不作赘述 本文得到国家自然科学基金资助. 1对于压缩传感.卩了前面还会有一个压缩测虽矩阵.这里不作赘述? 2 Netflix 家现频租赁公司.拥有很多用户对视频的评价.但这个用户/视频评价矩阵非當稀统。该公可提供100 万美元奖金希望能够把预测用户对视频的评价的准确率提高10%.以便有针对性地推荐.从而提高营收。见 hiip:/// 林宙辰 北京大学机器感知与智能教育部重点实验室，北京100871 引言 稀疏表示(Sparse Representation) [Elad2010]?H￡fc^f^感(Compressed Sensing) [EK2012]是目 前信号处理和机器学习领域的热门课题。所谓稀疏性.指的是有意义的倍号在适当选取的一组过完 备基(Ovcrcompicic Bases,或称为字典，Dictionary)下可以只用其中少数几个基来表达。写成数学 表达式就是： 如果W^xn(mn｝是一个合适的字典，y是有意义的倍号，X。是y在下的最稀疏 表示，即： 旺=arg min ||x||0, si. y = Wx, X 则IkolL《加，其中UHL表示x中非零元的个数。 上面的描述是基于向虽的稀疏性來刻画的。但在实际应用中，我们将而临着各种各样的数据. 如图像、视频和基因微阵列(Microarray),它们天然就是矩阵甚至是张虽。于是我们就自然而对着 一个问题：如何度虽矩阵和张鱼的稀疏性？如果套用向虽:的稀疏性.把它们强行展开成向尼、按照 向虽來处理，势必破坏数据内在的结构，在很多问题上就会行不通。比如图像或视频压缩.没有一 个人会把图像或视频当作向虽来压缩，因为这样没有充分利用空间和时间上的相关性。再如Nclflix 挑战2(图1),如果把用户/视频评价矩阵直接按向虽处理，必然导致用户未评价的视频都是她/他不 喜欢的视频这样不合理的结论。 本文主要讨论矩阵的稀疏性。那么什么才是矩阵的稀疏性度虽:呢？回想上而的两个例子，大家 很容易都能想到要充分利用图像或矩阵的行及列之间的相关性。另外，作为流形学习[LV2007]的基 本假定，我们知道真实数据都是存在于高维空间中非常低维的流形上的?而且往往都可以用低维的 子空间來近似，比如前几个主分虽所张成的线性子空间。行列相关性和低维子空间都共同指向了线 性代数的一个基本概念：矩阵的秩。以上的例子都提示我们：秩是矩阵稀疏性的合理度量。事实上, 秩是非常强的全局约束。一个7WX,/矩阵如果没有任何约束.它将有加〃个自由度：如果它的秩是 则自由度将下降为r(w + 77-r)o因此.秩是很好的针对矩阵的正则化子(regularizer)e ☆22★ ☆ 22 ★ ☆ 图1 Nciflix挑战。需要预测用户对其未评价过的视频的喜好程度。 正如其他“新鲜”事物(如稀疏表示)一样，秩其实在统计学中早已被用作矩阵的正则化子. 如减秩回归(Reduced.Rank Regression) ［Tsol981］：在三维立体视觉里，秩约束更是随处可见 ［MSKS2004］。但是E. Candes等人的工作赋予了秩极小化新的内涵，另外传统的己经获得巨大成功 的稀蔬表示和压缩传感理论向矩阵推广的需求也是秩极小化焕发新春的内在动力。 本章的主旨是简要介绍秩极小化的理论.算法与应用。第2节将介绍秩极小化的几个主要数学 模型。第3节将介绍一些基本理论结果。第4节将介绍求解秩(核范数)极小化的高效算法。第5 节将介绍秩极小化的一些典型应用。第6节将总结本章。 主要数学模型 如前所述，秩很早以前就己被应用于某些领域.如统计学里的减秩回归［TSO1981］和三维立体视 觉［MSKS2004］c但是秩极小化重新赢得许多学者的注意却是近几年的事° 2008年，压缩传感发明人 之一.斯坦福大学教授E. Candes考虑了矩阵填充(Matrix Completion, MC)问题［CR2009］：已知某 矩阵D在某些位置的值，可否恢复出该矩阵？显然这个问题的答案是不确定的.于是他建议选秩最 小的那个解/： min rank), sJ. 7ra(D) = 7ra(A\ Ju 其中Q是己知值的矩阵元素的位迓的集合，耳,是保留位置在Q里的矩阵元素的值.其他位置填0 的投影算子。稍后，E. Candes又进一步考虑了带噪声的MC问题［CP2010］： minrank(J), sJ. |血Q)-%(/)||；? ⑵ 2009年，Chandrasckaran等人［CSPW2009］和Wright等人［WGRM2009］同时提出了鲁棒主元分析 (Robus