An iterative scheme for near optimal and universal lossy compression

We present a new lossy compression algorithm for discrete sources. The encoder assigns a certain cost to each reconstruction sequence, finds the sequence that minimizes the cost, and describes it losslessly to the decoder via a universal lossless compressor. The cost of a sequence is defined as a linear combination of its empirical probabilities of some order k + 1 and its distortion relative to the source sequence. The linear structure of the cost in the empirical count matrix allows the encoder to employ a Viterbi-like algorithm for obtaining the minimizing reconstruction sequence simply. We identify a choice of coefficients for the linear combination in the cost function which ensures that the algorithm universally achieves the optimum rate-distortion performance of any Markov source in the limit of large n, provided k is increased as o(log n). Finding the optimal coefficients is complex and requires solving a non-convex optimization problem. As a detour, we propose a simple heuristic iterative procedure, and demonstrate its efficiency through our experimental results.