# Which are some good algorithms and heuristics to calculate the similarity between two matrices?

Say I have a matrix like this:

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

And this one:

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

The difference between this two matrices is 2 elements in 12, or 16,67%. So, I can say that they have 83,33% similarity.Which are some good algorithms or heuristics(I don't need more precision than +- 5%) to get this number(the 83,33% on this case) other than the naive algorithm that walk both matrices and compare each element using a nested loop structure?

• Are your matrices binary matrices? – nicoguaro Nov 29 '17 at 18:55
• @nicoguaro not necessarily – Mikael Nov 30 '17 at 15:48
• I would use a norm of the difference of the two matrices, then. – nicoguaro Nov 30 '17 at 15:51
• @nicoguaro can you elaborate that on an answer? – Mikael Nov 30 '17 at 16:01
• How is similarity defined for non-binary matrices? Do you just check if the elements are equal or not? Or do you take into account somehow the magnitude of their difference? – Federico Poloni Mar 20 '18 at 16:38

The short answer is: "it depends".

But the first question that is not entirely clear from the question is a definition of similarity between two matrices. Technically there is a term Matrix similarity, but there is certainly nothing common between it and what you are asking.

To justify the inquiry about the similarity definition, consider three matrices:

$$A_1=\left[\begin{array}{ccc} 1 &0 &0 \\ 1 &1 & 0 \\ 1 & 1 & 1 \end{array}\right], \quad A_2=\left[\begin{array}{ccc} 1 &1 &1 \\ 0 &1 & 1 \\ 0 & 0 & 1 \end{array}\right],\quad A_3=\left[\begin{array}{ccc} 1 &0 &0 \\ 0 &1 & 0 \\ 0 & 0 & 1 \end{array}\right]$$ Here, $A_1 = A_2^T$. However, according to element-wise similarity definition you proposed, the difference between them will be huge: 2/3. Moreover, the identity matrix $A_3=I_3$ has a smaller difference of just 1/3.

Other examples demonstrating more complicated similarities/differences between two matrices can be shown.

Nevertheless, let's assume that we are just interested performing strict element-to-element in two matrices. A natural metric would be the one that nicoguaro suggested: $\left|\left| A_1-A_2 \right|\right|_{1,2,F,\ldots}$ Here, $1,2,F,\ldots$ in the subscript correspond to different matrix norms (1-norm, 2-norm, Frobenius norm, etc.) Unfortunately, the calculation of the norm requires at least browsing through all the elements of the matrix $A_1-A_2$. And it will be not easy to come up with the speed-up of that calculation without knowing where your matrix comes from.

There are various algorithms that will be able to estimate your norm, provided some information:

But I think all that is an overkill. At this moment, there is no justification why a naïve algorithm for calculating a norm of a matrix $A_1-A_2$ is not sufficient. Since, even if the size of the matrix is large, you are storing them in the memory anyway; thus, you certainly can afford to compute at least the Frobenius norm.