g******6
发帖数: 942 | 1 给定一个矩阵, 知道其中有两个以上的行/列 是相同的或成比例的. 所以矩阵不是满次的
. 有什么算法能够很快的发现这些行/列? 谢谢. | g******6
发帖数: 942 | 2 Get a correlation matrix for any two rows/columns in the matrix to see whether
the two are identical or proportional? That sounds a fine solution but the
comuptation overhead is a little large. The complexity of this solution is
roughly O(n^3). Is there any solution with O(n^2) complexity? Thanks. | w**a
发帖数: 1024 | 3 这样行不？
假设所有元素都是非负（如果有负的,一下算法也很容易修补）
先把所有列归一化 n^2
然后对第一行qsort,找到横向连续相同的那些column index section。
一个index section 定义为：
若第2,3,4列数值相同，就把[2,3,4]定义为一个index section.
显然，这些sections应该是disjoint continuous sections，很容易找到。
对这些cont. sections随机抽出一行再进行qsort，
如此反复 上6，7次后如果你觉得差不多了（这里面有个概率，应该<1%的概率，在6,7次
后都相同）。整个列进行比较。
whether
【在 g******6 的大作中提到】
: Get a correlation matrix for any two rows/columns in the matrix to see whether
: the two are identical or proportional? That sounds a fine solution but the
: comuptation overhead is a little large. The complexity of this solution is
: roughly O(n^3). Is there any solution with O(n^2) complexity? Thanks.
|
|
