在大型稀疏矩阵中找到"最大"密集子矩阵

Question

给定一个大的稀疏矩阵(比如说10k +乘以1M +),我需要找到形成密集矩阵(所有非零元素)的行和列的子集,不一定是连续的.我希望这个子矩阵在某些宽高比约束内尽可能大(不是最大和,但是最大数量的元素).

这个问题是否有任何已知的确切或aproxamate解决方案？

对谷歌的快速扫描似乎给出了很多接近但不完全的结果.我应该寻找什么条款？

编辑:只是为了澄清; 子矩阵不需要是连续的.事实上,行和列顺序是完全任意的,因此邻接完全无关紧要.

基于Chad Okere的想法的想法

Answer 1

我想你想要这样的东西。你有一个像这样的矩阵

1100101
1110101
0100101

您想要第 1、2、5、7 列以及第 1 行和第 2 行，对吗？该子矩阵为 4x2，包含 8 个元素。或者您可以使用第 1、5、7 列和第 1、2、3 行，这将是一个 3x3 矩阵。

如果您想要一个“近似”方法，您可以从单个非零元素开始，然后继续查找另一个非零元素并将其添加到行和列列表中。在某些时候，您会遇到一个非零元素，如果它的行和列被添加到您的集合中，您的集合将不再完全非零。

因此，对于上面的矩阵，如果添加 1,1 和 2,2，则集合中将包含行 1,2 和列 1,2。如果您尝试添加 3,7 将会导致问题，因为 1,3 为零。所以你无法添加它。不过，您可以添加 2,5 和 2,7。创建 4x2 子矩阵。

您基本上会进行迭代，直到找不到更多要添加的新行和列。这也会让你得到局部最小值。您可以存储结果并从另一个起点重新开始（可能不适合您当前的解决方案）。

当一段时间后你找不到更多的时候就停下来。

显然，这需要很长时间，但我不知道你是否能够更快地做到这一点。