Rate-Distortion Computation and Statistical Physics
A new approach to rate-distortion computation and analysis is suggested in this work. We shall restrict our attention here to continuous amplitude memoryless sources. Much of the existing theory is formulated in terms of optimization over the output density, particularly the results leading to the Blahut algorithm. In the new approach we consider a mapping from the unit interval with the Lebesgue measure, to the output space. Instead of optimizing the output density directly, we optimize this mapping. The theoretical equivalence of the mapping approach (MA) to the traditional approach is intuitively obvious but can be formally shown by isomorphism theorems for topological measure spaces. Although equivalent in principle, the MA formulation is different, and by deriving the results from this angle, some new insights are gained, as well as a more efficient numerical approach to compute the rate-distortion function. First, the mapping approach is presented arid its equivalence to the usual approach is discussed. The optimality conditions are derived and are shown to be random-coding relatives of the Lloyd optimality conditions for optimal quantizer design. Next, the MA formulation is used to prove that, for the squared error distortion, the optimizing output density is purely discrete as long as Ihe rate-distortion function has not merged ,with the Shannon lower bound. In other words, except for the case that the bound i F attained (e.g., Gaussian source for all positive rates), the output density consists of singularities. This could explain why explicit expressions for the rate-distortion function are so hard to obtain. In a paper that recently came to my attention [l], it is shown (using a different approach) that the optimizing output is discrete if the source density’s support is not the entire space. This result is a special case of our result here, as for such sources the Shannon lower bound is strictly lower than the rate-distortion function at all nonzero distortions. We then address the analysis of the evolution of the optimizing output densities as we decrease the distortion (that is, as we “crawl up” the rate-distortion curve). Here we start by showing that. the functional that is minimized to find the optimizing density is the free energy of an appropriately defined statistical mechanics system. The slope parameter is simply related to the temperature in the physical analogy, and the optimizing output density is given by the isothermal equilibrium distribution at the given temperature. Thus, “crawling up” the rate-distortion curve is simply an annealing process in statistical mechanics. The analysis shows that the annealing process starts with a single output symbol at R = 0, and consists of a sequence of phase transitions which increase the number of symbols (or singularities) by splitting them. It is shown that the last phase transition occurs when the rate-distortion curve hits the Shannon lower bound, and where the singularities split, or rather, explode into a continuous distribution. Finally, we discuss the applicability of the mapping approach to practical computation of rate-distortion functions. Discretization for numerical computation results in an algorithm whose performance differs from that of the Blahut algorithm (BA). BA optimizes over a grid of points in the output space to obtain an approximate solution (whose quality depends on the resolution of the grid). MA uses the mapping which adapts its effective grid to the source distribution and so is more efficient. Moreover, as long as the Shannon lower bound is not attained, the optimal density is discrete (and usual1.y finite) so that few variables allow MA to find the exact solution, which BA approximates using the entire grid. Note also that once the Shannon lower bound is attained we can explicitly derive the solution, so numerical evaluation is no longer necessary. The MA based algorithm is closely related to our VQ design method [2]. Another relative is [3] where the derivation is constrained to a given alphabet size. The MA method allows the number of symbols to grow as necessary to obtain the unconstrained rate-distortion result.