# The source coding game with a cheating switcher

### Harikrishna R Palaiyanur, Cheng Chang and Anant Sahai

###
EECS Department

University of California, Berkeley

Technical Report No. UCB/EECS-2007-155

December 17, 2007

### http://www.eecs.berkeley.edu/Pubs/TechRpts/2007/EECS-2007-155.pdf

Motivated by the lossy compression of an active-vision video stream, we consider the problem of finding the rate-distortion function of an arbitrarily varying source (AVS) composed of a finite number of subsources with known distributions. Berger's paper `The Source Coding Game', \emph{IEEE Trans. Inform. Theory}, 1971, solves this problem under the condition that the adversary is allowed only strictly causal access to the subsource realizations. We consider the case when the adversary has access to the subsource realizations non-causally. Using the type-covering lemma, this new rate-distortion function is determined to be the maximum of the IID rate-distortion function over a set of source distributions attainable by the adversary. We then extend the results to allow for partial or noisy observations of subsource realizations. We further explore the model by attempting to find the rate-distortion function when the adversary is actually helpful.

Finally, a bound is developed on the uniform continuity of the IID rate-distortion function for finite-alphabet sources. The bound is used to give a sufficient number of distributions that need to be sampled to compute the rate-distortion function of an AVS to within a certain accuracy. The bound is also used to give a rate of convergence for the estimate of the rate-distortion function for an unknown IID finite-alphabet source .

BibTeX citation:

@techreport{Palaiyanur:EECS-2007-155, Author = {Palaiyanur, Harikrishna R and Chang, Cheng and Sahai, Anant}, Title = {The source coding game with a cheating switcher}, Institution = {EECS Department, University of California, Berkeley}, Year = {2007}, Month = {Dec}, URL = {http://www.eecs.berkeley.edu/Pubs/TechRpts/2007/EECS-2007-155.html}, Number = {UCB/EECS-2007-155}, Abstract = { Motivated by the lossy compression of an active-vision video stream, we consider the problem of finding the rate-distortion function of an arbitrarily varying source (AVS) composed of a finite number of subsources with known distributions. Berger's paper `The Source Coding Game', \emph{IEEE Trans. Inform. Theory}, 1971, solves this problem under the condition that the adversary is allowed only strictly causal access to the subsource realizations. We consider the case when the adversary has access to the subsource realizations non-causally. Using the type-covering lemma, this new rate-distortion function is determined to be the maximum of the IID rate-distortion function over a set of source distributions attainable by the adversary. We then extend the results to allow for partial or noisy observations of subsource realizations. We further explore the model by attempting to find the rate-distortion function when the adversary is actually helpful. Finally, a bound is developed on the uniform continuity of the IID rate-distortion function for finite-alphabet sources. The bound is used to give a sufficient number of distributions that need to be sampled to compute the rate-distortion function of an AVS to within a certain accuracy. The bound is also used to give a rate of convergence for the estimate of the rate-distortion function for an unknown IID finite-alphabet source .} }

EndNote citation:

%0 Report %A Palaiyanur, Harikrishna R %A Chang, Cheng %A Sahai, Anant %T The source coding game with a cheating switcher %I EECS Department, University of California, Berkeley %D 2007 %8 December 17 %@ UCB/EECS-2007-155 %U http://www.eecs.berkeley.edu/Pubs/TechRpts/2007/EECS-2007-155.html %F Palaiyanur:EECS-2007-155