{ "cells": [ { "cell_type": "markdown", "metadata": {}, "source": [ "## Distributed Lossy Compression Demo\n", "\n", "Author: Cheuk Ting Li " ] }, { "cell_type": "code", "execution_count": 1, "metadata": {}, "outputs": [], "source": [ "from psitip import *\n", "PsiOpts.setting(solver = \"pyomo.glpk\") # Set linear programming solver\n", "PsiOpts.setting(repr_latex = True) # Jupyter Notebook LaTeX display\n", "PsiOpts.setting(venn_latex = True) # LaTeX in diagrams\n", "PsiOpts.setting(proof_note_color = \"blue\") # Reasons in proofs are blue" ] }, { "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", "X1@@4@@X_1\r\n", "X1\r\n", "\r\n", "\r\n", "X2@@4@@X_2\r\n", "X2\r\n", "\r\n", "\r\n", "X1@@4@@X_1->X2@@4@@X_2\r\n", "\r\n", "\r\n", "\r\n", "\r\n", "enc_X1_M1\r\n", "\r\n", "Enc 1\r\n", "\r\n", "\r\n", "X1@@4@@X_1->enc_X1_M1\r\n", "\r\n", "\r\n", "\r\n", "\r\n", "enc_X2_M2\r\n", "\r\n", "Enc 2\r\n", "\r\n", "\r\n", "X2@@4@@X_2->enc_X2_M2\r\n", "\r\n", "\r\n", "\r\n", "\r\n", "M1@@4@@M_1\r\n", "M1\r\n", "\r\n", "\r\n", "enc_M1+M2_Y1+Y2\r\n", "\r\n", "Dec\r\n", "\r\n", "\r\n", "M1@@4@@M_1->enc_M1+M2_Y1+Y2\r\n", "\r\n", "\r\n", "\r\n", "\r\n", "M2@@4@@M_2\r\n", "M2\r\n", "\r\n", "\r\n", "M2@@4@@M_2->enc_M1+M2_Y1+Y2\r\n", "\r\n", "\r\n", "\r\n", "\r\n", "Y1@@4@@Y_1\r\n", "Y1\r\n", "\r\n", "\r\n", "Y2@@4@@Y_2\r\n", "Y2\r\n", "\r\n", "\r\n", "enc_X1_M1->M1@@4@@M_1\r\n", "\r\n", "\r\n", "\r\n", "\r\n", "enc_X2_M2->M2@@4@@M_2\r\n", "\r\n", "\r\n", "\r\n", "\r\n", "enc_M1+M2_Y1+Y2->Y1@@4@@Y_1\r\n", "\r\n", "\r\n", "\r\n", "\r\n", "enc_M1+M2_Y1+Y2->Y2@@4@@Y_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", "Y1, Y2 = rv_array(\"Y\", 1, 3)\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, Y1+Y2,\n", " label = \"Dec\") # Decoder maps M1,M2 to X1,X2\n", "\n", "model.graph() # Draw diagram" ] }, { "cell_type": "code", "execution_count": 3, "metadata": {}, "outputs": [ { "data": { "text/latex": [ "$\\exists A_{M_1}, A_{M_2}, Q_i:\\, \\left\\{\\begin{array}{l}\n", " R_1 \\ge I(A_{M_1}; X_1|A_{M_2}, Q_i),\\\\\n", " R_2 \\ge I(A_{M_2}; X_2|A_{M_1}, Q_i),\\\\\n", " R_1+R_2 \\ge I(A_{M_1}, A_{M_2}; X_1, X_2|Q_i),\\\\\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 (Y_1, Y_2)\\\\\n", "\\end{array} \\right\\}$" ], "text/plain": [ "( ( R1 >= I(A_M1&X1|A_M2+Q_i) )\n", " &( R2 >= I(A_M2&X2|A_M1+Q_i) )\n", " &( R1+R2 >= I(A_M1+A_M2&X1+X2|Q_i) )\n", " &( indep(Q_i, X1+X2) )\n", " &( markov(X1, Q_i+X2, A_M2) )\n", " &( markov(X2+A_M2, Q_i+X1, A_M1) )\n", " &( markov(X1+X2, Q_i+A_M1+A_M2, Y1+Y2) ) ).exists(A_M1+A_M2+Q_i)" ] }, "execution_count": 3, "metadata": {}, "output_type": "execute_result" } ], "source": [ "# Automatic inner bound, give Berger-Tung inner bound [Berger 1978], [Tung 1978]\n", "r = model.get_inner(convexify = True)\n", "r" ] }, { "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 (Y_1, Y_2),\\\\\n", " U_2 \\leftrightarrow X_2 \\leftrightarrow X_1\\\\\n", "\\end{array} \\right\\}$" ], "text/plain": [ "( ( R1 >= I(X1+X2&U1|U2) )\n", " &( R2 >= I(X1+X2&U2|U1) )\n", " &( R1+R2 >= I(X1+X2&U1+U2) )\n", " &( markov(U1, X1, X2) )\n", " &( markov(X1+X2, U1+U2, Y1+Y2) )\n", " &( markov(U2, X2, X1) ) ).exists(U1+U2)" ] }, "execution_count": 4, "metadata": {}, "output_type": "execute_result" } ], "source": [ "# Write the Berger-Tung outer bound [Berger 1978], [Tung 1978]\n", "r_bt_out = alland([\n", " R1 >= I(X1+X2 & U1 | U2),\n", " R2 >= I(X1+X2 & U2 | U1),\n", " R1+R2 >= I(X1+X2 & U1+U2),\n", " markov(Y1+Y2, 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": 7, "metadata": {}, "outputs": [ { "data": { "text/latex": [ "$\\left\\{ \\begin{array}{ll}\n", "U_1 & := (X_{1P}, M_1)\\\\\n", "U_2 & := (X_{1P}, M_2)\\end{array}\\right.$" ], "text/plain": [ "CompArray(\n", "[[U1, X1_P+M1],\n", " [U2, X1_P+M2]])" ] }, "execution_count": 7, "metadata": {}, "output_type": "execute_result" } ], "source": [ "r_out = model.get_outer(future = False) # Automatic outer bound\n", "\n", "# Proof that Berger-Tung outer bound is an outer bound\n", "(r_out >> r_bt_out).check_getaux_array()" ] }, { "cell_type": "code", "execution_count": 6, "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 (Y_1, Y_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, X_2|M_2, X_{1P})\\;\\;\\;{\\color{blue}{\\left(\\because\\, M_1 \\leftrightarrow (X_1, X_{1P}, M_2) \\leftrightarrow 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_2 {\\perp\\!\\!\\perp} X_{2P}\\right)}}\\\\\n", "&\\;\\;= I(M_2, X_{1P}, X_{2P}; X_2)\\;\\;\\;{\\color{blue}{\\left(\\because\\, X_2 \\leftrightarrow (M_2, X_{2P}) \\leftrightarrow X_{1P}\\right)}}\\\\\n", "&\\;\\;\\ge I(M_2, X_{1P}; X_2)\\\\\n", "&\\;\\;\\ge I(M_2; X_2|X_{1P})\\\\\n", "&\\;\\;\\ge I(M_2; X_{1P}, X_2)-I(M_2; M_1, X_{1P})\\\\\n", "&\\;\\;= I(M_2; X_1, X_2|M_1, X_{1P})\\;\\;\\;{\\color{blue}{\\left(\\because\\, (X_1, M_1) \\leftrightarrow (X_2, X_{1P}) \\leftrightarrow M_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_2 {\\perp\\!\\!\\perp} X_{2P}\\right)}}\\\\\n", "&\\;\\;= I(M_1; X_1|M_2, X_{1P})+I(M_2, X_{1P}, X_{2P}; X_2)\\;\\;\\;{\\color{blue}{\\left(\\because\\, X_2 \\leftrightarrow (M_2, X_{2P}) \\leftrightarrow X_{1P}\\right)}}\\\\\n", "&\\;\\;\\ge I(X_{1P}; X_2)+I(M_2; X_{1P}, X_2)+I(M_1, M_2; X_1|X_{1P})-I(M_2; X_1, X_{1P})\\\\\n", "&\\;\\;\\ge I(M_2; X_{1P}, X_2)+I(M_1, M_2; X_1|X_{1P})-I(M_2; X_1, X_{1P})\\\\\n", "&\\;\\;= I(M_1, M_2; X_1|X_{1P})+I(M_2; M_1, X_2|X_1, X_{1P})\\;\\;\\;{\\color{blue}{\\left(\\because\\, (X_1, M_1) \\leftrightarrow (X_2, X_{1P}) \\leftrightarrow M_2\\right)}}\\\\\n", "&\\;\\;= I(M_1; X_1|X_{1P})+I(M_2; X_1, X_2|M_1, X_{1P})\\;\\;\\;{\\color{blue}{\\left(\\because\\, M_2 \\leftrightarrow (X_1, X_{1P}) \\leftrightarrow M_1\\right)}}\\\\\n", "&\\;\\;= I(M_1, M_2; X_1, X_2|X_{1P})\\;\\;\\;{\\color{blue}{\\left(\\because\\, M_1 \\leftrightarrow (X_1, X_{1P}) \\leftrightarrow X_2\\right)}}\\\\\n", "&\\;\\;= I(M_1, M_2, X_{1P}; X_1, X_2)\\;\\;\\;{\\color{blue}{\\left(\\because\\, X_{1P} {\\perp\\!\\!\\perp} (X_1, X_2)\\right)}}\\\\\n", "\\end{align*}\n", "$" ], "text/plain": [ "" ] }, "execution_count": 6, "metadata": {}, "output_type": "execute_result" } ], "source": [ "# Output proof of Berger-Tung outer bound\n", "(r_out >> r_bt_out).proof()" ] }, { "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 }