I have a machine learning problem where I need to find the most dissimilar subset of rows/columns of an $m$-by-$m$ symmetric similarity matrix $M$ which minimizes the sum of the elements in an $n$-by-$n$ submatrix $N$, where $n < m$. In other words, by minimizing this sum, we find the most dissimilar rows/columns in $M$ that makes up $N$.

The values of $M$ are real, positive values between zero (dissimilar) and ones (similar). The diagonal consists of ones as the diagonal compares the same object with itself, meaning they definitely are identical. Furthermore, as the matrices are symmetrical, selecting row $i$ from $M$ also includes selecting column $i$ from $M$ (for $N$).

Take a 3-by-3 matrix as an example (i.e. $M$ with $m=3$):

\begin{pmatrix} 1 & 0.8 & 0.2 \\ 0.8 & 1 & 0 \\ 0.2 & 0 & 1 \end{pmatrix}

In this case, the first and second element are relatively similar (0.8), first and third are relatively dissimilar (0.2), and second and third are completely dissimilar (0). Assuming $n=2$, there are three possible ways to construct the submatrix $N$:

  1. Select first & second row/column:

\begin{pmatrix} 1 & 0.8 \\ 0.8 & 1 \end{pmatrix}

  1. Select first and third row/column:

\begin{pmatrix} 1 & 0.2 \\ 0.2 & 1 \end{pmatrix}

  1. Select second and third row/column:

\begin{pmatrix} 1 & 0 \\ 0 & 1 \end{pmatrix}

For this particular case, we know that the third alternative minimizes the sum. However, scaling this problem to $m=5000$ and $n=400$ makes the problem impossible to compute as the number of possible submatrices gets insanely large.

I was initially considering using the Monte Carlo method, but I'm thinking that there might be a more elegant way to do this. Do you have any pointers?


Unfortunately this problem is NP-hard, meaning the best exact algorithm you can hope for will take exponential time in the worst case.

It is NP-hard because any algorithm that would solve this problem can also be used to solve the NP-hard problem Independent Set (IS), in which we have a graph $G = (V, E)$ and an integer $k$, and ask whether there is a subset $X \subseteq V$ of $k$ vertices such that no pair of vertices in this subset are adjacent. Given any algorithm for solving your problem, any instance $G$ of IS can be solved by giving this algorithm the adjacency matrix for $G$, in which every element is 1 (indicating a pair of vertices connected by an edge) or 0 (indicating a pair of vertices that are not) as input, together with $N=k$; there is a size-$k$ independent set in $G$ if and only if there is a subset of $N$ rows/columns in the matrix having sum $N$ (i.e., all diagonal elements are 1 and the rest are 0).


You can try using integer linear programming. It isn't a magic silver bullet and probably won't find the optimal solution in a reasonable amount of time, but if you give the ILP solver a time budget, it might find a reasonable solution.

A formulation as ILP: use zero-or-one variables $x_i$, where $x_i=1$ means that the $i$th row and column is selected. Introduce zero-or-one variables $y_{i,j}$, along with inequalities $y_{i,j} \le x_i$, $y_{i,j} \le x_j$, $y_{i,j} \ge x_i + x_j - 1$. Then your objective is to minimize $\sum_{i,j} M_{i,j} y_{i,j}$, subject to the requirement that $\sum_i x_i = n$.


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.