Convex Optimization · Problem 4.57

Duality — Boyd & Vandenberghe

Mathematics — Optimization · capacity-communication-channel

Problem

Capacity of a communication channel. We consider a communication channel, with input X(t)∈{1,…,n}X(t) \in \{1, \ldots, n\}, and output Y(t)∈{1,…,m}Y(t) \in \{1, \ldots, m\}, for t=1,2,…t = 1, 2, \ldots (in seconds, say). The relation between the input and the output is given statistically: pij=prob(Y(t)=i∣X(t)=j),i=1,…,m,  j=1,…,n.p_{ij} = \mathbf{prob}(Y(t) = i | X(t) = j), \quad i = 1, \ldots, m, \; j = 1, \ldots, n. The matrix P∈Rm×nP \in \mathbf{R}^{m \times n} is called the channel transition matrix, and the channel is called a discrete memoryless channel. A famous result of Shannon states that information can be sent over the communication channel, with arbitrarily small probability of error, at any rate less than a number CC, called the channel capacity, in bits per second. Shannon also showed that the capacity of a discrete memoryless channel can be found by solving an optimization problem. Assume that XX has a probability distribution denoted x∈Rnx \in \mathbf{R}^n, i.e., xj=prob(X=j),j=1,…,n.x_j = \mathbf{prob}(X = j), \quad j = 1, \ldots, n. The mutual information between XX and YY is given by I(X;Y)=∑i=1m∑j=1nxjpijlog⁡2pij∑k=1nxkpik.I(X; Y) = \sum_{i=1}^m \sum_{j=1}^n x_j p_{ij} \log_2 \frac{p_{ij}}{\sum_{k=1}^n x_k p_{ik}}. Then the channel capacity CC is given by C=sup⁡xI(X;Y),C = \sup_x I(X; Y), where the supremum is over all possible probability distributions for the input XX, i.e., over x⪰0x \succeq 0, 1Tx=1\mathbf{1}^T x = 1. Show how the channel capacity can be computed using convex optimization. Hint. Introduce the variable y=Pxy = Px, which gives the probability distribution of the output YY, and show that the mutual information can be expressed as I(X;Y)=cTx−∑i=1myilog⁡2yi,I(X; Y) = c^T x - \sum_{i=1}^m y_i \log_2 y_i, where cj=∑i=1mpijlog⁡2pijc_j = \sum_{i=1}^m p_{ij} \log_2 p_{ij}, j=1,…,nj = 1, \ldots, n.

Related theory

Browse the problem library