2022/12/23 by Merhav, Neri
#FOS: Computer and information sciences #Information Theory (cs.IT)
paper · doi:10.48550/arxiv.2212.12208
We propose a universal ensemble for random selection of rate-distortion codes, which is asymptotically optimal in a sample-wise sense. According to this ensemble, each reproduction vector, \hbx, is selected independently at random under the probability distribution that is proportional to 2-LZ(\hbx), where LZ(\hbx) is the code-length of \hbx pertaining to the 1978 version of the Lempel-Ziv (LZ) algorithm. We show that, with high probability, the resulting codebook gives rise to an asymptotically optimal variable-rate lossy compression scheme under an arbitrary distortion measure, in the sense that a matching converse theorem also holds. According to the converse theorem, even if the decoder knew ℓ-th order type of source vector in advance (ℓ being a large but fixed positive integer), the performance of the above-mentioned code could not have been improved essentially, for the vast majority of codewords that represent all source vectors in the same type. Finally, we provide a discussion of our results, which includes, among other things, a comparison to a coding scheme that selects the reproduction vector with the shortest LZ code length among all vectors that are within the allowed distortion from the source vector.