Mutual Information Bounds for Lossy Common Information
Anderson de Andrade 1 · 2025
Read Mutual Information Bounds for Lossy Common Information by Anderson de Andrade 1 (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2507-04209.txt.
Introduction
Anderson de Andrade proves, in a 2025 paper, a bound separating two rival notions of shared information when some loss is allowed. The setting is the Gray-Wyner network, a classic model for sending common and private messages together. Wyner's lossy common information and the Gács-Körner version disagree on what counts as truly shared. De Andrade shows the mutual information between the targets sits between them as a dividing bound, extending a lossless-case result from the nineteen seventies.
Catalog record
| CREATOR | Anderson de Andrade 1 |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 11 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2507-04209
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Mutual Information Bounds for Lossy Common Information
Anderson de Andrade 1
Abstract
. We show the mutual information between the targets in a Gray-Wyner Network as a bound that separates Wyner’s lossy common information and Gács-Körner lossy common information. The results are a generalization of the lossless case presented by [ 6 ] . Keywords. common information, information theory
1.
Preliminaries
Let
X_{1}
and
X_{2}
be two random sources. In the Gray-Wyner Network
[
3
]
, an analysis transform
(Y_{0},Y_{1},Y_{2})=f(X_{1},X_{2})
produces common and private representations with corresponding rates
(R_{0},R_{1},R_{2})
. A synthesis transform
\hat{Z}_{1}=g_{1}(Y_{0},Y_{1})
and
\hat{Z}_{2}=g_{2}(Y_{0},Y_{2})
predicts the targets
Z_{1}
and
Z_{2}
of two dependent tasks, producing distortions
D_{1}=d_{1}(\hat{Z}_{1},Z_{1})
and
D_{2}=d_{2}(\hat{Z}_{2},Z_{2})
, respectively. The joint rate-distortion function
[
1
]
is given as
R_{X_{1},X_{2}}(D_{1},D_{2})
.
In this setting, we define Wyner’s lossy common information
[
5
,
6
]
as:
(1.1)
\displaystyle C(X_{1},X_{2};D_{1},D_{2})=\inf I(X_{1},X_{2};U),
where the infimum is over all joint densities
P(X_{1},X_{2},\hat{Z}_{1},\hat{Z}_{2},U)
under the following Markov conditions:
(1.2)
\displaystyle\hat{Z}_{1}\leftrightarrow U\leftrightarrow\hat{Z}_{2},
(1.3)
\displaystyle(X_{1},X_{2})\leftrightarrow(\hat{Z}_{1},\hat{Z}_{2})\leftrightarrow U,
and where
P(\hat{Z}_{1},\hat{Z}_{2}|X_{1},X_{2})\in\mathcal{P}^{X_{1},X_{2}}_{D_{1},D_{2}}
is any joint distribution that achieves the rate distortion function at
(D_{1},D_{2})
, i.e.,
I(X_{1},X_{2};\hat{Z}_{1},\hat{Z}_{2})=R_{X_{1},X_{2}}(D_{1},D_{2})
.
Gács-Körner lossy common information
[
5
,
2
]
is defined for this setting as:
(1.4)
\displaystyle K(X_{1},X_{2};D_{1},D_{2})=\sup I(X_{1},X_{2};V),
where the supremum is over all joint densities
(X_{1},X_{2},\hat{Z}_{1},\hat{Z}_{2},V)
, such that the following Markov conditions are met:
(1.5)
\displaystyle X_{2}\leftrightarrow X_{1}\leftrightarrow V,
(1.6)
\displaystyle X_{1}\leftrightarrow X_{2}\leftrightarrow V,
(1.7)
\displaystyle X_{1}\leftrightarrow\hat{Z}_{1}\leftrightarrow V,
(1.8)
\displaystyle X_{2}\leftrightarrow\hat{Z}_{2}\leftrightarrow V,
where
P(\hat{Z}_{1}|X_{1})\in\mathcal{P}^{X_{1}}_{D_{1}}
and
P(\hat{Z}_{2}|X_{2})\in\mathcal{P}^{X_{2}}_{D_{2}}
are optimal rate-distortion encoders at
D_{1}
and
D_{2}
, respectively.
Recall that the interaction information
[
4
,
7
]
between random variables
X
,
Y
, and
Z
is given as:
(1.9)
\displaystyle I(X;Y;Z)=I(X;Y)-I(X;Y|Z),
and that the chain rule of mutual information
[
1
]
is defined as:
(1.10)
\displaystyle I(X;Z)=I(X;Y,Z)-I(X;Y|Z).
We derive the following corollary:
(1.11)
\displaystyle I(X;Y;Z)=I(X,Y;Z)-I(X;Z|Y)-I(Y;Z|X).
An outline of the proof is presented as follows:
(1.12)
\displaystyle I(X;Y;Z)
\displaystyle=\nicefrac{{1}}{{2}}\left[I(X;Z)-I(X;Z|Y)+I(Y;Z)-I(Y;Z|X)\right]
\displaystyle(\text{eq.~\ref{eq:ii} twice})
(1.13)
\displaystyle=I(X,Y;Z)-I(X;Z|Y)-I(Y;Z|X).
\displaystyle(\text{eq.~\ref{eq:chain-rule} twice})
2.
Main Result
Theorem 1
.
For the Markov chain
(X_{1},X_{2})\to(\hat{Z}_{1},\hat{Z}_{2})
, yielding distortions
D_{1}
and
D_{2}
, we have:
(2.1)
\displaystyle K(X_{1},X_{2};D_{1},D_{2})\leq I(\hat{Z}_{1};\hat{Z}_{2})\leq C(X_{1},X_{2};D_{1},D_{2}),
with equality on both sides if and only if we can represent
X_{1}
and
X_{2}
as
X_{1}=(X^{\prime}_{1},W)
and
X_{2}=(X^{\prime}_{2},W)
, such that these Markov conditions hold:
(2.2)
\displaystyle\hat{Z}_{1}\leftrightarrow W\leftrightarrow\hat{Z}_{2},
(2.3)
\displaystyle(X_{1},X_{2})\leftrightarrow(\hat{Z}_{1},\hat{Z}_{2})\leftrightarrow W.
Proof.
Declaring the Markov chain condition in the theorem statement:
(2.4)
\displaystyle(X_{1},X_{2})\to(\hat{Z}_{1},\hat{Z}_{2}),
we show for the RHS that:
(2.5)
\displaystyle I(\hat{Z}_{1};\hat{Z}_{2})
\displaystyle=I(\hat{Z}_{1};\hat{Z}_{2};U)+I(\hat{Z}_{1};\hat{Z}_{2}|U)
\displaystyle(\text{\text{eq.~\ref{eq:ii}}})
(2.6)
\displaystyle=I(\hat{Z}_{1};\hat{Z}_{2};U)
\displaystyle(\text{cond.~\ref{wci:cond-1}})
(2.7)
\displaystyle=I(\hat{Z}_{1},\hat{Z}_{2};U)-I(\hat{Z}_{1};U|\hat{Z}_{2})-I(\hat{Z}_{2};U|\hat{Z}_{1})
\displaystyle(\text{eq.~\ref{eq:ii-break-down}})
(2.8)
\displaystyle\leq I(\hat{Z}_{1},\hat{Z}_{2};U)
\displaystyle\left(I(X;Y|Z)\geq 0\right)
(2.9)
\displaystyle=I(X_{1},X_{2},\hat{Z}_{1},\hat{Z}_{2};U)-I(X_{1},X_{2};U|\hat{Z}_{1},\hat{Z}_{2})
\displaystyle(\text{eq.~\ref{eq:chain-rule}})
(2.10)
\displaystyle=I(X_{1},X_{2},\hat{Z}_{1},\hat{Z}_{2};U)
\displaystyle(\text{cond.~\ref{wci:cond-2}})
(2.11)
\displaystyle=I(X_{1},X_{2};U)+I(\hat{Z}_{1},\hat{Z}_{2};U|X_{1},X_{2})
\displaystyle(\text{eq.~\ref{eq:chain-rule}})
(2.12)
\displaystyle=I(X_{1},X_{2};U).
\displaystyle(\text{cond.~\ref{eq:cond-base}})
Thus:
(2.13)
\displaystyle I(\hat{Z}_{1};\hat{Z}_{2})\leq I(X_{1},X_{2};U)
\displaystyle\implies\inf I(\hat{Z}_{1};\hat{Z}_{2})\leq\inf I(X_{1},X_{2};U)
(2.14)
\displaystyle\implies I(\hat{Z}_{1};\hat{Z}_{2})\leq C(X_{1},X_{2};D_{1},D_{2}),
\displaystyle(\text{eq.~\ref{eq:wci}})
where the infimum is over the same conditions as in
1.1
.
To prove the LHS, we have:
(2.15)
\displaystyle I(X_{1},X_{2};V)
\displaystyle=I(X_{1};V)+I(X_{2};V|X_{1})
\displaystyle(\text{eq.~\ref{eq:chain-rule}})
(2.16)
\displaystyle=I(X_{1};V)
\displaystyle(\text{cond.~\ref{eq:gkci-markov-1}})
(2.17)
\displaystyle=I(X_{1};X_{2};V)+I(X_{1};V|X_{2})
\displaystyle(\text{\text{eq.~\ref{eq:ii}}})
(2.18)
\displaystyle=I(X_{1};X_{2};V)
\displaystyle(\text{cond.~\ref{eq:gkci-markov-2}})
(2.19)
\displaystyle=I(X_{1},\hat{Z}_{1};X_{2},\hat{Z}_{2};V)
\displaystyle(\text{conds.~\ref{eq:cond-base},~\ref{eq:gkci-markov-1},~\ref{eq:gkci-markov-2}})
(2.20)
\displaystyle=I(\hat{Z}_{1};\hat{Z}_{2};V)
\displaystyle(\text{conds.~\ref{eq:gkci-markov-3},~\ref{eq:gkci-markov-4}})
(2.21)
\displaystyle\leq I(\hat{Z}_{1};\hat{Z}_{2}).
Equation
2.19
was derived by noting that for any random variables
X
,
Y
, and
Z
, we have
I(X,Y;Z)\geq I(X;Z)
. However, in our case, since
\hat{Z}_{1}
and
\hat{Z}_{2}
are derived by
X_{1}
and
X_{2}
, and because
X_{1}
and
X_{2}
have the same information about
V
, we have equality. Formally:
(2.22)
\displaystyle\left[(X_{1},X_{2})\to\hat{Z}_{1}\right]\land\left[X_{2}\leftrightarrow X_{1}\leftrightarrow V\right]
\displaystyle\implies I(X_{1};X_{2};V)=I(X_{1},\hat{Z}_{1};X_{2};V),
(2.23)
\displaystyle\left[(X_{1},X_{2})\to\hat{Z}_{2}\right]\land\left[X_{1}\leftrightarrow X_{2}\leftrightarrow V\right]
\displaystyle\implies I(X_{1};X_{2};V)=I(X_{1};X_{2},\hat{Z}_{2};V).
Due to conditions
1.7
and
1.8
,
X_{1}
and
X_{2}
can be respectively dropped.
Finally, we have:
(2.24)
\displaystyle I(X_{1},X_{2};V)\leq I(\hat{Z}_{1};\hat{Z}_{2})
\displaystyle\implies\sup I(X_{1},X_{2};V)\leq\sup I(\hat{Z}_{1};\hat{Z}_{2})
(2.25)
\displaystyle\implies K(X_{1},X_{2};D_{1},D_{2})\leq I(\hat{Z}_{1};\hat{Z}_{2}),
\displaystyle(\text{eq.~\ref{eq:gkci}})
where the supremum is over the same conditions as in
1.4
.
To obtain equality on the RHS, condition
2.31
together with condition
2.2
establishes that:
(2.26)
\displaystyle I(\hat{Z}_{1};W|\hat{Z}_{2})=I(\hat{Z}_{2};W|\hat{Z}_{1})=0.
Plugging this result (equation
2.26
) in equation
2.7
and continuing the same analysis yields:
(2.27)
\displaystyle I(\hat{Z}_{1},\hat{Z}_{2};W)-I(\hat{Z}_{1};W|\hat{Z}_{2})-I(\hat{Z}_{2};W|\hat{Z}_{1})=I(X_{1},X_{2};W)
(2.28)
\displaystyle\implies
\displaystyle I(\hat{Z}_{1};\hat{Z}_{2})=I(X_{1},X_{2};W)
(2.29)
\displaystyle\implies
\displaystyle I(\hat{Z}_{1};\hat{Z}_{2})=\inf I(X_{1},X_{2};U)
(2.30)
\displaystyle\implies
\displaystyle I(\hat{Z}_{1};\hat{Z}_{2})=C(X_{1},X_{2};D_{1},D_{2}),
where the infimum is over the same conditions as in
1.1
. Note that
W
is achieved by the infimum.
To obtain equality on the LHS, first note that the representation requirements
X_{1}=(X^{\prime}_{1},W)
and
X_{2}=(X^{\prime}_{2},W)
establish the following Markov condition:
(2.31)
\displaystyle X_{1}\rightarrow W\leftarrow X_{2},
implying that
W
can only carry information that is mutual between
X_{1}
and
X_{2}
such that:
(2.32)
\displaystyle I(X_{1};X_{2})-I(X_{1};X_{2}|W)=H(W).
Also note that due to conditions
2.2
and
2.31
, the sufficient condition
2.3
implies conditions
1.7
and
1.8
:
(2.33)
\displaystyle\left[\hat{Z}_{1}\leftrightarrow W\leftrightarrow\hat{Z}_{2}\right]\land\left[X_{1}\rightarrow W\leftarrow X_{2}\right]
(2.34)
\displaystyle\implies
\displaystyle\left\{(X_{1},X_{2})\leftrightarrow(\hat{Z}_{1},\hat{Z}_{2})\leftrightarrow W\iff\left[X_{1}\leftrightarrow\hat{Z}_{1}\leftrightarrow W\right]\land\left[X_{2}\leftrightarrow\hat{Z}_{2}\leftrightarrow W\right]\right\}.
This is because the information that is common between
\hat{Z}_{1}
and
\hat{Z}_{2}
must also be common between
X_{1}
and
X_{2}
:
(2.35)
\displaystyle\left[\hat{Z}_{1}\leftrightarrow W\leftrightarrow\hat{Z}_{2}\right]\land\left[X_{1}\rightarrow W\leftarrow X_{2}\right]\land
\displaystyle\implies\left[\hat{Z}_{1}\leftrightarrow X_{1}\leftrightarrow\hat{Z}_{2}\right],
(2.36)
\displaystyle\left[(X_{1},X_{2})\leftrightarrow(\hat{Z}_{1},\hat{Z}_{2})\leftrightarrow W\right]\land\left[\hat{Z}_{1}\leftrightarrow X_{1}\leftrightarrow\hat{Z}_{2}\right]
\displaystyle\implies\left[X_{1}\leftrightarrow\hat{Z}_{1}\leftrightarrow W\right],
(2.37)
\displaystyle\left[\hat{Z}_{1}\leftrightarrow W\leftrightarrow\hat{Z}_{2}\right]\land\left[X_{1}\rightarrow W\leftarrow X_{2}\right]\land
\displaystyle\implies\left[\hat{Z}_{1}\leftrightarrow X_{2}\leftrightarrow\hat{Z}_{2}\right],
(2.38)
\displaystyle\left[(X_{1},X_{2})\leftrightarrow(\hat{Z}_{1},\hat{Z}_{2})\leftrightarrow W\right]\land\left[\hat{Z}_{1}\leftrightarrow X_{2}\leftrightarrow\hat{Z}_{2}\right]
\displaystyle\implies\left[X_{2}\leftrightarrow\hat{Z}_{2}\leftrightarrow W\right].
Lastly, due to condition
2.2
, we have equality in Equantion
2.21
. Hence, putting it all together, we have:
(2.39)
\displaystyle I(\hat{Z}_{1};\hat{Z}_{2};W)=I(\hat{Z}_{1};\hat{Z}_{2})
\displaystyle\implies I(X_{1};X_{2};W)=I(\hat{Z}_{1};\hat{Z}_{2})
\displaystyle(\text{conds.~\ref{eq:cond-equal-1},~\ref{eq:lhs-eq-implication}})
(2.40)
\displaystyle\implies\sup I(X_{1};X_{2};V)=I(\hat{Z}_{1};\hat{Z}_{2})
(2.41)
\displaystyle\implies K(X_{1},X_{2};D_{1},D_{2})=I(\hat{Z}_{1};\hat{Z}_{2}),
where the supremum is over the same conditions as in
1.4
. Note that
W
is achieved by the supremum.
If either, condition
2.3
or
2.31
, is not met, more than
I(\hat{Z}_{1};\hat{Z}_{1})
is present in
W
and equality is not achieved in equation
2.8
. If condition
2.2
is not met, not all mutual information between
\hat{Z}_{1}
and
\hat{Z}_{2}
is placed on
W
and equality is not achieved in equation
2.21
.