Infinite-message Distributed Source Coding for Two-terminal Interactive Computing

Details Infinite-message Distributed Source Coding for Two-terminal Interactive Computing Infinite-message Distributed Source Coding for Two-terminal Interactive Computing

2009-08-25

arxiv.org/abs/0908.3512v2

Computer Science

Information Theory

21 pages, 5 figures. A shorter version (version 1) was published in Allerton Conference 2009. The second version contains exte

Scientific paper

A two-terminal interactive function computation problem with alternating messages is studied within the framework of distributed block source coding theory. For any arbitrary fixed number of messages, a single-letter characterization of the sum-rate-distortion function was provided in previous work using traditional information-theoretic techniques. This, however, does not directly lead to a satisfactory characterization of the infinite-message limit, which is a new, unexplored dimension for asymptotic-analysis in distributed block source coding involving potentially infinitesimal-rate messages. This paper introduces a new convex-geometric approach to provide a blocklength-free single-letter characterization of the infinite-message sum-rate-distortion function as a functional of the joint source pmf and distortion levels. This characterization is not obtained by taking a limit as the number of messages goes to infinity. Instead, it is in terms of the least element of a family of partially-ordered marginal-perturbations-concave functionals defined by the coupled per-sample distortion criteria. For computing the Boolean AND function of two independent Bernoulli sources at one and both terminals, with zero Hamming distortion, the respective infinite-message minimum sum-rates are characterized in closed analytic form. These sum-rates are achievable using infinitely many infinitesimal-rate messages. The convex-geometric functional viewpoint also suggests an iterative algorithm for evaluating any sum-rate-distortion function, including, as a special case, the Wyner-Ziv rate-distortion function.

Affiliated with

Also associated with

No associations

Rating

Infinite-message Distributed Source Coding for Two-terminal Interactive Computing 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 Infinite-message Distributed Source Coding for Two-terminal Interactive Computing, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Infinite-message Distributed Source Coding for Two-terminal Interactive Computing will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-232650