Find combination of columns and rows in matrix to get the highest sum submatrix.

Hey everyone, thanks for taking the time to read and help. I really appreciate it.

I have a binary matrix A = [40000x40000], and I want to find a 12x12 submatrix which has the highest sum. It should rather be a combination of different columns and rows.

I'm drawing a complete blank right now on how to find a combination that gives X number of submatrices with high sums. If the columns where fixed it would be easy, but I'm not sure how to find a combination without using 'trial and error' or just running a loop through the whole matrix. I guess that would be ok, since I could just save the results.

Can anyone help with a smart solution?

Thanks for reading and helping, I really appreciate it!!

Best regards, Kasper

Answer 1

[Stephen23]

This sounds like a version of the knapsack problem, where you are trying to maximize some value (the sum) with a limit on how many columns+rows that are selected. There are several tools on MATLAB File Exchange that claim to help solve this, otherwise an internet search will give you plenty of other algorithms to try out.