2
$\begingroup$

Given an N-dimensional matrix A, I want to find an M<N dimensional index array I such that the submatrix A[I, I] has the maximum element sum over all such I vectors.

For example for 3-dimensional

A = 
1  2  3
4  5  6
7  8  9

and 2-dimensional index [1,3]

A[(1,3), (1,3)] = 
1  3
7  9

So basically this is a discrete optimisation problem with N choose M possible solutions.

Is there an efficient way to find the best solution?

Improve this question
$\endgroup$
  • 1
    $\begingroup$ Are the entries in $A$ all nonnegative, or could some entries be negative? $\endgroup$ – Brian Borchers Jan 10 '20 at 16:32
  • $\begingroup$ @BrianBorchers, $A$ is a correlation matrix, so potentially [-1,1]. But most use cases for me have only nonnegative elements (or small neg numbers can be treated as 0 considering estimation error). $\endgroup$ – jf328 Jan 13 '20 at 0:53
2
$\begingroup$

This is a binary knapsack problem which is known to be NP-hard. No efficient algo exists yet, but there are algos that can solve problem up to size of 400 variables (according to a paper published in 1999).

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.