# Concavity of entropy difference

Suppose that $$\mathrm{A}$$ is a $$n\times n$$ random matrix with a given distribution. Suppose that $$\mathrm{U}$$ is a diagonal unitary random matrix, defined as \begin{align*} \begin{bmatrix} \exp(i\theta_1)&0&\cdots&0\\ 0&\exp(i\theta_2)&\cdots&0\\ 0&0&\ddots&0\\ 0&0&\cdots&\exp(i\theta_n) \end{bmatrix}, \end{align*} where $$\theta_i$$ are i.i.d. Uniform random variable over $$[0,2\pi]$$, independent of $$\mathrm{A}$$, and $$i$$ is the imaginary number.

I need to show that the following function is concave w.r.t. the input distribution: \begin{align*} F(p(\mathbf{x}))\triangleq H(\mathrm{A}\mathbf{X})- H(\mathrm{A} \mathrm{U}\mathbf{X}), \end{align*} where $$\mathbf{X}$$ is a continuous random vector of size $$n$$, with probability distribution $$p(\mathbf{x})$$, and $$H(\cdot)$$ is the Shannon entropy. This means that we need to show that for any $$0 \leq \lambda \leq 1$$, $$p_1(\mathbf{x})$$ and $$p_2(\mathbf{x})$$ \begin{align*} \lambda F(p_1(\mathbf{x}))+ (1-\lambda) F(p_2(\mathbf{x})) \leq F(p(\mathbf{x})), \end{align*} where $$p(\mathbf{x})=\lambda p_1(\mathbf{x})+ (1-\lambda) p_2(\mathbf{x})$$.

P.S. Some extra assumptions on $$\mathrm{A}$$ might be needed.

• I don't understand your (interesting) question. Please clarify your notation: What does "concave r.r.t. the input distribution" mean? concave w.r.t. $p$ (the notation $p(x)$in this context does not make much sense) or w,r,t, $X$ or ...? Jun 24 '20 at 12:11
• The entropy function (and hence the defined $F$ function), is a function of the underlying probability distribution, and not $\mathbf{X}$. I wrote it down. Please let me know if I'm not clear.
– Mini
Jun 24 '20 at 12:37
• Now this is clear! Jun 24 '20 at 12:39
• What happens in the situation when all distributions are discrete (with the diagonal entries, for instance, taking iid values +1 and -1), and one deals with the usual entropy instead of the differential one?
– R W
Jun 24 '20 at 16:28
– Mini
Jun 25 '20 at 9:35

Without further assumptions, I think $$F$$ is not necessarily concave.

Let $$\mathbf{X}_1\sim p_1$$, $$\mathbf{X}_2\sim p_2$$ and $$B\sim\textrm{Bernoulli}(\lambda)$$ be independent, and let \begin{align*} \mathbf{X} &:= \begin{cases} \mathbf{X}_1 & \text{if B=1,} \\ \mathbf{X}_2 & \text{if B=0.} \end{cases} \end{align*} Then, $$\mathbf{X}\sim p=\lambda p_1 + (1-\lambda) p_2$$.

In general, for two random variables $$Z$$ and $$C$$, where $$Z$$ is continuous and $$C$$ is discrete, we have \begin{align*} h(Z) + H(C\,|\,Z) &= H(C) + h(Z\,|\,C) \;, \end{align*} where $$H(\cdot)$$ denotes the ordinary (discrete) entropy and $$h(\cdot)$$ is the differential entropy.

It follows that \begin{align*} & \overbrace{h(\mathrm{A}\mathbf{X}) - h(\mathrm{A}\mathrm{U}\mathbf{X})}^{F(p)} + \overbrace{H(B\,|\,\mathrm{A}\mathbf{X}) - H(B\,|\,\mathrm{A}\mathrm{U}\mathbf{X})}^{\displaystyle(\sharp)} \\ &= h(\mathrm{A}\mathbf{X}\,|\,B) - h(\mathrm{A}\mathrm{U}\mathbf{X}\,|\,B) + H(B) - H(B) \\ &= \lambda\big(\underbrace{h(\mathrm{A}\mathbf{X}_1) - h(\mathrm{A}\mathrm{U}\mathbf{X}_1)}_{F(p_1)}\big) + (1-\lambda)\big(\underbrace{h(\mathrm{A}\mathbf{X}_2) - h(\mathrm{A}\mathrm{U}\mathbf{X}_2)}_{F(p_2)}\big) \end{align*} provided that $$p_1$$ and $$p_2$$ are absolutely continuous w.r.t. the three-dimensional Lebesgue and $$\mathrm{A}$$ is almost surely non-singular. (Otherwise, the differential entropies become $$-\infty$$ and $$F$$ would not be well-defined.)

Therefore, in order for $$F$$ to be concave, we must have \begin{align*} (\sharp) = H(B\,|\,\mathrm{A}\mathbf{X}) - H(B\,|\,\mathrm{A}\mathrm{U}\mathbf{X}) &\leq 0 \tag{?} \end{align*} whenever $$p_1$$ and $$p_2$$ are absolutely continuous and $$\mathrm{A}$$ is almost surely non-singular.

[Update: The original example was not valid because it disregarded the requirement that $$p_1$$ and $$p_2$$ have to be absolutely continuous and $$\mathrm{A}$$ non-singular. The following sketch is meant to circumvent that issue.]

Fix $$0<\lambda<1$$. Let \begin{align*} \hat{\mathrm{A}} &:= \begin{bmatrix} 1 & 1/2 & 1/2 \\ 0 & -1/2 & 1/2 \\ 0 & -1/2 & 1/2 \end{bmatrix} & \hat{\mathbf{X}}_1 &:= \begin{bmatrix} 1 \\ 0 \\ 0 \end{bmatrix} & \hat{\mathbf{X}}_2 &:= \begin{bmatrix} 0 \\ 1 \\ 1 \end{bmatrix} \end{align*} Let $$\mathrm{A}$$ be a non-singular (deterministic or random) matrix which is very close to $$\hat{\mathrm{A}}$$, and let $$\mathbf{X}_1=\hat{\mathbf{X}}+\sigma\mathbf{Z}_1$$ and $$\mathbf{X}_2=\hat{\mathbf{X}}+\sigma\mathbf{Z}_2$$, where $$\mathbf{Z}_1$$ and $$\mathbf{Z}_2$$ are two independent standard normal vectors and $$\sigma$$ is very small. Assume that $$\mathbf{Z}_1$$, $$\mathbf{Z}_2$$, $$\mathrm{U}$$ and $$\mathrm{A}$$ are all independent.

Note that both $$\mathrm{A}\mathbf{X}_1$$ and $$\mathrm{A}\mathbf{X}_2$$ are highly concentrated around a vector very close to $$\hat{\mathbf{X}}_1$$. By chooseing $$\mathrm{A}$$ close enough to $$\hat{\mathrm{A}}$$, we can make sure that $$\mathrm{A}\mathbf{X}_1$$ and $$\mathrm{A}\mathbf{X}_2$$ are hardly distinguishable. Hence, $$\mathrm{A}\mathbf{X}$$ would hardly have any information about $$B$$, and as a result \begin{align*} H(B\,|\,\mathrm{A}\mathbf{X}) &\approx H(B) = H(\lambda) \;. \end{align*}

On the other hand, $$\mathrm{A}\mathrm{U}\mathbf{X}_1$$ and $$\mathrm{A}\mathrm{U}\mathbf{X}_2$$ will be distinguishable, with $$\mathrm{A}\mathrm{U}\mathbf{X}_1$$ still being close to the linear span of $$\hat{\mathbf{X}}_1$$ and $$\mathrm{A}\mathrm{U}\mathbf{X}_2$$ typically far from it. In particular, $$\mathrm{A}\mathrm{U}\mathbf{X}$$ has significant information about $$B$$ and hence \begin{align*} H(B\,|\,\mathrm{A}\mathrm{U}\mathbf{X}) &\ll H(B) = H(\lambda) \;. \end{align*} Therefore, in this example, $$(\sharp)>0$$ contrary to the claim.

• For deterministic invertible matrices $\mathrm{A}$, the result is correct. I guess, I should have stated the invertible condition for $\mathrm{A}$.
– Mini
Jul 4 '20 at 10:15
• Is $F(p)$ really concave when $\mathrm{A}$ is deterministic and invertible? Isn't $F(p)$ continuous as a function of $\mathrm{A}$? If so, we can choose $\mathrm{A}$ invertible but very close to the matrix I used above, and the concavity inequality would still fail. Am I missing something? Jul 4 '20 at 13:04
• I argue as following: Let $\mathbf{Y}=(|X_1|,|X_2|,\cdots,|X_n|)$ and $\mathbf{Z}=(\angle X_1,\angle X_2 ,\cdots,\angle X_n)$. We have $h(\mathrm{A}\mathbf{X})=h(\mathbf{X})+\log(|det(\mathrm{A})|)$. Hence $F(P)=h(\mathbf{X})-h(\mathrm{U} \mathbf{X})=h(\mathbf{Z}|\mathbf{Y})-2n\pi$, and we know that entropy is a concave function. Note that in the last step, I changed the coordinate from Cartersian to polar.
– Mini
Jul 4 '20 at 14:34
• In fact, $F(p)$ is not continuous w.r.t $\mathrm{A}$, since $\log$ is not continuous around 0.
– Mini
Jul 4 '20 at 15:06
• I am not used to differential entropy, so I don't get how you did your last step. Regarding the (dis-)continuity of $F(p)$, we are not applying $\log$ around $0$ in $h(\mathrm{A}\mathbf{X})$ as long as $\mathbf{X}$ is absolutely continuous, are we? Jul 4 '20 at 15:35