2
$\begingroup$

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.

$\endgroup$
9
  • $\begingroup$ 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 ...? $\endgroup$ Jun 24 '20 at 12:11
  • $\begingroup$ 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. $\endgroup$
    – Mini
    Jun 24 '20 at 12:37
  • 1
    $\begingroup$ Now this is clear! $\endgroup$ Jun 24 '20 at 12:39
  • 1
    $\begingroup$ 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? $\endgroup$
    – R W
    Jun 24 '20 at 16:28
  • $\begingroup$ Still I don't know the answer. I'll think about it. $\endgroup$
    – Mini
    Jun 25 '20 at 9:35
1
+50
$\begingroup$

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.

$\endgroup$
13
  • $\begingroup$ For deterministic invertible matrices $\mathrm{A}$, the result is correct. I guess, I should have stated the invertible condition for $\mathrm{A}$. $\endgroup$
    – Mini
    Jul 4 '20 at 10:15
  • $\begingroup$ 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? $\endgroup$
    – Algernon
    Jul 4 '20 at 13:04
  • $\begingroup$ 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. $\endgroup$
    – Mini
    Jul 4 '20 at 14:34
  • $\begingroup$ In fact, $F(p)$ is not continuous w.r.t $\mathrm{A}$, since $\log$ is not continuous around 0. $\endgroup$
    – Mini
    Jul 4 '20 at 15:06
  • $\begingroup$ 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? $\endgroup$
    – Algernon
    Jul 4 '20 at 15:35

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.