一种推广的CUR矩阵分解算法：更低的时间复杂度和更好的紧界王书森，张志华浙江大学，计算机科学与技术学院中国，杭州310027E-mail：{wss,zhzhang}@zju.edu.cn摘要CUR矩阵分解是对一般矩阵进行Nystrom逼近的一个重要推广，它能够近似的逼近于任何列数和行数较小的数据矩阵。在本文中，我们提出了一种新的随机CUR矩阵分解算法，该算法能够达到预期的相对误差限。而本文的优点就在于该算法的相对误差是现有CUR算法的三分之一倍：更好的紧界，更低的时间复杂度，并且该算法能够避免在主内存中对数据矩阵进行维护。最后，我们用真实数据通过几次实验验证了改进的CUR算法的相对误差限优于现有算法的相对误差限。1.引言在当今社会，随着股票、基因、网络文件、图象和视频的发展，从中提取的矩阵正日益变得庞大，这无疑给现有的数据分析带来新的挑战。而目前已开展的大部分工作主要专注于操作、理解以及翻译大型矩阵。在许多情况下，矩阵分解主要用于将矩阵分解为带有压缩式和信息性的矩阵，以便于计算与处理。一个基本的方法就是奇异值分解，该方法是对数据矩阵进行分解的最低秩逼近。例如奇异值分解在特征脸[20、21]和潜在语义分析[4]中的应用已被证明它是一种非常成功的算法。然而，由奇异值分解产生的基向量几乎没有任何实际意义，这使得我们理解和翻译数据矩阵变得很困难。在参考文献[10、19]中给出的例子很好的证明了这一观点，即向量{1/2（年龄），1/√2(高度)，1/2（收入）}是取自人体特征的数据集，它表示的是人体显著的不相关外貌特征的总和，它并不是人体特有的信息。参考文献[17]的作者也声称：“试着去研究一种对任何实验向量都能够找出它们基向量的方法将会是一件很有趣的事情，当然，前提是必须使用实际数据向量而不是人工向量，因为人工向量几乎没有什么意义。”因此，对于一个列数较小或者行数较小的矩阵，如果能够找出一种能够近似代替它的矩阵的方法，那将是很有意义的。CUR矩阵分解便给出了这一方法，并且我们已经证明了它在高维数据分析中是一种很有用的方法，具体证明请参考[19]。给定矩阵A，利用CUR分解，从A的列向量中选定适当的子集构造出矩阵C，再从A的行向量中选定适当的子集构造出矩阵R，最后通过A=CUR选出最佳近似矩阵U.典型的CUR分解算法是通过两个阶段来完成的，第一阶段是列向量选择阶段，第二阶段是行向量选择与列向量选择同时进行。因此，第二阶段比第一阶段更加复杂。CUR矩阵分解问题在参考文献[7,8,9,10,12,13,16,18,19,22]中研究的比较广泛。其中研究最广泛而且最著名的应该是[10]，[10]中的作者设计了一种随机CUR分解算法，又名“子空间采样算法”。特别值得注意的是，该算法在高概率条件下具有1的相对误差率。不幸的是，所有现存的CUR分解算法都要求矩阵具有大量的列数和行数，并且列数与行数充分接近。例如，设A为nm矩阵，mn,minkrank(A)，子空间采样算法要想在高概率条件下使结果达到1的相对误差率，必须要求矩阵具有)(64k或)ln(24kk的行数。并且该算法的计算次数至少都得是A的奇异值分解的计算次数，即}).,{min(22nmmn因此该算法不太适用于大型矩阵。在本文中，我们提出了一种新的CUR分解算法，该算法无论在理论上还是在实际中都优于子空间采样算法。特别的，我们在定理5中证明了这种新颖的随机CUR分解算法具有比子空间采样算法更低的时间复杂度和更紧缩的理论误差限的结论本文的其余部分安排如下：第三部分介绍了几种现存的列选择算法和子空间采样算法；第四部分介绍和分析了我们新提出的CUR算法；第五部分则通过实验，对比了我们提出的新CUR算法与子空间采样算法的优缺点。2.符号说明对于矩阵nmijR)a(A，设(i)a表示矩阵A的第i行，ja表示矩阵A的第j列，ji,ij|a|||A||表示A的1-范数，2/1ji,2ijF)a(||A||表示A的Frobenius范数，2||A||表示A的谱范数。mI表示m阶单位矩阵，mnO表示nm阶零矩阵，kA,TkA,kA,kA,TkA,kA,0iTi,Ai,Ai,AATAAVUVUvuVUA表示A的奇异值分解，这里rank(A)，kA,TkA,kA,V,,U表示对应于最大的奇异值k的矩阵，我们记kA,TkA,kA,kVUA，A,TA,A,VUA表示A的Moore-Penrose广义逆。3.相关工作3.1节介绍了几种与本工作相关的相对误差列选择算...
