在大型稀疏矩阵中寻找大型非稀疏子矩阵
Finding a large non-sparse submatrix in a large sparse matrix
我有一个非常大的 N x P 二进制矩阵，我想找到两组 R 和 C，它们包含构成最大可能密集（非稀疏，制作up of only 1's) 子矩阵，它至少满足 |R| 的一定大小和|C|。索引不一定是连续的。例如，最小 |R|=3 |C|=2，对于下面的矩阵，我想输出 R = {1,2,3} C = {2,5}.
0 1 1 0 1
1 1 0 1 1
0 1 0 1 1
有什么好的算法可以做到这一点吗？
我曾经想过将其建模为优化问题，我不知道是否可以用 AMPL 编写这样的问题以与任何开源求解器一起使用，例如，类似于 (不确定如何准确表述）：
但我怀疑它是 NP-hard 或需要幂集搜索。或者这个问题是否也可以看作是一个邻接矩阵并试图找到一个最大的集团？欢迎任何想法！
我最终意识到这个问题可以重新表述为一个二部图，然后最大尺寸子矩阵将等价于二部图中的最大边双群，这是一个 NP 完全问题。我发现 R 包 biclust 中的 BiMax 实现非常有用！
我有一个非常大的 N x P 二进制矩阵，我想找到两组 R 和 C，它们包含构成最大可能密集（非稀疏，制作up of only 1's) 子矩阵，它至少满足 |R| 的一定大小和|C|。索引不一定是连续的。例如，最小 |R|=3 |C|=2，对于下面的矩阵，我想输出 R = {1,2,3} C = {2,5}.
0 1 1 0 1
1 1 0 1 1
0 1 0 1 1
有什么好的算法可以做到这一点吗？
我曾经想过将其建模为优化问题，我不知道是否可以用 AMPL 编写这样的问题以与任何开源求解器一起使用，例如，类似于 (不确定如何准确表述）：
但我怀疑它是 NP-hard 或需要幂集搜索。或者这个问题是否也可以看作是一个邻接矩阵并试图找到一个最大的集团？欢迎任何想法！
我最终意识到这个问题可以重新表述为一个二部图，然后最大尺寸子矩阵将等价于二部图中的最大边双群，这是一个 NP 完全问题。我发现 R 包 biclust 中的 BiMax 实现非常有用！