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

1 Answer 1

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, 2020 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, 2020 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, 2020 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, 2020 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, 2020 at 15:35

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .