Lossy Compression of Discrete Sources via the Viterbi Algorithm

DOI10.1109/TIT.2011.2178059MaRDI QIDQ5272027zbMATH OpenOpenAlexFDO

Authors Shirin Jalali, Tsachy Weissman, Andrea Montanari

Publication date 12 July 2017

Published in IEEE Transactions on Information Theory (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1011.3761

Mathematics Subject Classification ID

Source coding (94A29)

Abstract: We present a new lossy compressor for discrete-valued sources. For coding a sequence $x^n$, 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 $x^n$ and a linear function of its $k^{mth}$ order empirical distribution. The structure of the cost function allows the encoder to employ the Viterbi algorithm to recover the minimizer of the cost. We identify a choice of the coefficients comprising the linear function of the empirical distribution used in the cost function which ensures that the algorithm universally achieves the optimum rate-distortion performance of any stationary ergodic source in the limit of large $n$, provided that $k$ diverges as $o(logn)$. Iterative techniques for approximating the coefficients, which alleviate the computational burden of finding the optimal coefficients, are proposed and studied.

Cited in

(2)

• Achievable complexity-performance tradeoffs in lossy compression
• From compression to compressed sensing

This page was built for publication: Lossy Compression of Discrete Sources via the Viterbi Algorithm

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5272027)