Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Consider a random matrix $X$ and a random vector $Y$. Let the Shannon entropies $H(X) = H(Y) = n$. Is there a simple upper bound for entropy $H(XY)$? I believe $H(XY) \leq 2n$ as that is a simple upper bound for the joint entropy of $(X,Y)$, but is it also the case that $H(XY) \leq n$?


The entries of $X$ need not be independent. $X$ is $m$ by $n$ for some $m \leq n$ and $Y$ has $n$ entries.

share|improve this question
    
Why do you think that H(XY) would be at most n? –  Did Jul 28 at 18:54
    
@Did I just couldn't think of an example where the entropy is higher. Is there in fact a simple example? –  Lembik Jul 29 at 17:46
    
what are the dimensions of our matrix $X$? Are all the entries independent? What is the size of your vector $Y$? @Lembik –  john mangual Jul 30 at 22:47
    
@johnmangual The entries of $X$ need not be independent. $X$ is $m$ by $n$ for some $m \leq n$ and $Y$ has $n$ entries. –  Lembik Jul 31 at 6:47
1  
I think your argument is that $H(XY)\le H(X) + H(Y)$, and I think that is pretty obviously correct. If the mapping $(X,Y)\mapsto XY$ is invertible, then clearly equality holds, i.e., $H(XY) = H(X) + H(Y)$. It's easy to construct examples where this is the case. For example, let $X=\text{diag}(\pm 1,1)$ with equal probability and let $Y=[1\ \ \pm1]^T$ with equal probability. It's then easy to see that one can "reconstruct" $X$ and $Y$ from knowledge of $XY$, and so $H(XY) = H(X)+H(Y)$. –  Will Nelson Aug 1 at 1:08

1 Answer 1

up vote 2 down vote accepted
+50

Differential entropy

I don't think that you can derive an upper bound for the following reason.

Let's assume $Y \sim \mathcal N(0,\eta I)$ is Gaussian distributed (with $\eta$ chosen such that $H[Y]=n$) and $X \sim \mathcal N(\lambda O, \kappa I)$, where $\kappa$ is chosen such that $H[X]=n$, $O$ a matrix consisting of ones, and $\lambda$ a free parameter which we are going to play around with.

For $\lambda=1$ the entropy of will have some value $H[XY]=c$ . However, since the differential entropy depends on scale, increasing $\lambda$ will also increase $H[XY]$. More specifically, for arbitrary $\lambda$ $$H[XY]=H\left[\frac{1}{\lambda} XY\right]+n\log \lambda=c + n\log \lambda.$$

Since $\lambda$ only changes the mean of $X$, is does not affect its marginal entropy $H[X]$. However, as you can see, the entropy $H[XY]$ can be made arbitrarily large by increasing $\lambda$. Therefore, there is no upper bound in terms of the single marginal entropies.

It might help to know the transformation formula for discrete entropies. Maybe this can make it clearer that the differential entropy changes under a deterministic function $f$.

Consider the function $f:\mathbb{R}^{n}\rightarrow\mathbb{R}^{n}$ and that we want to know $H\left[Y\right]$ in terms of $H\left[X\right]$ where $Y=f(X)$:

\begin{align}H\left[Y\right] &= \left\langle -\log p_{Y}(Y)\right\rangle _{Y}\\ &= \left\langle -\log p_{Y}(f(X))\right\rangle _{X}\\ &= \left\langle -\log\left(\underbrace{p_{Y}(f(X))\left|\frac{dy}{dx}\right|}_{p_{X}(X)}\left|\frac{dy}{dx}\right|^{-1}\right)\right\rangle _{X}\\ &= H\left[X\right]+\left\langle \log\left(\left|\frac{dy}{dx}\right|\right)\right\rangle _{X}. \end{align}

Discrete entropy (after discussion with Will Nelson in the comments) Will was right that for discrete entropy and a deterministic function, one can show that $$H[XY]=H[f(X,Y)]\le H[X] + H[Y].$$ The reason (which can be found on wikipedia) is that $$0 \le H[Z,f(Z)]=H[Z] + H[f(Z)|Z] = H[Z|f(Z)] + H[f(Z)]$$ and the fact that $H[f(Z)|Z]=0$ for deterministic $f$.

How can we apply this to the case above? First of all, we know that $$2n \ge H[X,Y] \ge n.$$ This follows from $H[X,Y] = H[X] + H[Y|X]$, $H[Y|X]\ge 0$ and the fact that conditioning reduces entropy.

So if $X$ and $Y$ are completely dependent, then $H[X,Y] = n \ge H[XY]$. Whether $H[XY]=H[X,Y]=n$ depends on $H[X,Y|XY]=0$ which is the case if the nullspace of $XY$ is zero for all $X$.

So we know now that $H[XY]\le H[X,Y]$ and under which conditions this would be equal to $n$. Of course one could still have $H[X,Y]>n$ and $H[XY]\le n$, but without any further knowledge of the distribution $p(X,Y)$ I have no idea how to show anything better.

share|improve this answer
    
I am a little confused. I had assumed that the joint entropy $H(X,Y) = 2n$ and that therefore $H(f(X,Y)) \leq 2n$. Is that not even right? –  Lembik Jul 31 at 8:37
    
The joint entropy of $X$ and $Y$ is only $2n$ if $X$ and $Y$ are independent. Why would you expect $H[f(X,Y)]\le 2n$? For example, if $f:\mathbb R^{2n+m}\rightarrow \mathbb R^{2n+m}$, then $H\left[f(X,Y)\right] = H\left[X,Y\right]+\left\langle \log\left(\left|\frac{df}{d(x,y)}\right|\right)\right\rangle _{X,Y}$. Depending on $f$ this can de- or increase the entropy. E.g. if $f$ just multiplies with a constant greater than one, you will always increase the differential entropy. –  fabee Jul 31 at 9:00
    
Right I meant $H(X,Y) \leq 2n$, that was a mistake. I will have to think about your comment. I expected $H(f(X,Y)) \leq H(X,Y)$ on the principle that entropy equals information and you can't increase the amount of information by applying a deterministic function. –  Lembik Jul 31 at 9:02
    
I think it is not very helpful to think about entropy as information in this case. In particular, for differential entropy this notion is not always unproblematic. What you are probably thinking of is the data processing inequality (scholarpedia.org/article/Mutual_information). –  fabee Jul 31 at 9:06
1  
In that case one would have to show that $H[f(X,Y)]\le H[X,Y]$ for $f(x,y)=xy$ and I am not completely sure whether that holds. However, you said that $H[Y]=n$ which is the dimension of $Y$. Is that a coincidence or on purpose? If so, $H[XY]$ must be smaller or equal than $n$ since $n$ is the entropy of the uniform distribution in $n$ dimensions which has maximal entropy (discrete case). This means you cannot increase the entropy of $Y$ no matter what you do with it. –  fabee Aug 2 at 8:58

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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