Computation of Marton’s Error Exponent for Discrete Memoryless Sources

The error exponent of fixed-length lossy source coding was established by Marton. Ahlswede showed that this exponent can be discontinuous at a rate R, depending on the probability distribution P of the given information source and the distortion measure d(x, y). The reason for the discontinuity in the error exponent is that there exists (d, ∆) such that the rate-distortion function R(∆|P) is neither concave nor quasi-concave with respect to P. Arimoto’s algorithm for computing the error exponent in lossy source coding is based on Blahut’s parametric representation of the error exponent. However, Blahut’s parametric representation is a lower convex envelope of Marton’s exponent, and the two do not generally agree. The contribution of this paper is to provide a parametric representation that perfectly matches the inverse function of Marton’s exponent, thus avoiding the problem of the rate-distortion function being nonconvex with respect to P. The optimal distribution for fixed parameters can be obtained using Arimoto’s algorithm. Performing a nonconvex optimization over the parameters successfully yields the inverse function of Marton’s exponent.