{ "cells": [ { "cell_type": "markdown", "metadata": {}, "source": [ "## Ch 12 - Distributed Lossy Compression\n", "\n", "Reference: Ch 12 of A. El Gamal and Y.-H. Kim, _Network Information Theory_, Cambridge University Press, 2011.\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", ")" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### Thm 12.1 (Berger-Tung Inner Bound)" ] }, { "cell_type": "code", "execution_count": 2, "metadata": {}, "outputs": [ { "data": { "image/svg+xml": [ "\r\n", "\r\n", "\r\n", "\r\n", "\r\n", "\r\n", "%3\r\n", "\r\n", "\r\n", "X_1@@4@@X_1\r\n", "X_1\r\n", "\r\n", "\r\n", "X_2@@4@@X_2\r\n", "X_2\r\n", "\r\n", "\r\n", "X_1@@4@@X_1->X_2@@4@@X_2\r\n", "\r\n", "\r\n", "\r\n", "\r\n", "enc_X_1_M_1\r\n", "\r\n", "Enc 1\r\n", "\r\n", "\r\n", "X_1@@4@@X_1->enc_X_1_M_1\r\n", "\r\n", "\r\n", "\r\n", "\r\n", "enc_X_2_M_2\r\n", "\r\n", "Enc 2\r\n", "\r\n", "\r\n", "X_2@@4@@X_2->enc_X_2_M_2\r\n", "\r\n", "\r\n", "\r\n", "\r\n", "M_1@@4@@M_1\r\n", "M_1\r\n", "\r\n", "\r\n", "enc_M_1+M_2_Xh1+Xh2\r\n", "\r\n", "Dec\r\n", "\r\n", "\r\n", "M_1@@4@@M_1->enc_M_1+M_2_Xh1+Xh2\r\n", "\r\n", "\r\n", "\r\n", "\r\n", "M_2@@4@@M_2\r\n", "M_2\r\n", "\r\n", "\r\n", "M_2@@4@@M_2->enc_M_1+M_2_Xh1+Xh2\r\n", "\r\n", "\r\n", "\r\n", "\r\n", "Xh1@@4@@\\hat{X}_1\r\n", "Xh1\r\n", "\r\n", "\r\n", "Xh2@@4@@\\hat{X}_2\r\n", "Xh2\r\n", "\r\n", "\r\n", "enc_X_1_M_1->M_1@@4@@M_1\r\n", "\r\n", "\r\n", "\r\n", "\r\n", "enc_X_2_M_2->M_2@@4@@M_2\r\n", "\r\n", "\r\n", "\r\n", "\r\n", "enc_M_1+M_2_Xh1+Xh2->Xh1@@4@@\\hat{X}_1\r\n", "\r\n", "\r\n", "\r\n", "\r\n", "enc_M_1+M_2_Xh1+Xh2->Xh2@@4@@\\hat{X}_2\r\n", "\r\n", "\r\n", "\r\n", "\r\n", "\r\n" ], "text/plain": [ "" ] }, "execution_count": 2, "metadata": {}, "output_type": "execute_result" } ], "source": [ "X1, X2 = rv_array(\"X\", 1, 3)\n", "Xh1, Xh2 = rv(\"Xh1\", latex=\"\\hat{X}_1\"), rv(\"Xh2\", latex=\"\\hat{X}_2\")\n", "M1, M2 = rv_array(\"M\", 1, 3)\n", "R1, R2 = real_array(\"R\", 1, 3)\n", "U1, U2 = rv_array(\"U\", 1, 3)\n", "Q = rv(\"Q\")\n", "\n", "model = CodingModel() # Define distributed lossy compression\n", "model.set_rate(M1, R1) # The rate of M1, M2 are R1, R2 resp.\n", "model.set_rate(M2, R2)\n", "model.add_edge(X1, X2) # X1, X2 are correlated source\n", "model.add_node(X1, M1,\n", " label = \"Enc 1\") # Encoder 1 maps X1 to M1\n", "model.add_node(X2, M2,\n", " label = \"Enc 2\") # Encoder 2 maps X2 to M2\n", "model.add_node(M1+M2, Xh1+Xh2,\n", " label = \"Dec\") # Decoder maps M1,M2 to Xh1,Xh2\n", "\n", "model.graph() # Draw diagram" ] }, { "cell_type": "code", "execution_count": 3, "metadata": {}, "outputs": [ { "data": { "text/latex": [ "$\\displaystyle \\begin{array}{l}\n", "{\\color{blue}{\\text{Codebook:}}}\\\\\n", "{\\color{blue}{\\;\\;A_{M_1}[i_1], M_1[i_1]\\text{,}\\,\\text{rate = }I(A_{M_1}; X_1|Q_i)}}\\\\\n", "{\\color{blue}{\\;\\;A_{M_2}[i_2], M_2[i_2]\\text{,}\\,\\text{rate = }I(A_{M_2}; X_2|Q_i)}}\\\\\n", "{\\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}}}\\\\\n", "{\\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}}}\\\\\n", "{\\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}}}\\\\\n", "{\\color{blue}{\\;\\;\\;\\;\\text{generates}\\,\\hat{X}_1\\,\\text{from}\\,A_{M_2}, A_{M_1}}}\\\\\n", "{\\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}}}\\\\\n", "{\\color{blue}{\\;\\;\\;\\;\\text{generates}\\,\\hat{X}_2\\,\\text{from}\\,\\hat{X}_1, A_{M_2}, A_{M_1}}}\\\\\n", "\\exists A_{M_1}, A_{M_2}, Q_i:\\, \\left\\{\\begin{array}{l}\n", " \\begin{array}{l}\n", "R_1 \\ge I(A_{M_1}; X_1|A_{M_2}, Q_i)\\\\\n", "{\\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)}}\n", "\\end{array},\\\\\n", " \\begin{array}{l}\n", "R_2 \\ge I(A_{M_2}; X_2|A_{M_1}, Q_i)\\\\\n", "{\\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)}}\n", "\\end{array},\\\\\n", " \\begin{array}{l}\n", "R_1+R_2 \\ge I(A_{M_2}; X_2|Q_i)+I(A_{M_1}; X_1|A_{M_2}, Q_i)\\\\\n", "{\\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)}}\n", "\\end{array},\\\\\n", " Q_i {\\perp\\!\\!\\perp} (X_1, X_2),\\\\\n", " X_1 \\leftrightarrow (Q_i, X_2) \\leftrightarrow A_{M_2},\\\\\n", " (X_2, A_{M_2}) \\leftrightarrow (Q_i, X_1) \\leftrightarrow A_{M_1},\\\\\n", " (X_1, X_2) \\leftrightarrow (Q_i, A_{M_1}, A_{M_2}) \\leftrightarrow (\\hat{X}_1, \\hat{X}_2)\\\\\n", "\\end{array} \\right\\}\n", "\\end{array}$" ], "text/plain": [ "" ] }, "metadata": {}, "output_type": "display_data" } ], "source": [ "# Automatic inner bound, give Berger-Tung inner bound [Berger 1978], [Tung 1978]\n", "r = model.get_inner(is_proof=True)\n", "r.display(note=True)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### Thm 12.2 (Berger-Tung Outer Bound)" ] }, { "cell_type": "code", "execution_count": 4, "metadata": {}, "outputs": [ { "data": { "text/latex": [ "$\\exists U_1, U_2:\\, \\left\\{\\begin{array}{l}\n", " R_1 \\ge I(X_1, X_2; U_1|U_2),\\\\\n", " R_2 \\ge I(X_1, X_2; U_2|U_1),\\\\\n", " R_1+R_2 \\ge I(X_1, X_2; U_1, U_2),\\\\\n", " U_1 \\leftrightarrow X_1 \\leftrightarrow X_2,\\\\\n", " (X_1, X_2) \\leftrightarrow (U_1, U_2) \\leftrightarrow (\\hat{X}_1, \\hat{X}_2),\\\\\n", " U_2 \\leftrightarrow X_2 \\leftrightarrow X_1\\\\\n", "\\end{array} \\right\\}$" ], "text/plain": [ "( ( R_1 >= I(X_1+X_2&U_1|U_2) )\n", " &( R_2 >= I(X_1+X_2&U_2|U_1) )\n", " &( R_1+R_2 >= I(X_1+X_2&U_1+U_2) )\n", " &( markov(U_1, X_1, X_2) )\n", " &( markov(X_1+X_2, U_1+U_2, Xh1+Xh2) )\n", " &( markov(U_2, X_2, X_1) ) ).exists(U_1+U_2)" ] }, "execution_count": 4, "metadata": {}, "output_type": "execute_result" } ], "source": [ "# Write the Berger-Tung outer bound [Berger 1978], [Tung 1978]\n", "r_bt_out = region(\n", " R1 >= I(X1+X2 & U1 | U2),\n", " R2 >= I(X1+X2 & U2 | U1),\n", " R1+R2 >= I(X1+X2 & U1+U2),\n", " markov(Xh1+Xh2, U1+U2, X1+X2),\n", " markov(U1, X1, X2),\n", " markov(U2, X2, X1)\n", " ).exists(U1+U2)\n", "r_bt_out" ] }, { "cell_type": "code", "execution_count": 5, "metadata": {}, "outputs": [ { "data": { "text/latex": [ "$\\begin{align*}\n", "&1.\\;\\text{Claim:}\\\\\n", "&\\exists U_1, U_2:\\, \\left\\{\\begin{array}{l}\n", " R_1 \\ge I(U_1; X_1, X_2|U_2),\\\\\n", " R_2 \\ge I(U_2; X_1, X_2|U_1),\\\\\n", " R_1+R_2 \\ge I(U_1, U_2; X_1, X_2),\\\\\n", " U_1 \\leftrightarrow X_1 \\leftrightarrow X_2,\\\\\n", " (X_1, X_2) \\leftrightarrow (U_1, U_2) \\leftrightarrow (\\hat{X}_1, \\hat{X}_2),\\\\\n", " U_2 \\leftrightarrow X_2 \\leftrightarrow X_1\\\\\n", "\\end{array} \\right\\}\\\\\n", "\\\\\n", "&\\;\\;1.1.\\;\\text{Substitute }\\left\\{ \\begin{array}{ll}\n", "U_1 & := (X_{1P}, M_1)\\\\\n", "U_2 & := (X_{1P}, M_2)\\end{array}\\right.\\text{:}\\\\\n", "\\\\\n", "&\\;\\;1.2.\\;\\text{Steps: }\\\\\n", "&\\;\\;R_1\\\\\n", "&\\;\\;\\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)}}\\\\\n", "&\\;\\;= 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)}}\\\\\n", "&\\;\\;= 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)\\\\\n", "&\\;\\;\\;\\;\\;\\;\\;\\;\\;\\;{\\color{blue}{\\left(\\because\\, (X_{2P}, M_2) \\leftrightarrow X_2 \\leftrightarrow X_1\\right)}}\\\\\n", "&\\;\\;= 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})\\\\\n", "&\\;\\;\\;\\;\\;\\;\\;\\;\\;\\;{\\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)}}\\\\\n", "&\\;\\;= 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})\\\\\n", "&\\;\\;\\;\\;\\;\\;\\;\\;\\;\\;{\\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)}}\\\\\n", "&\\;\\;= 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)}}\\\\\n", "\\\\\n", "&\\;\\;1.3.\\;\\text{Steps: }\\\\\n", "&\\;\\;R_2\\\\\n", "&\\;\\;\\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)}}\\\\\n", "&\\;\\;= I(M_2, X_{2P}; X_2)\\;\\;\\;{\\color{blue}{\\left(\\because\\, X_{2P} {\\perp\\!\\!\\perp} X_2\\right)}}\\\\\n", "&\\;\\;= I(M_2, X_{2P}; X_1, X_2)\\;\\;\\;{\\color{blue}{\\left(\\because\\, (X_{2P}, M_2) \\leftrightarrow X_2 \\leftrightarrow X_1\\right)}}\\\\\n", "&\\;\\;= 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)}}\\\\\n", "&\\;\\;= 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)}}\\\\\n", "&\\;\\;\\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})\\\\\n", "&\\;\\;\\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})\\\\\n", "&\\;\\;= 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})\\\\\n", "&\\;\\;\\;\\;\\;\\;\\;\\;\\;\\;{\\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)}}\\\\\n", "&\\;\\;= 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)}}\\\\\n", "\\\\\n", "&\\;\\;1.4.\\;\\text{Steps: }\\\\\n", "&\\;\\;R_1+R_2\\\\\n", "&\\;\\;\\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)}}\\\\\n", "&\\;\\;\\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)}}\\\\\n", "&\\;\\;= 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)}}\\\\\n", "&\\;\\;= 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)}}\\\\\n", "&\\;\\;= 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})\\\\\n", "&\\;\\;\\;\\;\\;\\;\\;\\;\\;\\;{\\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)}}\\\\\n", "&\\;\\;= 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})\\\\\n", "&\\;\\;\\;\\;\\;\\;\\;\\;\\;\\;{\\color{blue}{\\left(\\because\\, M_2 \\leftrightarrow X_{2P} \\leftrightarrow X_{1P}\\right)}}\\\\\n", "&\\;\\;\\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})\\\\\n", "&\\;\\;= 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})\\\\\n", "&\\;\\;\\;\\;\\;\\;\\;\\;\\;\\;{\\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)}}\\\\\n", "&\\;\\;= 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)}}\\\\\n", "\\end{align*}\n", "$" ], "text/plain": [ "" ] }, "execution_count": 5, "metadata": {}, "output_type": "execute_result" } ], "source": [ "# Proof of outer bound\n", "model.proof_outer(r_bt_out)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### Thm 12.3 (Quadratic Gaussian Distributed Source Coding)\n", "\n", "Skipped" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### Thm 12.4 (Quadratic Gaussian CEO Problem)\n", "\n", "Skipped" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### References\n", "- A. El Gamal and Y.-H. Kim, _Network Information Theory_, Cambridge University Press, 2011, Ch. 12.\n", "- T. Berger, \"Multiterminal source coding,\" in The Information Theory Approach to Communications, G. Longo, Ed. New York: Springer-Verlag, 1978, pp. 171–231.\n", "- S.-Y. Tung, \"Multiterminal source coding,\" Ph.D. dissertation, Cornell University, Ithaca, NY, 1978.\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 }