2009 Poster Sessions : An implementable scheme for universal lossy compression of discrete Markov sources

Student Name : Shirin Jalali
Advisor : Tsachy Weissman
Research Areas: Information Systems
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)$.

Shirin Jalali is a Ph.D candidate in Electrical Engineering at Stanford University. Her research interests are information theory and statistical signal processing. During her Ph.D, with her advisor, professor Tsachy Weissman, she has worked on several problems on centralized and distributed universal source coding. She received her B.S. and M.S. degrees both in Electrical Engineering from Sharif University of Technology, Tehran, Iran, in 2002 and 2004 respectively.