Finite-state rate-distortion for individual sequences

Abstract

We introduce a class of lossy finite-state machines for lossy compression of an individual sequence drawn from a finite alphabet at a fixed distortion, and define a fundamental quantity finite-state rate-distortion that is an asymptotically attainable lower bound on the compression rate of any lossy finite-state machine. For Hamming distortion, we obtain a universal lower bound on the finite-state rate-distortion of any individual sequence.