I just finished reading *The Shadow Lines*, by Amitav Ghosh, and I loved it. Ghosh’s unnammed narrator, a doctoral student from Calcutta studying in London, tells the story of his own childhood and his present life in England. As a boy, he was fascinated with his cousin Tridib, who was doing postdoctoral studies in archaeology. Tridib ties together the characters in the book — his brother Robi, the narrator, Ila, and Tridib’s lover, May. Through their memories and reminiscences we get a snapshot of a time in the 1960s, when Bangladesh was East Pakistan and the wounds of Partition were still fresh. The narrator’s desire for Ila, his cousin, the border with Bangladesh, Tridib’s relationship with May, and Ila’s displacement in the UK are all shadowy boundaries in Ghosh’s world. It wasn’t the kind of novel I’d necessarily have picked up and read before, but it was deeply moving and I’m glad I bought it. I was a big fan of *In An Antique Land* as well, so now I’m tempted to gorge on Ghosh like I would ghosht…

# Monthly Archives: October 2007

# In Rainbows

My verdict : pretty good. A bit more lyrical, especially song like “Faust Arp.” That and “15 Step” are my favorites after the first listen through. It may verge on self-indulgent, but most pop music is that way.

In case you didn’t know, this is Radiohead’s new album, available as a download for pay-what-you-want (no, really).

# Mathematical methods in systems EE?

One thing that I have definitely benefited from in graduate school is my undergraduate background/degree in mathematics. It’s not that I *use* the contents of the math classes I have taken — Dynkin diagrams and cohomology don’t often appear in information theory or signal processing problems — but I am pretty comfortable with mathematical formalism. Grad students who didn’t do as much math usually get caught up on measure theory and so on by taking the graduate probability sequence or analysis sequence. What we don’t get is a survey of all the mathematical tools which we could use to attack different problems so that we know *what kind of tools* may relate to a given problem and *where* to look for it.

I think a first-year topics lecture series that introduces some new mathematical concepts to first-year graduate students could be great. Subjects like algebraic graph theory, auctions and mechanism design, random matrices, and so on may form a small unit in a regular class or may not be covered in classes at all. Not everyone wants to sit through a reading group on percolation theory, but they might want to get a basic idea of what percolation results are like and how they are useful (e.g. network connectivity).

On the other hand, maybe if such a lecture series were offered nobody would come and it would be useless. Any thoughts?

# LIDS blog

For some reason I never noticed that LIDS has a blog, with Kush Varshney doing the writing. It’s more interesting than mine, so go take a look.

# Allerton 2007 : Networks and Algorithms

**Constrained Consensus and Alternating Projection Methods**

*(Asu Ozdaglar)*

The problem here is somewthing like the minimization of the sum of local utility functions, but here the values for the optimization can be constrained. Asu proposed an alternating projection algorithm that minimizes the objective and then projects back onto the feasible set. In order to prove the covergence rates, she separates the linear update error (which can be analyzed using standard Markov chain techniques) from the projection error, which requires some technical conditions on the constraints. The key is that the latter error is the only one that incorporates the constraints. The bound is obtained by looking at a stopped process and letting the stopping time go to infinity.

**Network Coding Using Non-Commutative Algebras**

*(Shweta Agarwal and Sriram Vishwanath)*

For multiple unicast sessions, finite field operations and linear coding may not be sufficient to achieve capacity for network codes. The proposal in this paper was code using modules over a noncommutative ring, but still use Gaussian elimination for decoding. I had to duck out towards the end, so I wasn’t sure if there explicit code constructions provided.

**Rates of Convergence for Distributed Average Consensus with Probabilistic Quantization**

*(Tuncer Can Aysal, Mark Coates, and Michael Rabbat)*

Most gossip and consensus algorithms assume we can do computation over the reals, which is not really feasible. This work tries to tackle the effect of quantization on the convergence rate. The probabilistic quantization rule they use is this : if the true outcome is distance *d* away from an endpoint of a quantization bin of length *D*, quantize to that point with probability *d/D*. The resulting scheme can be analyzed and all nodes will converge to the same point (an absorbing state of a Markov chain). In expectation, this point will be the true average, although it will over or under-estimate the average in any realization. One tricky part of the analysis is a very long waiting time for the average to settle on one value after all nodes have converged to one of the quantization points neighboring the true mean.

**New Market Models and Algorithms**

*(Vijay Vazirani)*

This talk was on pricing algorithms for links in networks. He started out by talking about the Fisher market, which is a multicommodity market model where every user has a fixed budget, goods are divisible, and each user has a different utility for the different goods. There is an algorithm for doing the allocations efficiently in these markets. The Kelly approach to analyzing TCP uses pricing on edges and a combinatorial auction to generate efficient flows, and it formally similar to Fisher’s model in the linear case. Vazirani presented a ascending price auction for links where the sinks are buyers in a multicast scenario. The resulting allocations are fair and efficient. By showing a connection to the Eisenberg-Gale (1957) optimization problem, he proposed a new class of Eisenberg-Gale markets in which a strongly polynomial time algorithm will exist for cases where there is a max-min result to exploit (like multicast).

**Fast Gossip through Markov Chain Lifting**

*(Kyomin Jung, Devavrat Shah, and Jinwoo Shin)*

The standard analysis of gossip algorithms uses results on the mixing time of reversible Markov chains. However, results of Chen et al. and Diaconis et al. show that nonreversible chains may mix much more quickly. In particular, a “lifting” construction can be used to embed expander graphs in the original graph (I think?). The lifting construction itself is quite cool — I read the paper on it on the plane on the way back and may write more about it. The trick is really to get a better bound on the conductance of the chain, which then bounds the mixing times.

**Stochastic Approximation Analysis of Distributed Estimation Algorithms**

*(Ram Rajagopal and Martin Wainwright)*

This paper was on computing *nonlinear* functions of sensor observations. In particular, suppose sensors have access to iid samples of a random variable *X* with unknown distribution. They would like to estimate the *a*-quantile — that is, the *b* such that *P(X < b) = a*. The nodes can communicate with each other over noisy or rate-constrained links. The performance measure that Ram uses is ratio of the decentralized MSE to the centralized MSE. The algorithm works by local flooding and updates, and the estimator is strongly consistent, with asymptotically normal error. What is more interesting is that the error is a function of the Laplacian of the communication graph.

**Gossip Along the Way: Order-Optimal Consensus through Randomized Path Averaging**

*(Florence Bénézit, Alexandros Dimakis, Patrick Thiran, and Martin Vetterli)*

This algorithm is similar to the Geographic Gossip algorithm that Alex and I worked on. In that work a node would wake up, pick a target at random, and route a packet to the closest node to the target to perform one pairwise exchange in a standard gossip algorithm. The corresponding Markov chain went from having a mixing time of *O(n)* to *O(1)* at the expense of *O(\sqrt{n})* extra transmissions. In this work, they change the algorithm to aggregate and average all values along the routing path from the source to destination, so instead of averaging 2 nodes in each round, they average *O(\sqrt{n})* nodes in each round. This shaves off the extra *O(\sqrt{n})* from routing and so they get order-optimal performance (compared to the centralized algorithm, perhaps modulo all the log terms that I omitted in this brief description. The key to the analysis is to eschew computing the actual chain but instead look at “typical” paths and construct flows using the comparison method (original in Diaconis/Stroock, I think) to bound the mixing time.

# Allerton 2007 : Information Theory

Because Allerton proceedings don’t get handed out at the conference, my understanding of what I saw is upper bounded by the quality of my notes. If anyone has any clarifications or corrections, please let me know!

**A Rate-Distortion Approach to Anonymous Networking**

*(Parvathinathan Venkitasubramaniam and Lang Tong)*

This problem was looking at networks in which we want to keep eavesdropping nodes from doing traffic analysis. There is a technique called Chaum mixing that can be used by trusted routers to scramble traffic and increase anonymity. The measure of anonymity they use is an equivocation at the eavesdropper normalized by the entropy of the sessions. The problem then becomes a rate-distortion problem for scheduling sessions in the network. They use two classes of nodes, covert relays and normal relays, and try to find tradeoffs between the density of covert relays and the anonymity.

**Wireless Network Information Flow**

*(Salman Avestimehr, Suhas Diggavi, and David Tse)*

Suhas presented this paper, which was on the deterministic model that David presented at ITW. Since we have broadcast and multiple access in wireless networks, the signal interactions become quite complex. The deterministic model reduces these networks to deterministic finite-field networks, which have a simple cut-set upper bound in terms of the rank of associated matrices. This outer bound is achievable as well, so the capacity of this simplified model can be calculated and looks a bit like the Ford-Fulkerson theorem in a more general sense.

**Source Coding with Mismatched Distortion Measures**

*(Urs Niesen, Devavrat Shah, and Gregory Wornell)*

If the distortion measure that we are to use is not known at the time of encoding, what should we do? To be more concrete, suppose we have *f* and *g* as distortion measures. Given a rate *R* and distortion *D* for the source under distortion *f*, what is the smallest distortion *E*we can achieve under the same code with measure *g*? It can be arbitrarily bad! But we can also write the performance using a single-letter characterization. There was a second problem Urs discussed, bitu I didn’t quite catch it — I think it was fixing *D* under *f* and asking what *E* we can get under *g*, regardless of the rate.

**A Deterministic Approach to Wireless Relay Networks**

*(Salman Avestimehr, Suhas Diggavi, and David Tse)*

This was a continuation of the work in the earlier talk, providing the details of the proof. The first part shows that if all paths from source to sink in the network are of equal length, then the capacity is the cut-set bound. In order to deal with unequal length paths, they use a time expansion argument (which looked a bit like a trellis, actually) with scheduling to avoid different flows mixing. It’s a bit tricky to show that you get back to the cut set bound with this, but I assume the details are in the paper. The other part was to show that this model can be used to construct a scheme for the original Gaussian channel that is “close” to optimal, and that the maximum gap (one bit in many cases) occurs in a very small regime of parameters.

**The Approximate Capacity of an One-Sided Gaussian Interference Channel**

*(Guy Bresler, Abhay Parekh, and David Tse)*

This was yet another paper using the deterministic model, this time for the many-to-one (and by a clever duality argument on the interference pattern, the one-to-many) interference channel, in which one transmit-receive pair experiences (inflicts) interference from (on) everyone else. The central idea here is interference alignment — if one signal level experiences interference from a transmitter, it can experience interference from other transmitters with no problem (or so I understood it). Guy showed that the Han-Kobayashi scheme is not optimal because the interference pattern is “too crowded,” and gave a lattice-based scheme that emulates the deterministic model.