{
"cells": [
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## Gray-Wyner System Demo\n",
"\n",
"Author: Cheuk Ting Li "
]
},
{
"cell_type": "code",
"execution_count": 1,
"metadata": {},
"outputs": [],
"source": [
"from psitip import *\n",
"PsiOpts.setting(\n",
" solver = \"ortools.GLOP\", # Set linear programming solver\n",
" repr_latex = True, # Jupyter Notebook LaTeX display\n",
" venn_latex = True, # LaTeX in diagrams\n",
" proof_note_color = \"blue\", # Reasons in proofs are blue\n",
" solve_display_reg = True, # Display claims in solve commands\n",
" random_seed = 4321 # Random seed for example searching\n",
")"
]
},
{
"cell_type": "code",
"execution_count": 2,
"metadata": {},
"outputs": [
{
"data": {
"image/svg+xml": [
"\r\n",
"\r\n",
"\r\n",
"\r\n",
"\r\n"
],
"text/plain": [
""
]
},
"execution_count": 2,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"X, Y, U = rv(\"X, Y, U\")\n",
"M0, M1, M2 = rv_array(\"M\", 3)\n",
"R0, R1, R2 = real_array(\"R\", 3)\n",
"\n",
"model = CodingModel() # Define Gray-Wyner system\n",
"model.set_rate(M0, R0) # The rate of M0, M1, M2 are R0, R1, R2 resp.\n",
"model.set_rate(M1, R1)\n",
"model.set_rate(M2, R2)\n",
"model.add_edge(X, Y) # X, Y are correlated source\n",
"model.add_node(X+Y, M0+M1+M2,\n",
" label = \"Enc\") # Encoder maps X,Y to M0,M1,M2\n",
"model.add_node(M0+M1, X,\n",
" label = \"Dec 1\") # Decoder 1 maps M0,M1 to X\n",
"model.add_node(M0+M2, Y,\n",
" label = \"Dec 2\") # Decoder 2 maps M0,M2 to Y\n",
"\n",
"model.graph() # Draw diagram"
]
},
{
"cell_type": "code",
"execution_count": 3,
"metadata": {},
"outputs": [
{
"data": {
"text/latex": [
"$\\exists A_{M_0}:\\, \\left\\{\\begin{array}{l}\n",
" R_0 \\ge 0,\\\\\n",
" R_1 \\ge 0,\\\\\n",
" R_2 \\ge 0,\\\\\n",
" R_0+R_1 \\ge H(X)+I(A_{M_0}; Y|X),\\\\\n",
" R_0+R_2 \\ge H(Y)+I(A_{M_0}; X|Y),\\\\\n",
" R_0+R_1+R_2 \\ge H(X)+H(Y|A_{M_0})+I(A_{M_0}; Y|X)\\\\\n",
"\\end{array} \\right\\}$"
],
"text/plain": [
"( ( R_0 >= 0 )\n",
" &( R_1 >= 0 )\n",
" &( R_2 >= 0 )\n",
" &( R_0+R_1 >= H(X)+I(A_M_0&Y|X) )\n",
" &( R_0+R_2 >= H(Y)+I(A_M_0&X|Y) )\n",
" &( R_0+R_1+R_2 >= H(X)+H(Y|A_M_0)+I(A_M_0&Y|X) ) ).exists(A_M_0)"
]
},
"execution_count": 3,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"r = model.get_inner() # Automatic inner bound\n",
"r"
]
},
{
"cell_type": "code",
"execution_count": 4,
"metadata": {},
"outputs": [
{
"data": {
"text/latex": [
"$\\exists U:\\, \\left\\{\\begin{array}{l}\n",
" R_0 \\ge I(X, Y; U),\\\\\n",
" R_1 \\ge H(X|U),\\\\\n",
" R_2 \\ge H(Y|U)\\\\\n",
"\\end{array} \\right\\}$"
],
"text/plain": [
"( ( R_0 >= I(X+Y&U) )\n",
" &( R_1 >= H(X|U) )\n",
" &( R_2 >= H(Y|U) ) ).exists(U)"
]
},
"execution_count": 4,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"# Although the above region does not look like the Gray-Wyner region [Gray-Wyner 1974],\n",
"# they are actually equivalent.\n",
"\n",
"# Write the Gray-Wyner region\n",
"r_gw = ((R0 >= I(X+Y&U)) & (R1 >= H(X|U)) & (R2 >= H(Y|U))).exists(U)\n",
"r_gw"
]
},
{
"cell_type": "code",
"execution_count": 5,
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"True\n",
"True\n"
]
}
],
"source": [
"# Prove r is the same region as r_gw\n",
"print(bool(r >> r_gw)) # r implies r_gw\n",
"print(bool(r_gw >> r)) # r_gw implies r"
]
},
{
"cell_type": "code",
"execution_count": 6,
"metadata": {},
"outputs": [
{
"data": {
"text/latex": [
"$\\exists A:\\, \\left\\{\\begin{array}{l}\n",
" R_1 \\ge H(X|A),\\\\\n",
" R_2 \\ge H(Y|A),\\\\\n",
" R_0 \\ge I(A; X, Y)\\\\\n",
"\\end{array} \\right\\}$"
],
"text/plain": [
"( ( R_1 >= H(X|A) )\n",
" &( R_2 >= H(Y|A) )\n",
" &( R_0 >= I(A&X+Y) ) ).exists(A)"
]
},
"execution_count": 6,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"# Automatic outer bound with 1 auxiliary, coincides with inner bound\n",
"model.get_outer(1)"
]
},
{
"cell_type": "code",
"execution_count": 7,
"metadata": {},
"outputs": [
{
"data": {
"text/latex": [
"$A_{M_0} := (X_P, M_0)$"
],
"text/plain": [
"CompArray(\n",
"[[A_M_0, X_P+M_0]])"
]
},
"execution_count": 7,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"(model.get_outer() >> r).check_getaux_array() # Converse proof, print auxiliary"
]
},
{
"cell_type": "code",
"execution_count": 8,
"metadata": {},
"outputs": [
{
"data": {
"text/latex": [
"$\\displaystyle \\begin{align*}\n",
"&1.\\;\\text{Claim:}\\\\\n",
"&\\exists U:\\, \\left\\{\\begin{array}{l}\n",
" R_0 \\ge I(X, Y; U),\\\\\n",
" R_1 \\ge H(X|U),\\\\\n",
" R_2 \\ge H(Y|U)\\\\\n",
"\\end{array} \\right\\}\\\\\n",
"\\\\\n",
"&\\;\\;1.1.\\;\\text{Substitute }U := (X_P, Y_P, M_0)\\text{:}\\\\\n",
"\\\\\n",
"&\\;\\;1.2.\\;\\text{Steps: }\\\\\n",
"&\\;\\;R_0\\\\\n",
"&\\;\\;\\ge I(M_0; X, Y|X_P, Y_P)\\;\\;\\;{\\color{blue}{\\left(\\because\\,\\text{rate of }M_0\\text{:}\\, R_0 \\ge I(M_0; X, Y|X_P, Y_P)\\right)}}\\\\\n",
"&\\;\\;\\ge I(M_0, X_P, Y_P; X, Y)-I(X, Y; X_F, X_P, Y_P)\\\\\n",
"&\\;\\;= I(Q_o; X, Y|X_F, X_P, Y_P)+I(M_0, X_P, Y_P; X, Y)\\;\\;\\;{\\color{blue}{\\left(\\because\\, (X, Y) {\\perp\\!\\!\\perp} (X_P, Y_P, X_F, Q_o)\\right)}}\\\\\n",
"&\\;\\;= I(M_0, X_P, Y_P; X, Y)\\;\\;\\;{\\color{blue}{\\left(\\because\\, (X, Y) \\leftrightarrow (Y_P, X_F, X_P) \\leftrightarrow Q_o\\right)}}\\\\\n",
"\\\\\n",
"&\\;\\;1.3.\\;\\text{Steps: }\\\\\n",
"&\\;\\;R_1\\\\\n",
"&\\;\\;\\ge I(M_1; X, Y|M_0, X_P, Y_P)\\;\\;\\;{\\color{blue}{\\left(\\because\\,\\text{rate of }M_1\\text{:}\\, R_1 \\ge I(M_1; X, Y|X_P, Y_P, M_0)\\right)}}\\\\\n",
"&\\;\\;\\ge I(M_1; X|M_0, X_P, Y_P)\\\\\n",
"&\\;\\;= H(X|M_0, X_P, Y_P)\\;\\;\\;{\\color{blue}{\\left(\\because\\, H(X|Y_P, M_1, M_0, X_P) = 0\\right)}}\\\\\n",
"\\\\\n",
"&\\;\\;1.4.\\;\\text{Steps: }\\\\\n",
"&\\;\\;R_2\\\\\n",
"&\\;\\;\\ge I(M_2; X, Y|M_0, X_P, Y_P)\\;\\;\\;{\\color{blue}{\\left(\\because\\,\\text{rate of }M_2\\text{:}\\, R_2 \\ge I(M_2; X, Y|X_P, Y_P, M_0)\\right)}}\\\\\n",
"&\\;\\;\\ge I(M_2; Y|M_0, X_P, Y_P)\\\\\n",
"&\\;\\;= H(Y|M_0, X_P, Y_P)\\;\\;\\;{\\color{blue}{\\left(\\because\\, H(Y|M_2, M_0, X_P, Y_P) = 0\\right)}}\\\\\n",
"\\end{align*}\n",
"$"
],
"text/plain": [
""
]
},
"metadata": {},
"output_type": "display_data"
}
],
"source": [
"# Output converse proof (is_proof = True for shorter proof)\n",
"# Lower search level to avoid modification to regions\n",
"with PsiOpts(auxsearch_level = 1):\n",
" (model.get_outer(is_proof = True) >> r_gw).proof().display()"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"### Extremal Points and Corner Points"
]
},
{
"cell_type": "code",
"execution_count": 9,
"metadata": {},
"outputs": [
{
"data": {
"text/latex": [
"$H(X, Y)$"
],
"text/plain": [
"H(X+Y)"
]
},
"execution_count": 9,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"# Minimum sum rate is H(X, Y)\n",
"sumrate = r.minimum(R0 + R1 + R2, [R0, R1, R2])\n",
"sumrate"
]
},
{
"cell_type": "code",
"execution_count": 10,
"metadata": {},
"outputs": [
{
"data": {
"text/latex": [
"$H(X)+H(Y)$"
],
"text/plain": [
"H(X)+H(Y)"
]
},
"execution_count": 10,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"# Minimum weighted sum rate when R0 is counted twice is H(X)+H(Y)\n",
"wsumrate = r.minimum(R0 * 2 + R1 + R2, [R0, R1, R2])\n",
"wsumrate"
]
},
{
"cell_type": "code",
"execution_count": 11,
"metadata": {},
"outputs": [
{
"data": {
"text/latex": [
"$\\inf_{A_{M_0}}\\max\\left(\\frac{1}{2}H(X)+\\frac{1}{2}I(A_{M_0}; Y|X),\\, \\frac{1}{2}H(Y)+\\frac{1}{2}I(A_{M_0}; X|Y),\\, \\frac{1}{3}H(X)+\\frac{1}{3}H(Y|A_{M_0})+\\frac{1}{3}I(A_{M_0}; Y|X)\\right)$"
],
"text/plain": [
"(( universe() ).exists(A_M_0)).minimum(emax((1/2)*H(X)+(1/2)*I(A_M_0&Y|X), (1/2)*H(Y)+(1/2)*I(A_M_0&X|Y), (1/3)*H(X)+(1/3)*H(Y|A_M_0)+(1/3)*I(A_M_0&Y|X)))"
]
},
"execution_count": 11,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"# Minimum symmetric rate\n",
"symrate = r.minimum(emax(R0, R1, R2), [R0, R1, R2])\n",
"symrate"
]
},
{
"cell_type": "code",
"execution_count": 12,
"metadata": {},
"outputs": [
{
"data": {
"text/latex": [
"$\\sup_{A_{M_0}:\\, A_{M_0} \\leftrightarrow X \\leftrightarrow Y,\\; A_{M_0} \\leftrightarrow Y \\leftrightarrow X}I(A_{M_0}; Y)$"
],
"text/plain": [
"(( ( markov(A_M_0, X, Y) )\n",
" &( markov(A_M_0, Y, X) ) ).exists(A_M_0)).maximum(I(A_M_0&Y))"
]
},
"execution_count": 12,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"# The corner point max R0 s.t. R0 + R1 = H(X), R0 + R2 = H(Y)\n",
"corner1 = (r & (R0 + R1 == H(X)) & (R0 + R2 == H(Y))).maximum(R0, [R0, R1, R2])\n",
"corner1"
]
},
{
"cell_type": "code",
"execution_count": 13,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"True"
]
},
"execution_count": 13,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"# This is the Gacs-Korner common information [Gacs-Korner 1973]\n",
"bool(corner1 == gacs_korner(X & Y))"
]
},
{
"cell_type": "code",
"execution_count": 14,
"metadata": {},
"outputs": [
{
"data": {
"text/latex": [
"$\\inf_{A_{M_0}:\\, X \\leftrightarrow A_{M_0} \\leftrightarrow Y}I(A_{M_0}; X, Y)$"
],
"text/plain": [
"(( ( markov(X, A_M_0, Y) ) ).exists(A_M_0)).minimum(I(A_M_0&X+Y))"
]
},
"execution_count": 14,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"# The corner point min R0 s.t. R0 + R1 + R2 = H(X,Y)\n",
"corner2 = (r & (R0 + R1 + R2 == H(X+Y))).minimum(R0, [R0, R1, R2])\n",
"corner2"
]
},
{
"cell_type": "code",
"execution_count": 15,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"True"
]
},
"execution_count": 15,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"# This is Wyner's common information [Wyner 1975]\n",
"bool(corner2 == wyner_ci(X & Y))"
]
},
{
"cell_type": "code",
"execution_count": 16,
"metadata": {},
"outputs": [
{
"data": {
"text/latex": [
"$\\inf_{A_{M_0}:\\, X \\leftrightarrow A_{M_0} \\leftrightarrow Y,\\; A_{M_0} \\leftrightarrow Y \\leftrightarrow X}I(A_{M_0}; Y)$"
],
"text/plain": [
"(( ( markov(X, A_M_0, Y) )\n",
" &( markov(A_M_0, Y, X) ) ).exists(A_M_0)).minimum(I(A_M_0&Y))"
]
},
"execution_count": 16,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"# The corner point min R0 s.t. R0 + R2 = H(Y), R1 = H(X|Y)\n",
"corner3 = (r & (R0 + R2 == H(Y)) & (R1 == H(X|Y))).minimum(R0, [R0, R1, R2])\n",
"corner3"
]
},
{
"cell_type": "code",
"execution_count": 17,
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"True\n",
"True\n"
]
}
],
"source": [
"# This is the necessary conditional entropy [Cuff-Permuter-Cover 2010] plus I(X;Y)\n",
"# We need the double Markov property [Csiszar-Korner 2011] to prove this\n",
"with dblmarkov().assumed():\n",
" print(bool(corner3 <= H_nec(Y | X) + I(X & Y)))\n",
" print(bool(corner3 >= H_nec(Y | X) + I(X & Y)))"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"### References\n",
"- A. El Gamal and Y.-H. Kim, _Network Information Theory_, Cambridge University Press, 2011, Ch. 14.\n",
"- R. M. Gray and A. D. Wyner, \"Source coding for a simple network,\" Bell Syst. Tech. J., vol. 53, no. 9, pp. 1681–1721, 1974.\n",
"- P. Gács and J. Körner, \"Common information is far less than mutual information,\" Problems Control Inf. Theory, vol. 2, no. 2, pp. 149–162, 1973.\n",
"- A. D. Wyner, \"The common information of two dependent random variables,\" IEEE Trans. Inf. Theory, vol. IT-21, no. 2, pp. 163–179, Mar. 1975.\n",
"- P. W. Cuff, H. H. Permuter, and T. M. Cover, \"Coordination capacity,\" IEEE Trans. Inf. Theory, vol. 56, no. 9, pp. 4181–4206, Sep. 2010.\n",
"- C. T. Li and A. El Gamal, \"Extended Gray–Wyner system with complementary causal side information,\" IEEE Trans. Inf. Theory, vol. 64, no. 8, pp. 5862–5878, 2017\n",
"- I. Csiszár and J. Körner, \"Information theory: coding theorems for discrete memoryless systems,\" Cambridge University Press, 2011.\n"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": []
}
],
"metadata": {
"kernelspec": {
"display_name": "Python 3",
"language": "python",
"name": "python3"
},
"language_info": {
"codemirror_mode": {
"name": "ipython",
"version": 3
},
"file_extension": ".py",
"mimetype": "text/x-python",
"name": "python",
"nbconvert_exporter": "python",
"pygments_lexer": "ipython3",
"version": "3.8.3"
}
},
"nbformat": 4,
"nbformat_minor": 4
}