限秩最大子集问题

在Internet和其他的很多信息量高度集中的媒体上，信息检索（Information Retrieval，IR）正日益成为一个重要的课题。在潜在语义分析（Latent Semantic Analysis，LSA）方法中，相关子集的选择与低秩矩阵逼近起着重要和关键的作用。本文讨论的限秩最大子集问题（LRMS）便是子集选择问题的一种：对于原来的一个大矩阵A∈Rm×n，和给定的一个正整数p≤r=rank（A），考虑怎样在A中选择一个列子矩阵A0，使得A0的秩为p，且A0是所有A的秩p子矩阵中列数最大的一个。 针对这样一个问题，人们一般采用的是枚举方法，但是枚举法是一个指数时间算法。在实际计算中，计算量很大，不能满足实时性的要求。在第三章中，我们用分而治之的方法来求解LRMS问题。首先，我们给出了一个LRMS问题可以用分而治之方法来求解的充分必要条件和一个可判定条件（充分条件），当原矩阵A是列可分时，LRMS问题可以用分而治之方法来求解。在此基础上，我们进一步给出了判断一个矩阵是列可分的可分准则，此可分准则利用数值代数中常用的QR分解得到。由此，我们得到一个求解LMRS问题的分而治之方法。数值试验表明，分而治之方法比枚举法要大大节省计算时间。 实际上，在第三章中，我们只是解决了原矩阵A是列可分的LRMS问题，那么对于原矩阵A是列不可分的LRMS问题，该如何求解呢?第四章中，我们就针对原矩阵A是列不可分的LRMS问题，提出一个贪婪算法。贪婪算法的思想是：每次“最贪婪的”从剩下的子矩阵中选择一列添加到已知的子矩阵中，或“最贪婪的”从已知的子矩阵中消去一列。这分别构成向前贪婪算法和向后贪婪算法。并且，结合这两种贪婪算法，我们还提出一个混合贪婪算法。这些贪婪算法（特别是向后贪婪算法和混合贪婪算法）都能够很好的得到所需的最优子矩阵。 最后，本文还讨论了数值秩情形的LRMS问题。对于此情况，我们前面提出的算法仍然是适用的。随后，我们还提出了一些还有待解决和可以进一步考虑的问题。