Computer Science – Information Theory
Scientific paper
2009-01-15
Computer Science
Information Theory
10 pages, 2 figures, Data Compression Conference (DCC) 2009
Scientific paper
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)$.
Jalali Shirin
Montanari Andrea
Weissman Tsachy
No associations
LandOfFree
An Implementable Scheme for Universal Lossy Compression of Discrete Markov Sources does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with An Implementable Scheme for Universal Lossy Compression of Discrete Markov Sources, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and An Implementable Scheme for Universal Lossy Compression of Discrete Markov Sources will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-126827