Fixed-Slope Universal Lossy Coding for Individual Sequences

In a theory of lossy coding of individual sequences, two kinds of coding schemes, the fixed-rate coding and the fixed-distortion coding, have been studied. This paper investigates another kind of lossy coding scheme of individual sequences, which is called fixed-slope lossy coding. We show that the optimal cost attainable by the blockwise fixed-slope lossy encoder is equal to the optimal average cost with respect to the overlapping empirical distribution of the given sequence. Moreover, we clarify that the fixed-slope universal lossy block encoder based on the complexity function achieves the optimal cost. As an application of the result, we show that for any ergodic source the sample average of the cost achieved by the lossy block encoder based on the complexity function is asymptotically equal to the optimal cost with probability one