|| Stochastic Codebook Regeneration for Sequential Compression of Continuous Alphabet Sources
||Ahmed Elshafiy, Mahmoud Namazi, University of California, Santa Barbara, United States; Ram Zamir, Tel Aviv University, Israel; Kenneth Rose, University of California, Santa Barbara, United States|
||D6-S5-T2: Rate-Distortion Theory II
||Monday, 19 July, 23:20 - 23:40
||Monday, 19 July, 23:40 - 00:00
This paper proposes an effective and asymptotically optimal framework for stochastic, adaptive codebook regeneration for sequential (``on the fly'') lossy coding of continuous alphabet sources. Earlier work has shown that the rate-distortion bound can be asymptotically achieved for discrete alphabet sources, by a “natural type selection” (NTS) algorithm. At each iteration n, a maximum-likelihood framework is used to estimate the reproduction distribution most likely to generate the empirical types of a sequence of K length-l codewords that respectively ``d-match'' (i.e., are within distortion d from) a sequence of K length-l source words. The reproduction distribution estimated at iteration n is used to regenerate the codebook for iteration n+1. The sequence of reproduction distributions was shown to converge, asymptotically in K, n, and l, to the optimal distribution that achieves the rate-distortion bound for discrete alphabet sources. This work generalizes the NTS framework to handle sources over more general (e.g., continuous) alphabet spaces, which often preclude a natural interpretation of the concept of ``type''. We show, for continuous alphabet sources and fixed block length l, that as K goes to infinity and n goes to infinity, the sequence of estimated reproduction distributions converges, in the weak convergence sense, to a distribution that achieves the rate-distortion bound, albeit for an auxiliary distortion measure introduced as subterfuge to effectively impose a maximum distortion constraint over K blocks. Leveraging this result, we establish that the sequence of reproduction distributions converges, asymptotically in l, to the optimal codebook reproduction distribution Q* that achieves the rate-distortion bound, with respect to the original distortion measure.