t**o
发帖数: 64 | 1 不太清楚应该怎么归类。
题是这样的
有一个 100x100的correlation matrix，怎么样找20x20的主对角子阵，使得这个子阵
的所有元素之和最大。 |
s***t
发帖数: 49 | 2 减掉 前一个的左上，加上 后一个的 右下。
keep 当前最大。
复杂度： 20X20 + 20X80
【在 t**o 的大作中提到】
: 不太清楚应该怎么归类。
: 题是这样的
: 有一个 100x100的correlation matrix，怎么样找20x20的主对角子阵，使得这个子阵
: 的所有元素之和最大。
|
t**o
发帖数: 64 | 3 能不能具体一点？
子阵的选取行和列可以跳着来的。
【在 s***t 的大作中提到】
: 减掉 前一个的左上，加上 后一个的 右下。
: keep 当前最大。
: 复杂度： 20X20 + 20X80
|
d*****y
发帖数: 140 | 4 我怎么感觉这个问题的最优解是np-complete. 这个我再仔细想想。
不过有个找近似解方法：
let x = (x1,...,x100), x_i = 0 or 1 x_i=1 if 低i行or列属于你要找的子矩阵。
那么x 对应的子矩阵的所有元素之和可以表示为
S = x'Wx, where x'表示转置 and W是那么100的corr matrix.
问题转化为:
max S = x'Wx
subject to ,x_i=0,1 sum(x)=20.
relax 0-1限制，W的最大eigenvalue的eigenvector是实数解，所以一个近似取x的方法
是，把eigenvector里面的绝对值最大20个元素找出来，对应的row/col就组成了你要的
matrix了。note that 这个eigenvector一定是实数，而且的所有元素必定全非负或者
全部非正，所以你总能找20个最大出来。
【在 t**o 的大作中提到】
: 不太清楚应该怎么归类。
: 题是这样的
: 有一个 100x100的correlation matrix，怎么样找20x20的主对角子阵，使得这个子阵
: 的所有元素之和最大。
|
D**********d
发帖数: 849 | 5 实际上是选对角元的问题，可用递归思想。For example, 如果要选 98X98 的主对角子
阵，那可以证明，它一定是在 99X99 的主对角子阵里。
那么如何由 100x100 选 99X99?
对每个对角元，计算如果没有选该元的损失：然后找出最小的，其余的就是满足条件的
99X99 的了。
【在 t**o 的大作中提到】
: 不太清楚应该怎么归类。
: 题是这样的
: 有一个 100x100的correlation matrix，怎么样找20x20的主对角子阵，使得这个子阵
: 的所有元素之和最大。
|
