Lossy Compression of Discrete Sources via the Viterbi Algorithm
Shirin Jalali, Andrea Montanari, Tsachy Weissman · IEEE Transactions on Information Theory · 2011
We present a new lossy compressor for finite-alphabet sources. For coding a sequence xn, the encoder starts by assigning a certain cost to each possible reconstruction sequence. It then finds the one that minimizes this cost and describes it losslessly to the decoder via a universal lossless compressor. The cost of each sequence is a linear combination of its distance from the sequence xnand a linear function of its kthorder empirical distribution. The structure of the cost function allows the encoder to employ the Viterbi algorithm to find the sequence with minimum cost. We identify a choice of the coefficients used in the cost function which ensures that the algorithm universally achieves the optimum rate-distortion performance for any stationary ergodic source, in the limit of large , provided that increases as o(log n). Iterative techniques for approximating the coefficients, which alleviate the computational burden of finding the optimal coefficients, are proposed and studied.