This paper investigates the fixed-slope lossy coding of individual sequences and nonstationary sources. We clarify that, for a given individual sequence, the optimal cost attainable by the blockwise lossy encoders is equal to the optimal average cost with respect to the empirical distribution of the given sequence. Moreover, we show that, for a given nonstationary source, the optimal cost attainable by the blockwise encoders is equal to the supremum of the optimal average cost over all the stationary sources in the stationary hull of the given source. In addition, we show that the universal lossy coding algorithm based on Lempel-Ziv 78 code attains the optimal cost for any individual sequence and any nonstationary source.

This paper investigates the fixed-rate and fixed-distortion lossy coding problems of individual sequences subject to the subadditive distortion measure. The fixed-rate and fixed-distortion universal lossy coding schemes based on the complexity of the sequence are proposed. The obtained coding theorems reveal that the optimal distortion (resp. rate) attainable by the fixed-rate (resp. fixed-distortion) lossy coding is equal to the optimal average distortion (resp. rate) with respect to the overlapping empirical distribution of the given sequence. Some connections with the lossy coding problem of ergodic sources are also investigated.