Technical Program

Paper Detail

Paper IDO.5.1
Paper Title On Effective Stochastic Mechanisms for On-The-Fly Codebook Regeneration
Authors Ahmed Elshafiy, Mahmoud Namazi, Kenneth Rose, University of California, Santa Barbara, United States
Session O.5: Topics in Source Coding
Presentation Lecture
Track Source Coding
Manuscript  Click here to download the manuscript
Virtual Presentation  Click here to watch in the Virtual Symposium
Abstract This paper proposes an effective mechanism for stochastic codebook generation for lossy coding, using source examples. Earlier work has shown that the rate-distortion bound can be asymptotically achieved by a ``natural type selection'' (NTS) mechanism which iteratively considers asymptotically long source strings (from given distribution $P$) and regenerates the codebook according to the type of the first codeword to ``$d$-match'' the source string (i.e., satisfy the distortion constraint), where the sequence of codebook generating types converges to the optimal reproduction distribution. While ensuring optimality, earlier results had a significant practical flaw, due to the order of limits at which the convergence is achieved. More specifically, NTS iterations indexed by $n$ presume asymptotically large $\ell$, but the codebook size grows exponentially with $\ell$. The reversed order of limits is practically preferred, wherein most codebook regeneration iterations involve manageable string lengths. This work describes a dramatically more efficient mechanism to achieve the optimum within a practical framework. It is specifically shown that it is sufficient to individually encode many source strings of short fixed length $\ell$, then find the maximum likelihood estimate for the distribution $Q_{n+1}$ that would have generated the observed sequence of $d$-matching codeword strings, then use $Q_{n+1}$ to generate a new codebook for the next iteration. The sequence of distributions $Q_{1}, Q_{2}, \dots$ converges to the optimal reproduction distribution $Q_{\ell}^{*}(P,d)$, achievable at finite length $\ell$. It is further shown that $Q_{\ell}^{*}(P,d)$ converges to the optimal reproduction distribution $Q^{*}(P,d)$ that achieves the rate-distortion bound $R(P,d)$, asymptotically in string length $\ell$.

Plan Ahead


2021 IEEE International Symposium on Information Theory

11-16 July 2021 | Melbourne, Victoria, Australia

Visit Website!