0
$\begingroup$

We have well established theory for measuring the information content and randomness of binary strings. Notions such as Shanon entropy and Kolmogorov-complexity were developed for binary strings.

For a binary square matrix, it is not sufficient to just convert the matrix into binary string and measure its information content or its randomness since naive unraveling of the binary matrix into binary string would lose the adjacency information in each row and in each column.

My question: What are the analogous notions for measuring the information content and randomness of binary square matrix?

$\endgroup$

1 Answer 1

Reset to default
2
$\begingroup$

You claim that unraveling the (square) matrix into a vector loses some information. However, the transformation is bijective - given the $n^2$ vector, you can easily reconstruct the $n\times n$ matrix. Information theory is oblivious to representation. If you have some random variable $X$ and some bijection defined on its domain $f$ then $H(X) = H(f(X))$. So classical information theory covers the case of matrices.

$\endgroup$
8
  • $\begingroup$ Thanks Yuval. I guess you are assuming that $f$ is known or it is a fixed function $f$. Given $n^2$ string, there are many possible matrices depending on the unraveling method (scan order). Don't you agree? $\endgroup$
    – Mohammad Al-Turkistany
    Apr 27, 2013 at 16:23
  • 2
    $\begingroup$ It doesn't matter. When calculating the entropy of a random matrix, you use the formula $-\sum_x \Pr[A = x] \log \Pr[A = x]$. There is no mention here of any kind of representation. If it helps in calculating the entropy, you can choose whatever representation you wish, but it's only for convenience. And it's you who gets to choose. $\endgroup$
    – Yuval Filmus
    Apr 27, 2013 at 16:49
  • $\begingroup$ I still argue that a $n^2$ binary string with H-adjacency and V-adjacency defined by some function holds more information than just plain $n^2$ binary string. I hope my motivation is clear now. $\endgroup$
    – Mohammad Al-Turkistany
    Apr 27, 2013 at 18:35
  • 1
    $\begingroup$ No it doesn't. The entire point of information theory is to define intrinsic measures of information that don't rely on what you think is important in your data. $\endgroup$
    – Yuval Filmus
    Apr 27, 2013 at 18:39
  • 1
    $\begingroup$ In what sense would they have different information content? You have to spell that out. In the standard sense, the corresponding vectors would have exactly the same entropy. $\endgroup$
    – Yuval Filmus
    Apr 28, 2013 at 13:54

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.