Natural type selection in adaptive lossy compression

Consider approximate (lossy) matching of a source string ~P, with a random codebook generated from reproduction distribution Q, at a specified distortion d. Previous work determined the minimum coding rate R₁=R(P, Q, d) for this setting. We observe that for a large word length and with high probability, the matching codeword is typical with a distribution Q₁ which is different from Q. If a new random codebook is generated ~Q₁, then the source string will favor codewords which are typical with a new distribution Q₂, resulting in a minimum coding rate R₂=R(P, Q₁, d), and so on. We show that the sequences of distributions Q₁, Q ₂,... and rates R₁, R₂,..., generated by this procedure, converge to an optimum reproduction distribution Q*, and the rate-distortion function R(P, d), respectively. We also derive a fixed rate-distortion slope version of this natural type selection process. In the latter case, an iteration of the process stochastically simulates an iteration of the Blahut-Arimoto (1972) algorithm for rate-distortion function computation (without recourse to prior knowledge of the underlying source distribution). To strengthen these limit statements, we also characterize the steady-state error of these procedures when iterating at a finite string length. Implications of the main results provide fresh insights into the workings of lossy variants of the Lempel-Ziv algorithm for adaptive compression