These were a few more “traditional information theory” talks that I had reasonable notes on. The remainder of my ITA posts will be on topics further afield.

Distributed functional scalar quantization with limited encoder interaction
Vinith Misra, Stanford, Vivek K Goyal, MIT, and Lav R. Varshney, MIT

I had looked at an earlier results on this problem and now I think I get it a little better. The regime they look at is high-rate quantization, in which the quantization points are represented by a normalized point density and the distortion is calculated with respect to that. They want to compute some function g(X_1^n) of n different source variables encoded separately. So we can choose a point density function \lambda_i for each of the variables, write the MSE of estimating g in terms of those and then optimize. It turns out that a key parameter is the “functional sensitivity” of g(X_1^n) at each coordinate, which is given by the expectation of the i-th derivative conditioned on the value of X_i. This decouples the design of the quantizers and leads to a performance improvement. As an extension they look at cases where the encoders can “chat” in the sense that they can somehow choose the function g to be computed… and that part I didn’t understand so well.

Bounds for interactive computation in collocated networks
Nan Ma, Boston University, Prakash Ishwar, Boston University, and Piyush Gupta, Bell Labs

The model here is that every sensor observes one component of a joint source \{\mathbf{S}(t) : t = 1, 2, \ldots\}. The decoder wants to estimate \{ f(\mathbf{S}(t)) : t = 1, 2, \ldots\}, and the sensors can broadcast messages to all other sensors. They get a rate region related to iterated conditioning on all past messages and then make a connection to communication complexity and monochromatic rectangles (c.f. the book by Kushilevitz and Nisan). As an example, they show that to compute the parity function of binary sources, the destination basically has to recover all the sources.

Erasure descriptions
Ebad Ahmed and Aaron B. Wagner, Cornell University

This talk discussed a multiple descriptions problem with a binary source and the erasure distortion measure (erasures cost 1, errors cost infinity). The encoder provides n rate R descriptions, any k of which should allow recovery of the whole source. Furthermore, there should be no excess rate, meaning the R = 1/k since the decoder with k descriptions needs at most total rate 1 to recover the source. The question is what happens to the distortion for decoders who get fewer descriptions. They have some hand-tweaked code constructions for certain cases but not a general construction (yet). Furthermore, via random coding arguments they can make some Pareto optimality claims.

Variable-rate channel capacity
Sergio Verdu, Princeton University, and Shlomo Shamai, Technion

For source coding we have {variable,fixed}-to-{variable,fixed} coding schemes, which gives 4 alternatives to look at, but in channel coding, what do we have? This talk looked at some formulations for problems and how one might define capacity. In variable-to-fixed, we can think of the encoder having an infinite reservoir of bits which has to get mapped to a codeword in \mathcal{X}^n. We count the number L_n of consecutively recovered bits and define the rate as \lim \inf_{n \to \infty}\mathbb{E}[L_n]/n. We can think of fixed-to-variable codes as rateless codes, where we try to send k bits over a variable blocklength N_k and define the rate as \lim \inf_{n \to \infty} \mathbb{E}[k/N_k]. Some results were shown on the relationship of these capacities to each other. When the channel has a strong converse then they are all equal and equal to the Shannon capacity. Some relationship to broadcast channels was discussed.