2
$\begingroup$

Let $X$ and $Y$ be two $\rho$ correlated Gaussian vectors, such that $X,Y\sim N(0,1)^n$ and $E[X_iY_i]=\rho$. Let $M_X = f(X)$ and $M_Y = f(Y)$ be $k$-bit functions of $X$ and $Y$, that is $H(X)=H(Y)=k$.

We then have that $M_X - X - Y - M_Y$ is a Markov Chain.

By the standard Strong Data Processing Inequality (SDPI), we get $I(M_X; Y) \le \rho^2 I(M_X; X) \le \rho^2 k$ and likewise $I(M_Y; X) \le \rho^2 k$.

I would like to show that $$I(M_X ; M_Y) \le \rho^2 k / 2.$$

This is motivated by the fact that when $M_X$ and $M_Y$ are seen as approximations to $X$ and $Y$, then one will need twice as good approximations when both $X$ and $Y$ are approximated, rather than if only one of them is (the case $I(X ; M_Y)$.)

I'm aware of the general result by Yury Polyanskiy and Yihong Wu, which lets one compute an end-to-end SDPI for a Markov Chain (or graph). However, in that case, it is assumed that each link loses some constant factor, wherein my case the two links $M_X - X$ and $Y - M_Y$ are rate capped rather than noisy.

Do you know any information-theoretical tricks, or known relations, that I'm unaware of which might be useful?

$\endgroup$

1 Answer 1

1
$\begingroup$

What happens if $n = k = 1$ and $X = Y$? In this case $\rho = 1$. Let $M_X = 0$ if $X < 0$ and 1 otherwise. Let $M_Y = 0$ if $Y < 0$ and 1 otherwise. Then $I(M_X;M_Y) = H(M_X) - H(M_X|M_Y) = 1$. This seems to contradict your wanted inequality.

$\endgroup$
5
  • $\begingroup$ It does unfortunately. Even for larger k and n. I still feel like there should be some loss over $\rho^2 k$ when $\rho\in(0,1)$. Do you have any intuition on this? $\endgroup$ Jul 28, 2020 at 6:44
  • $\begingroup$ No, no intuition unfortunately. I just tried the simplest example i could think of. The same example with arbitrary $\rho$ seems hard to evaluate though. $\endgroup$ Jul 28, 2020 at 9:43
  • $\begingroup$ I'm mostly interested in the asymptotics as $\rho\to 0$. Perhaps the answer is something like $\rho^2 k/(2-|\rho|)$... $\endgroup$ Jul 28, 2020 at 12:54
  • 1
    $\begingroup$ If you analyze this particular channel for $\rho$ correlated $X$ and $Y$, you get $1 - H(\frac14 + \frac{1}{2\pi} \cdot\arcsin(\rho))$ where I am using $H$ for the binary entropy function. (That number is directly coming from (math.stackexchange.com/questions/255368/…)), so perhaps that might be a good place to start to get the asymptotics you are looking for. $\endgroup$
    – Efe
    Aug 10, 2020 at 19:06
  • $\begingroup$ @Efe (I think you need a factor 2 inside $H$, but) good point. We also know that for binary sources the two-function "most informative boolean function" conjecture states $I(W_X;W_Y)\le 1-H(\frac{1+\rho}2)$ for $W_X,W_Y\in\{0,1\}$. Looks like a good conjceture for the Gaussian case is still $\rho^2/(2-\rho^2)$ or $\rho^2/(2-|\rho|)$. $\endgroup$ Aug 13, 2020 at 13:24

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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