1
$\begingroup$

Given a matrix $X$ of dimensions $n*d$ my goal is to determine the amount of resources used by this matrix. The definition for resources used here is flexible, but relates to the amount of information encoded in the matrix. That is, a a completely uniform matrix uses very little resources as it can be compressed quite easily.

This relation between resources used and information contained reminded me of entropy. However, my field of specialization is computing hence I'm wondering if there's some better concepts I'm missing. The problem with calculating entropy is that it requires the distribution of the random variable $X$ (here my matrix entries) however I do not have access to such a distribution, nor can I reasonably build one given the single matrix (in the context of my problem).

I also thought of SVD, and how information contained can be related to the variance of the data, however I moved away from that solution as measuring the amount of resources used would require me to know the true distribution (ie. the mean and variance when 100% of information is conserved) which I do not have.

What would be the best way to quantify the amount of resources used, or the amount of information used by/contained in a matrix?

Edit: Some context around my problem. I am developing a machine learning algorithm which seeks to build the optimal architecture for a neural network given some resource constraint. In my setting the resource constraint is amount of information encodable, equivalently, space available for the model to use in memory. To do this however I need to calculate the amount of resource the model uses. It isn't sufficient for me to say it's taking a certain amount of memory because that tells me nothing about the actual content of the information. Information in a neural network is encoded in a weight matrix, where there is one weight for each layer. $X$ is one such weight matrix.

Edit 2: The neural network weights are can be seen as an approximation to the real distribution of the inputs. We don't have the actual distribution, so this is our best guess. Information here is meant to be the relative difference between the unknown true distribution and our best guess distribution. I believe one could relate this to the free energy concept in a restricted Boltzmann machine. My goal here is to say, I have encoded $Z$% of the true distribution in my approximation, and this approximation can be stored in $Y$ amount of bits at best. So I know how much resource this information takes.

$\endgroup$
8
  • $\begingroup$ By "model" in your edit you mean "neural network"? And how do you quantify "optimal"? Anyway, your problem seems to boil down to guessing what the inputs and outputs of that neural network will be. You need to assign a probability distribution for them, based on any prior information and data you have (there's no such thing as the "true" distribution). From them you can guess what the possible weights (by backprop, for example) could be – another probability distribution. $\endgroup$ – pglpm May 5 '20 at 23:15
  • $\begingroup$ Check out these papers by MacKay, they deal with something close: inference.org.uk/mackay/PhD.html Chapters 2 and 3. $\endgroup$ – pglpm May 5 '20 at 23:23
  • $\begingroup$ @pglpm I don't think it's necessary to have a specific definition for optimal here. Model does refer to the neural network. I don't see the relation between guessing the inputs/outputs and my problem. Very simply I'm looking to quantify the amount of information encoded in the network to be able to quantify the amount of resources it would take (since both are correlated). $\endgroup$ – donkey May 6 '20 at 2:34
  • $\begingroup$ The problem is that there's no such thing as "the amount of information encoded in something" that you could measure with some kind of meter. For example I can't ask "what's the information encoded in the numbers (4, 7.1, 53)?". The question has no meaning whatsoever. Information is a relative notion that depends on what you know, what you don't know, and what are the objects concerned by this knowledge. Please take a look at the books by MacKay or by Cover & Thomas. $\endgroup$ – pglpm May 6 '20 at 6:21
  • $\begingroup$ I see what you're getting at. I have clarified with some more rigorous detail what I'm looking for. $\endgroup$ – donkey May 6 '20 at 15:47
1
$\begingroup$

A very commonly used measure of "information" in a matrix is the rank.

A nice way to see that this gives us a good measure of the "information contained" in the matrix is via the SVD. In particular, the rank of a matrix is the number of non-zero singular values. If these non-zero singular values are $\sigma_1,\sigma_2,\dots,\sigma_r$, then using a "compact SVD", we can recover the original matrix $A$ using these $r$ numbers and $2r$ "singular vectors". In particular, we have $$ A = U \Sigma V = \pmatrix{u_1 & \cdots &u_r} \pmatrix{\sigma_1 \\ & \ddots \\ && \sigma_r} \pmatrix{v_1 & \cdots & v_r} \\ = \sigma_1 u_1v_1^T + \cdots + \sigma_r u_1 v_1^T. $$ As a sanity check, note that the "uniform matrix" (i.e. the matrix whose entries are all equal) has a rank of $1$, which is indeed the lowest possible rank. A weakness to this metric is that the rank can only be a whole number (unlike entropy, for instance).

The idea of low-rank representing low information-content is the central idea behind applications of low-rank matrix completion to machine learning, which is a highly active area of research. It is also the main idea behind principal component analysis, which was in turn the idea behind one of the first facial recognition algorithms.


Another such measure is the "von Neumann entropy", which (as its name suggest) extends the idea of entropy to be about matrices. In its usual usage, von Neumann entropy is specific to positive definite symmetric matrices, but we can extend this idea to arbitrary matrices as follows:

Suppose that $A$ is a matrix with singular values $\sigma_1,\sigma_2,\dots,\sigma_n$ and that $A$ has been normalized so that $\sigma_1 + \cdots + \sigma_n = 1$. The "entropy" of $A$ can be defined as the entropy of the distribution $(\sigma_1,\dots,\sigma_n)$. That is, the entropy is equal to the sum $$ H = -[\sigma_1 \log(\sigma_1) + \cdots + \sigma_n \log(\sigma_n)] $$ where $0 \log(0)$ is defined to be zero. This metric of information gives us a defintion equivalent to the "entropy of entanglement" of a state in a bipartite quantum system.

$\endgroup$
6
  • $\begingroup$ There have been attempts at extending the notion of "rank" to non-integer values in the context of completions. My own work here is an example of such an attempt. $\endgroup$ – Ben Grossmann May 5 '20 at 22:30
  • $\begingroup$ Does the base of log matter? How would these metrics do against each other, is there an established relation we can approximate? $\endgroup$ – donkey May 13 '20 at 22:10
  • $\begingroup$ By the looks of the formula entropy is additive, as in, entropy(H1, H2) = entropy(H1) + entropy(H2), is this correct? The only problem I see would be possibly with the singular value and normalization condition. $\endgroup$ – donkey May 13 '20 at 22:17
  • $\begingroup$ The base of the log doesn't matter; choosing a different base just scales the metric, i.e. scales all entropies in the same way. I don't know of any good way to directly compare these metrics. The entropy is not additive. For instance, the entropy of $A$ is equal to that of $-A$, but the entropy of $A + (-A)$ is zero. I believe that it is, however, "subadditive" in the sense that $H(A + B) \leq H(A) + H(B)$. $\endgroup$ – Ben Grossmann May 13 '20 at 22:32
  • $\begingroup$ What would be the correct way of extending this concept to a set of matrices then? Should I be trying to find one matrix that represents my set and calculate it's entropy instead? $\endgroup$ – donkey May 14 '20 at 14:22

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.