Lossy Compression with Universal Distortion

A novel variant of lossy coding is considered in which the distortion measure is revealed only to the encoder and only at run-time. Two forms of rate redundancy are used to analyze the performance, and achievability results of both a pointwise and minimax nature are demonstrated. One proof uses appropriate quantization of the space of distortion measures while another uses ideas from VC dimension and growth functions. Future research directions pertaining to Rissanen's redundancy result are discussed.