MATLAB:查找矩阵的缩写版本,最小化矩阵元素的总和

Question

我有一个151 × 151的矩阵A.它是一个相关矩阵,因此1主对角线上有s,主对角线上方和下方有重复值.每行/每列代表一个人.

对于给定的整数,n我将寻求通过踢出人来减小矩阵的大小,这样我留下了一个n-by-n最小化元素总和的相关矩阵.除了获得缩写矩阵之外,我还需要知道应该从原始矩阵中引导的人的行号(或者他们的列号 - 它们将是相同的数字).

作为我的起点A = tril(A),它将从相关矩阵中去除冗余的非对角线元素.

因此,如果n = 4我们上面有假想的5- by- 5矩阵,那么很明显人5应该被踢出矩阵,因为那个人正在贡献很多非常高的相关性.

同样清楚的是,人1不应该被踢出,因为那个人贡献了很多负相关,从而降低了矩阵元素的总和.

我明白这sum(A(:))将总结矩阵中的所有内容.但是,我很清楚如何搜索最小可能的答案.

我注意到一个类似的问题.找到具有最小元素和的子矩阵,它有一个强力解决方案作为接受的答案.虽然这个答案很好,但对于一个151 × 151的矩阵来说这是不切实际的.

编辑:我曾想过迭代,但我认为这不会真正最小化简化矩阵中的元素总和.下面我有一个粗体的4- by- 4相关矩阵,边缘上有行和列的总和.很明显,n = 2最优矩阵是涉及人1和4 的2乘2的单位矩阵,但根据迭代方案,我会在迭代的第一阶段踢出人1,因此算法得出一个解决方案不是最佳的.我写了一个总是产生最佳解决方案的程序,当n或k很小时它运行良好,但是当试图从151 × 151矩阵制作一个最佳的75- x- 75矩阵时,我意识到我的程序需要数十亿年终止.

我含糊地回忆说,有时这些n选择k问题可以通过动态编程方法解决,避免重新计算的东西,但我无法弄清楚如何解决这个问题,也没有谷歌搜索启发我.

如果没有其他选择,我愿意牺牲精度以获得速度,或者最好的程序需要一周以上才能生成精确的解决方案.但是,如果能够生成一个精确的解决方案,我很高兴让程序运行长达一周.

如果程序无法在合理的时间范围内优化矩阵,那么我会接受一个解释为什么n选择此特定类型的k任务无法在合理的时间范围内解决的答案.

Answer 1

根据 Matthew Gunn 的建议以及 Gurobi 论坛上的一些建议，我提出了以下函数。看起来效果很好。

我会授予它答案，但如果有人能想出效果更好的代码，我会从这个答案中删除勾号，并将其放在他们的答案上。

function [ values ] = the_optimal_method( CM , num_to_keep)
%the_iterative_method Takes correlation matrix CM and number to keep, returns list of people who should be kicked out 

N = size(CM,1);  

clear model;  
names = strseq('x',[1:N]);  
model.varnames = names;  
model.Q = sparse(CM); % Gurobi needs a sparse matrix as input  
model.A = sparse(ones(1,N));  
model.obj = zeros(1,N);  
model.rhs = num_to_keep;  
model.sense = '=';  
model.vtype = 'B';

gurobi_write(model, 'qp.mps');

results = gurobi(model);

values = results.x;

end