Universal Lossy Coding for Individual Sequences Based on Complexity Functions

摘要

A theory of lossless compression of individual sequences has been formulated by Ziv and Lempel, and developed by their subsequent papers. While the framework of lossless coding problem of individual sequences can be extended to lossy coding problem, the lossy coding problem of individual sequences are not so well studied as the lossless coding problem. This paper considers four kinds of rate-distortion problems for individual sequences: the fix-rate coding under the maximum-distortion criterion (fm-coding) and the average-distortion criterion (fa-coding), the variable-rate coding under the maximum-distortion criterion (urn-coding) and the average-distortion criterion (m-coding). The converse coding theorems for each problem are established. Moreover, universal lossy coding schemes for individual sequences based on complexity functions are proposed, and the coding theorems for fm, fa and urn-coding problems are clarified.