0
$\begingroup$

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?

$\endgroup$
  • 1
    $\begingroup$ Are your matrices binary matrices? $\endgroup$ – nicoguaro Nov 29 '17 at 18:55
  • $\begingroup$ @nicoguaro not necessarily $\endgroup$ – Mikael Nov 30 '17 at 15:48
  • 1
    $\begingroup$ I would use a norm of the difference of the two matrices, then. $\endgroup$ – nicoguaro Nov 30 '17 at 15:51
  • $\begingroup$ @nicoguaro can you elaborate that on an answer? $\endgroup$ – Mikael Nov 30 '17 at 16:01
  • $\begingroup$ 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? $\endgroup$ – Federico Poloni Mar 20 '18 at 16:38
2
$\begingroup$

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.

$\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.