Notebook

Ch 12 - Distributed Lossy Compression¶

Reference: Ch 12 of A. El Gamal and Y.-H. Kim, Network Information Theory, Cambridge University Press, 2011.

Author: Cheuk Ting Li

In [1]:

from psitip import *
PsiOpts.setting(
    solver = "ortools.GLOP",    # Set linear programming solver
    repr_latex = True,          # Jupyter Notebook LaTeX display
    venn_latex = True,          # LaTeX in diagrams
    proof_note_color = "blue",  # Reasons in proofs are blue
)

Thm 12.1 (Berger-Tung Inner Bound)¶

In [2]:

X1, X2 = rv_array("X", 1, 3)
Xh1, Xh2 = rv("Xh1", latex="\hat{X}_1"), rv("Xh2", latex="\hat{X}_2")
M1, M2 = rv_array("M", 1, 3)
R1, R2 = real_array("R", 1, 3)
U1, U2 = rv_array("U", 1, 3)
Q = rv("Q")

model = CodingModel()        # Define distributed lossy compression
model.set_rate(M1, R1)       # The rate of M1, M2 are R1, R2 resp.
model.set_rate(M2, R2)
model.add_edge(X1, X2)       # X1, X2 are correlated source
model.add_node(X1, M1,
            label = "Enc 1") # Encoder 1 maps X1 to M1
model.add_node(X2, M2,
            label = "Enc 2") # Encoder 2 maps X2 to M2
model.add_node(M1+M2, Xh1+Xh2,
            label = "Dec")   # Decoder maps M1,M2 to Xh1,Xh2

model.graph()                # Draw diagram

Out[2]:

In [3]:

# Automatic inner bound, give Berger-Tung inner bound [Berger 1978], [Tung 1978]
r = model.get_inner(is_proof=True)
r.display(note=True)

$\displaystyle \begin{array}{l} {\color{blue}{\text{Codebook:}}}\\ {\color{blue}{\;\;A_{M_1}[i_1], M_1[i_1]\text{,}\,\text{rate = }I(A_{M_1}; X_1|Q_i)}}\\ {\color{blue}{\;\;A_{M_2}[i_2], M_2[i_2]\text{,}\,\text{rate = }I(A_{M_2}; X_2|Q_i)}}\\ {\color{blue}{\text{Enc 1}\,\text{finds}\,i_1\text{:}\,\left(X_1\text{,}A_{M_1}[i_1], M_1[i_1]\right)\in\mathcal{T}}}\\ {\color{blue}{\text{Enc 2}\,\text{finds}\,i_2\text{:}\,\left(X_2\text{,}A_{M_2}[i_2], M_2[i_2]\right)\in\mathcal{T}}}\\ {\color{blue}{\text{Dec}\,\text{finds}\,i_2, i_1\text{:}\,\left(M_1, M_2\text{,}A_{M_2}[i_2], M_2[i_2], A_{M_1}[i_1], M_1[i_1]\right)\in\mathcal{T}}}\\ {\color{blue}{\;\;\;\;\text{generates}\,\hat{X}_1\,\text{from}\,A_{M_2}, A_{M_1}}}\\ {\color{blue}{\text{Dec}\,\text{finds}\,i_2, i_1\text{:}\,\left(M_1, M_2, \hat{X}_1\text{,}A_{M_2}[i_2], M_2[i_2], A_{M_1}[i_1], M_1[i_1]\right)\in\mathcal{T}}}\\ {\color{blue}{\;\;\;\;\text{generates}\,\hat{X}_2\,\text{from}\,\hat{X}_1, A_{M_2}, A_{M_1}}}\\ \exists A_{M_1}, A_{M_2}, Q_i:\, \left\{\begin{array}{l} \begin{array}{l} R_1 \ge I(A_{M_1}; X_1|A_{M_2}, Q_i)\\ {\color{blue}{\;\;\;\;\left(\because\,\text{enc }X_1\text{ to }A_{M_1}, M_1\text{,}\,\text{dec }M_1, M_2\text{ to }A_{M_1}\right)}} \end{array},\\ \begin{array}{l} R_2 \ge I(A_{M_2}; X_2|A_{M_1}, Q_i)\\ {\color{blue}{\;\;\;\;\left(\because\,\text{enc }X_2\text{ to }A_{M_2}, M_2\text{,}\,\text{dec }M_1, M_2\text{ to }A_{M_2}\right)}} \end{array},\\ \begin{array}{l} R_1+R_2 \ge I(A_{M_2}; X_2|Q_i)+I(A_{M_1}; X_1|A_{M_2}, Q_i)\\ {\color{blue}{\;\;\;\;\left(\because\,\text{enc }X_2\text{ to }A_{M_2}, M_2\text{,}\,\text{enc }X_1\text{ to }A_{M_1}, M_1\text{,}\,\text{dec }M_1, M_2\text{ to }A_{M_2}, A_{M_1}\right)}} \end{array},\\ Q_i {\perp\!\!\perp} (X_1, X_2),\\ X_1 \leftrightarrow (Q_i, X_2) \leftrightarrow A_{M_2},\\ (X_2, A_{M_2}) \leftrightarrow (Q_i, X_1) \leftrightarrow A_{M_1},\\ (X_1, X_2) \leftrightarrow (Q_i, A_{M_1}, A_{M_2}) \leftrightarrow (\hat{X}_1, \hat{X}_2)\\ \end{array} \right\} \end{array}$

Thm 12.2 (Berger-Tung Outer Bound)¶

In [4]:

# Write the Berger-Tung outer bound [Berger 1978], [Tung 1978]
r_bt_out = region(
        R1 >= I(X1+X2 & U1 | U2),
        R2 >= I(X1+X2 & U2 | U1),
        R1+R2 >= I(X1+X2 & U1+U2),
        markov(Xh1+Xh2, U1+U2, X1+X2),
        markov(U1, X1, X2),
        markov(U2, X2, X1)
    ).exists(U1+U2)
r_bt_out

Out[4]:

$\exists U_1, U_2:\, \left\{\begin{array}{l} R_1 \ge I(X_1, X_2; U_1|U_2),\\ R_2 \ge I(X_1, X_2; U_2|U_1),\\ R_1+R_2 \ge I(X_1, X_2; U_1, U_2),\\ U_1 \leftrightarrow X_1 \leftrightarrow X_2,\\ (X_1, X_2) \leftrightarrow (U_1, U_2) \leftrightarrow (\hat{X}_1, \hat{X}_2),\\ U_2 \leftrightarrow X_2 \leftrightarrow X_1\\ \end{array} \right\}$

In [5]:

# Proof of outer bound
model.proof_outer(r_bt_out)

Out[5]:

$\begin{align*} &1.\;\text{Claim:}\\ &\exists U_1, U_2:\, \left\{\begin{array}{l} R_1 \ge I(U_1; X_1, X_2|U_2),\\ R_2 \ge I(U_2; X_1, X_2|U_1),\\ R_1+R_2 \ge I(U_1, U_2; X_1, X_2),\\ U_1 \leftrightarrow X_1 \leftrightarrow X_2,\\ (X_1, X_2) \leftrightarrow (U_1, U_2) \leftrightarrow (\hat{X}_1, \hat{X}_2),\\ U_2 \leftrightarrow X_2 \leftrightarrow X_1\\ \end{array} \right\}\\ \\ &\;\;1.1.\;\text{Substitute }\left\{ \begin{array}{ll} U_1 & := (X_{1P}, M_1)\\ U_2 & := (X_{1P}, M_2)\end{array}\right.\text{:}\\ \\ &\;\;1.2.\;\text{Steps: }\\ &\;\;R_1\\ &\;\;\ge I(M_1; X_1|M_2, X_{1P})\;\;\;{\color{blue}{\left(\because\,\text{rate of }M_1\text{:}\, R_1 \ge I(M_1; X_1|X_{1P}, M_2)\right)}}\\ &\;\;= I(M_1; X_1|M_2, X_{1P})-I(M_2, X_{1P}; X_1|X_2)\;\;\;{\color{blue}{\left(\because\, (X_{1P}, M_2) \leftrightarrow X_2 \leftrightarrow X_1\right)}}\\ &\;\;= I(M_1; X_1|M_2, X_{1P})+I(M_2, X_2, X_{2P}; X_1)-I(M_2, X_{1P}, X_2; X_1)\\ &\;\;\;\;\;\;\;\;\;\;{\color{blue}{\left(\because\, (X_{2P}, M_2) \leftrightarrow X_2 \leftrightarrow X_1\right)}}\\ &\;\;= I(M_2, X_2; X_1|X_{2P})+I(M_1; X_1, X_2|M_2, X_{1P})-I(M_1, X_1; M_2, X_2|X_{1P})\\ &\;\;\;\;\;\;\;\;\;\;{\color{blue}{\left(\because\, I(X_{2P}; X_1)+I(M_2; X_1, M_1|X_{1P}) = I(X_{1P}, M_2; X_1)\right)}}\\ &\;\;= I(M_1; X_1, X_2|M_2, X_{1P})-I(M_2, X_2; M_1, Q_o, X_{1P}|X_1, X_{2P})\\ &\;\;\;\;\;\;\;\;\;\;{\color{blue}{\left(\because\, I(X_1, X_{1P}, Q_o, M_1; X_2, M_2|X_{2P}) = I(X_1, M_1; X_2, M_2|X_{1P})\right)}}\\ &\;\;= I(M_1; X_1, X_2|M_2, X_{1P})\;\;\;{\color{blue}{\left(\because\, (M_1, X_{1P}, Q_o) \leftrightarrow (X_1, X_{2P}) \leftrightarrow (M_2, X_2)\right)}}\\ \\ &\;\;1.3.\;\text{Steps: }\\ &\;\;R_2\\ &\;\;\ge I(M_2; X_2|X_{2P})\;\;\;{\color{blue}{\left(\because\,\text{rate of }M_2\text{:}\, R_2 \ge I(M_2; X_2|X_{2P})\right)}}\\ &\;\;= I(M_2, X_{2P}; X_2)\;\;\;{\color{blue}{\left(\because\, X_{2P} {\perp\!\!\perp} X_2\right)}}\\ &\;\;= I(M_2, X_{2P}; X_1, X_2)\;\;\;{\color{blue}{\left(\because\, (X_{2P}, M_2) \leftrightarrow X_2 \leftrightarrow X_1\right)}}\\ &\;\;= H(M_2|X_{2P})+H(X_2|X_1)-H(M_2, X_2|X_1, X_{2P})\;\;\;{\color{blue}{\left(\because\, X_{2P} {\perp\!\!\perp} X_1\right)}}\\ &\;\;= H(X_2|X_1)+H(M_2|X_{1P}, X_{2P})-H(M_2, X_2|X_1, X_{2P})\;\;\;{\color{blue}{\left(\because\, M_2 \leftrightarrow X_{2P} \leftrightarrow X_{1P}\right)}}\\ &\;\;\ge I(M_2; X_1|X_2)+I(M_2, X_{1P}; X_2)+I(M_2, X_2; X_{2P}|X_1)-I(M_2, X_2; X_{1P}, X_{2P})\\ &\;\;\ge H(X_2|X_1)+H(M_2|M_1, X_{1P})-I(M_2, X_2; X_{2P}|X_{1P})-H(M_2, X_2|X_1, X_{2P})\\ &\;\;= I(M_2; X_1, X_2|M_1, X_{1P})-I(M_2, X_2; M_1, Q_o, X_{1P}|X_1, X_{2P})\\ &\;\;\;\;\;\;\;\;\;\;{\color{blue}{\left(\because\, H(X_2|X_1)+H(M_2|X_1, X_2, X_{1P}, M_1) = I(X_{2P}; X_2, M_2|X_{1P})+H(X_2, M_2|X_1, X_{2P}, X_{1P}, Q_o, M_1)\right)}}\\ &\;\;= I(M_2; X_1, X_2|M_1, X_{1P})\;\;\;{\color{blue}{\left(\because\, (M_1, X_{1P}, Q_o) \leftrightarrow (X_1, X_{2P}) \leftrightarrow (M_2, X_2)\right)}}\\ \\ &\;\;1.4.\;\text{Steps: }\\ &\;\;R_1+R_2\\ &\;\;\ge R_1+I(M_2; X_2|X_{2P})\;\;\;{\color{blue}{\left(\because\,\text{rate of }M_2\text{:}\, R_2 \ge I(M_2; X_2|X_{2P})\right)}}\\ &\;\;\ge I(M_2; X_2|X_{2P})+I(M_1; X_1|M_2, X_{1P})\;\;\;{\color{blue}{\left(\because\,\text{rate of }M_1\text{:}\, R_1 \ge I(M_1; X_1|X_{1P}, M_2)\right)}}\\ &\;\;= I(M_1; X_1|M_2, X_{1P})+I(M_2, X_{2P}; X_2)\;\;\;{\color{blue}{\left(\because\, X_{2P} {\perp\!\!\perp} X_2\right)}}\\ &\;\;= I(M_1; X_1|M_2, X_{1P})+I(M_2, X_{2P}; X_1, X_2)\;\;\;{\color{blue}{\left(\because\, (X_{2P}, M_2) \leftrightarrow X_2 \leftrightarrow X_1\right)}}\\ &\;\;= I(X_2; X_{2P}|M_2)+I(M_2, X_2; X_1|X_{2P})+I(M_1, M_2, X_{1P}; X_1, X_2)-I(X_{1P}; X_2|M_2)-I(M_1, X_1; M_2, X_2|X_{1P})\\ &\;\;\;\;\;\;\;\;\;\;{\color{blue}{\left(\because\, I(X_{2P}; X_1)+I(M_2; X_1, M_1|X_{1P}) = I(X_{1P}, M_2; X_1)\right)}}\\ &\;\;= I(M_2, X_2; X_1, X_{2P})+I(M_1, M_2, X_{1P}; X_1, X_2)-I(M_2; X_{2P}|X_{1P})-I(M_2, X_2; M_1, X_1, X_{1P})\\ &\;\;\;\;\;\;\;\;\;\;{\color{blue}{\left(\because\, M_2 \leftrightarrow X_{2P} \leftrightarrow X_{1P}\right)}}\\ &\;\;\ge I(M_2, X_2; X_1, X_{2P})+I(M_1, M_2, X_{1P}; X_1, X_2)-I(M_2, X_2; X_{1P}, X_{2P})-I(M_1, X_1; M_2, X_2|X_{1P})\\ &\;\;= I(M_1, M_2, X_{1P}; X_1, X_2)-I(M_2, X_2; M_1, Q_o, X_{1P}|X_1, X_{2P})\\ &\;\;\;\;\;\;\;\;\;\;{\color{blue}{\left(\because\, I(X_{2P}, Q_o; X_2, M_2|X_1, X_{1P}, M_1) = I(X_{2P}; X_2, M_2|X_{1P})\right)}}\\ &\;\;= I(M_1, M_2, X_{1P}; X_1, X_2)\;\;\;{\color{blue}{\left(\because\, (M_1, X_{1P}, Q_o) \leftrightarrow (X_1, X_{2P}) \leftrightarrow (M_2, X_2)\right)}}\\ \end{align*} $

Thm 12.3 (Quadratic Gaussian Distributed Source Coding)¶

Skipped

Thm 12.4 (Quadratic Gaussian CEO Problem)¶

Skipped

References¶

A. El Gamal and Y.-H. Kim, Network Information Theory, Cambridge University Press, 2011, Ch. 12.
T. Berger, "Multiterminal source coding," in The Information Theory Approach to Communications, G. Longo, Ed. New York: Springer-Verlag, 1978, pp. 171–231.
S.-Y. Tung, "Multiterminal source coding," Ph.D. dissertation, Cornell University, Ithaca, NY, 1978.

In [ ]: