I am having problems seeing how the Blahut-Arimoto argorithm for the calculation of $R(D)$ deals with a Bernoulli($p$) source. In particular, I am failing to see how the value of $D$ for which $RD(D)\approx 0$ that the algorithm finds makes sense.

Assume that we are dealing with a Bernoulli(.25) source, and Hamming distortion, i.e. the distortion between $x$ and $\hat{x}$, $d(x, \hat{x})$, is

\begin{equation*} d(x, \hat{x}) = \begin{cases} 0 & x = \hat{x}\\ 1 & \text{otherwise} \end{cases} \end{equation*}

In such a case if the rate is zero, any distortion $D > 0.25$ is achievable. This follows from the rate-distortion function calculated for Bernoulli(p) sources in Theorem 10.3.1 of Cover and Thomas (2006, p. 307), but it's also easy to see directly: if the encoder sends no message whatsoever, the best the decoder can do is always "decode" to the most frequent source word. For a Bernoulli(.25) source this gets it wrong .25 of the time, and hence $D=0.25$.

But now, I can't seem to get this result by running the Blahut-Arimoto algorithm. I will be using here the version in Cover and Thomas (2006, p. 334), but the relevant Wikipedia page presents the very same algorithm, as far as I can see.

We being with a choice of $\lambda=10^{-6}$ and an initial output distribution $r(\hat{x})=\text{Bernoulli}(.5)$. In the Blahut-Arimoto algorithm, the $\lambda$ gives the slope of the $R(D)$ curve at the point to be calculated. We want it to be low, so that the curve is flat---and thus $R(D)\approx 0$. Using the uniform distribution for the initial value of $r(\hat{x})$ is common in the implementations of the algorithm I have examined.

We now calculate the conditional ditribution of the channel, $q(\hat{x}|x)$, thus:

$$q(\hat{x}|x) = \frac{r(\hat{x}) e^{-\lambda d(x, \hat{x})}}{\sum_{\hat{x}} r(\hat{x}) e^{-\lambda d(x, \hat{x})}}$$

If we calculate this with the values given above, we get that

\begin{equation*} q(\hat{x} | x) = \begin{cases} 0.49999975 & x = \hat{x}\\ 0.50000025 & \text{otherwise} \end{cases} \end{equation*}

When I recalculate the output distribution for this channel, amd iterate the process, I'm stuck with the very same channel, which has an associated distortion of 0.5, higher than the correct value of 0.25. I've calculated this to an accuracy of $10^{-10}$ and still get 0.5. The analogous happens for different, small values of $\lambda$.

What am I missing?


The situation looks paradoxical because of the illogical setting of the goal.

Intuition suggests that compression of a discrete function is possible either by narrowing the discrete spectrum, or by coarsening the values at the points of the spectrum.

In this case, the chosen Blahut-Arimoto method excludes the way of a narrowing of the spectrum, and the chosen criterion of Hamming is insensitive to discretization level.

  • $\begingroup$ Thanks for your answer :) I don't think this is a matter of intuition. The B-A algorithm is (if I understood correctly) guaranteed to converge to the optimal solution which, as I show in the question, is not 0.5 for rate zero. $\endgroup$ – Schiphol Jun 3 '18 at 8:14

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.