D-Semifaithful Codes That are Universal Over Both Memoryless Sources and Distortion Measures

We prove the existence of codebooks for d-semifaithful lossy compression that are simultaneously universal with respect to both the class of finite-alphabet memoryless sources and the class of all bounded additive rational distortion measures. By applying independent random selection of the codewords according to a mixture of all memoryless sources, we achieve redundancy rates that are within O(log n/n) close to the empirical rate-distortion function of every given source vector with respect to every bounded, rational distortion measure.

Automated summary

We prove the existence of codebooks that can be universally applied to both finite-alphabet memoryless sources and bounded additive rational distortion measures for d-semifaithful lossy compression. By utilizing independent random selection of codewords based on a mixture of all memoryless sources, we achieve redundancy rates that are within O(log n/n) close to the empirical rate-distortion function for every given source vector and bounded rational distortion measure.