Adversarial Coding and Compressing Active Sources
Harikrishna R Palaiyanur, Cheng Chang and Anant Sahai
National Science Foundation Graduate Research Fellowship
In many real-world systems, sensors have a choice in what to observe. In the "active vision" paradigm we are reminded that "people do not merely see, they also look." How are we to model the data streams that result from such sensors?
To answer this, we consider the problem of finding the rate-distortion function of an arbitrarily varying source (AVS) with a finite number of sources with known distributions. Berger's paper "The Source Coding Game," IEEE Trans. Inform. Theory, 1971, considers this problem under the condition that the adversary is allowed only causal access to the source realizations. We consider the case when the adversary has access to the source realizations non-causally. Using the type-covering lemma, this new rate distortion function can be determined to be the maximum of the IID rate distortion function over a set of source distributions attainable by the adversary. We find a bound on the number of distributions that need to be sampled to determine the rate distortion function of an AVS to within a certain accuracy. This bound is developed through an explicit bound on the continuity of the IID rate-distortion function.
We plan to investigate the usefulness of this bound in the problem of estimating the rate-distortion function for an unknown source, especially those that might have memory.
- H. Palaiyanur, C. Chang, and A. Sahai, "The Source Coding Game with a Cheating Switcher," Proc. International Symposium on Information Theory, Nice, France, June 2007.