Playa Norte on Isla Mujeres
I was lucky enough to get invited to present at the Communications Theory Workshop (CTW) in Cancun last month. Since the conference started on a Monday I took the weekend before to do a little sightseeing, hang out on the beach (see above), and visit Chichen Itza, which was pretty amazing. CTW is a small conference — single track, 2.5 days, and plenty of time for panels, discussions, etc. I had a great time there, and it was really nice to meet new people who were working on interesting problems that I hadn’t even heard about.
The first day was focused on wireless data services, the explosion thereof, and the lack of capacity to support it all. Add more relays, femtocells, interference management and alignment, putting more antennas for MIMO gains. Reinaldo Valenzuela was pretty pessimistic — according to him we are pretty much at the point where service providers are losing money by providing data over wireless. He seemed to think the only way out now is to change pricing models or really try to exploit network MIMO.
The second day was on cognitive radio, where the picture also seemed a bit pessimistic. Michael Marcus kind of laid into academics for not participating in the FCC comment process. The criticism is valid — if we care about cognitive radio and its potentials and so on, we should try to persuade the regulators to do smart things and not piecemeal things. As things stand now, it’s unclear how much additional capacity is available in the TV bands, given the current requirements for operating there. The sensing requirements nigh unreasonable, and if you do detect a primary you have to stay silent for 30 minutes. That makes it kind of hard to run a commercial service.
Another thing I learned during that day was that wireless microphones in the US operate in the TV bands, and are grandfathered in to the existing rules for cognitive radio. This means you have to detect if you will interfere with a wireless mic, which seems quite tough. Steve Shellhammer talked about a contest Qualcomm ran to build a detector for this problem. In addition, a large fraction of wireless microphone users are not licensed and hence their use is illegal, but nobody’s enforcing that.
The second half of the day was on emerging topics, followed by a panel called “Is Communication Theory Dead?” I think the pessimism and despair of the first two days needed to be let out a little, and there was a pretty spirited discussion of whether communication theorists were answering the right questions or not. It was like group therapy or something. Luckily there was the banquet after the panel so people could forget their woes…
The last day of the workshop was the session I spoke in, which were 5 talks on wireless networks, but from vastly different perspectives. Tara Javidi talked about routing, Daniela Tuninetti about information theory and cognitive interference channels, Elza Erkip about game theory models for the interference channel, and Anna Scaglione about cooperative information flooding. For my part, I talked about (very) recent work I have done with Tara on distributed consensus with quantized messages. We have some nice first-order results but I’m still hammering away at better bounds on the convergence rate.
An Ergodic Walk 
Dear Anand,
Thanks for posting a link to the workshop; I clicked on your slides, and I have a quick question for you about them. What is \hat{x}_i? I didn’t see it defined anywhere. Is it x_i rounded to the nearest multiple or 1/2^R?
Best,
alex
Yes, it’s the rounded version of x_i. We’re still working with the scalar data case (as opposed to your more directly discrete histogram approach).
Thanks. I meant to say “of 1/2^R,” not “or 1/2^R,” but I’m sure you figured out that was a typo.
Hi, Anand
I might be misunderstanding your result, because the following seems to me to be a counterexample.
Suppose R=2, so that \hat{x}_i have to lie in the set {0,1/4, 1/2, 3/4, 1}. Suppose R_0=3, so that entries of W are multiples of 1/2^3 = 1/8, and initial values are multiples of 1/2^(2+3)=1/32.
Suppose we just have two agents. Agent 1 begins with x_1(0)=9/32, agent 2 begins with x_2(0)=23/32. These are not in the same quantization bucket: the first is between 1/4 and 1/2 and the second is between 1/2 and 3/4. Their rounded values are \hat{x}_1(0)=1/4, \hat{x}_2(0)=3/4.
Now suppose W_{12}=W_{21}=7/8, and correspondingly W_{11}=W_{22}=1/8.
Then
x_1(1) = x_1(0) + W_{12} (\hat{x}_2(0) – \hat{x}_1(0))
= 9/32 + (7/8)(3/4-1/4)
= 23/32
and similarly x_2(1)=9/32. The agents have switched values.
So the values of x_1,x_2 cycle forever and never end up in the same bucket.
What am I missing?
Well, you’re not misunderstanding it because the result as described in the slides in not quite correct.
The short answer is that oscillation is a problem, so that having W_{ii} > 0 is not enough for the thing to converge. I am still working on the finding the simplest condition on the W matrix.
Sorry to be so unclear — I’m sure you have more insights on this than I do since you’ve been thinking about issues with discretization for longer than I have.
Thanks for your response!
Actually, I have not thought about this particular model( unquantized state and quantized transmissions) at all, so I really do not have any insights đŸ™‚ I agree its an interesting question though.
By the way, you probably know that this exact update scheme was studied earlier by Frasca, Carli, Fagnani, and Zampieri:
Click to access frascaquantized.pdf
(see Eq. 5 in above paper) who proved conclusions which are considerably weaker than convergence to the same bin.
Yes, in fact I am using their scheme and trying to do a different analysis — the motivation is different for me I guess. They (here and other works) are looking at getting asymptotically close to the true average by adapting the quantization scheme. I am asking for considerably less — just to get “close enough” without having to do any adaptation.
I think in various places they also look at getting close enough without doing adaptation.
Anyway, I was thinking of reading through the various papers on this model at some time in the future, so it would be great if you could send me a draft of your paper once you are finished.