Iterative Computation of Scalable Rate-Disortion Bounds
Signal Compression Laboratory Research Project
| Researcher: | Ertem Tuncel |
| Faculty: | Prof. Kenneth Rose |
| Research Focus: | Scalable source coding refers to first approximating the source coarsely, and then iteratively improving the approximation as more and more information is supplied. Practical examples are TSVQ, MSVQ, wavelet based coding and all similar hierarchical coding schemes. We consider methods for determining and computing the rate-distortion (RD) bound for N-layer scalable source coding of a finite memoryless source. We derive the optimality conditions in terms of the joint N-layer reproduction distributions. We demonstrate that, it is in general impractical to validate a tentative solution, as one has to verify the conditions for all legitimate distributions conditioned on points on the i'th layer where the reproduction distribution vanishes. As an alternative computational approach, we propose an iterative algorithm that converges to the optimal joint reproduction distribution, if initialized with a distribution strictly positive everywhere. For non-scalable coding, N=1, the algorithm specializes to the well-known Blahut-Arimoto algorithm. The algorithm may be used to compute the RD bound or as an optimality testing procedure by applying it to the perturbed tentative solution. We address two additional difficulties due to the higher dimensionality of the RD surface in the scalable (N>1) case, namely, identifying the sufficient set of Lagrangian parameters to span the entire RD bound; and a method for navigation on the RD surface to compute a particular RD point. |
| Presentation | Iterative Computation of Scalable Rate Distortion Bounds |