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?

Improve this question
$\endgroup$
6
  • 1
    $\begingroup$ Are your matrices binary matrices? $\endgroup$
    – nicoguaro ♦
    Nov 29, 2017 at 18:55
  • $\begingroup$ @nicoguaro not necessarily $\endgroup$
    – Mikael
    Nov 30, 2017 at 15:48
  • 1
    $\begingroup$ I would use a norm of the difference of the two matrices, then. $\endgroup$
    – nicoguaro ♦
    Nov 30, 2017 at 15:51
  • $\begingroup$ @nicoguaro can you elaborate that on an answer? $\endgroup$
    – Mikael
    Nov 30, 2017 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, 2018 at 16:38

1 Answer 1

Reset to default
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.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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