An Implementable Scheme for Universal Lossy Compression of Discrete Markov Sources
| dc.creator | Jalali, Shirin | |
| dc.creator | Montanari, Andrea | |
| dc.creator | Weissman, Tsachy | |
| dc.date | 2009-01-15 | |
| dc.date | 2009-01-18 | |
| dc.date.accessioned | 2026-07-07T12:30:57Z | |
| dc.date.available | 2026-07-07T12:30:57Z | |
| dc.description | We present a new lossy compressor for discrete sources. For coding a source sequence $x^n$, the encoder starts by assigning a certain cost to each reconstruction sequence. It then finds the reconstruction that minimizes this cost and describes it losslessly to the decoder via a universal lossless compressor. The cost of a sequence is given by 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)$. | |
| dc.description | 10 pages, 2 figures, Data Compression Conference (DCC) 2009 | |
| dc.identifier | https://arxiv.org/abs/0901.2367 | |
| dc.identifier | http://arxiv.org/abs/0901.2367 | |
| dc.identifier.uri | http://salesiana.dossiersoluciones.com/handle/123456789/216295 | |
| dc.subject | Information Theory | |
| dc.title | An Implementable Scheme for Universal Lossy Compression of Discrete Markov Sources | |
| dc.type | text |