2020 IEEE International Symposium
on Information Theory
21-26 June 2020 • Los Angeles, California, USA
| Paper ID | O.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
