Two new papers on molecular communication

I just got back from lovely Cambridge, Mass., where I managed to sneak in a day to see some of the interesting talks at Bionetics before storming back to Toronto to cover my teaching schedule.  December in Boston, what more could you ask for?

I'm a coauthor on a couple of new molecular communication papers that just came out, one at Bionetics, and the other on arXiv:

• For Bionetics, my Ph.D. student, Nariman Farsad, and our collaborators, Satoshi Hiyama and Yuki Moritani of NTT DOCOMO, continued some of our earlier work on microchannels.  This was a short "work-in-progress" paper, where we considered the performance of active transport systems in a more realistic simulation environment.  Surprisingly, Brownian motion with drift usually does better than molecular motors -- probably because every molecule can start propagating right away, rather than waiting to be picked up by a motor. [N. Farsad, A. W. Eckford, S. Hiyama, and Y. Moritani, "Information rates of active propagation in microchannel molecular communication,” in Proc. 5th International Conference on Bio-Inspired Models of Network, Information, and Computing Systems, Boston, MA, USA, 2010. (pdf)]

• On arXiv (and also submitted to Trans. Info. Theory), K. V. Srinivas, Ravi Adve, and I extended Sachin's earlier work on Brownian motion with drift.  We're looking at molecular timing channels, where information is encoded in the transmission time x. The receiver sees the reception time y, where y = x + n, and where n is the first arrival time of a Brownian motion; thus, these are additive noise channels. It turns out that the first arrival time distribution of a Brownian motion with positive drift is given by the inverse Gaussian distribution (kind of an odd name at first glance, since it's not the reciprocal of a Gaussian PDF).  So a molecular timing channel in the presence of positive drift is an additive inverse Gaussian noise channel. There is a rich literature on the inverse Gaussian, which lets us get closed-form solutions and bounds for a number of important quantities, like ML detectors, probabilities of error, and capacities -- sadly, not as clean and nice as the solutions for the AWGN, but we do what we can. [K. V. Srinivas, R. S. Adve, and A. W. Eckford, "Molecular communication in fluid media: The additive inverse Gaussian noise channel," arXiv:1012.0081 (submitted to IEEE Transactions on Information Theory).]

You can also check out more of my molecular communication work here.

Sixty years of Hamming codes

Via Slashdot, this year marks the 60th anniversary of the venerable Hamming code.  Arriving just two years after Shannon's seminal paper, the Hamming codes were the first nontrivial error-correcting code, and Hamming's contribution to the theory of error correcting codes (using metrics which are now known as Hamming distance and Hamming weight) are still taught today.

Here (pdf) is Hamming's original paper (from BSTJ), and here is my Hamming code lecture from last spring's information theory course:

Ph.D. position available (Update: No longer available)

Update August 16, 2011: This particular position is no longer available.

Capacity in the presence of intractability

Shannon's channel capacity, C = max_p(x) I(X;Y), gives the highest rate at which information can be reliably transmitted over a noisy channel.  But the simplicity of the equation is deceptive: there are very few channels for which capacity is known.  Normally, the difficulty is in optimizing over all input distributions p(x), but what if I(X;Y) is itself intractable?

I(X;Y) can be hard to calculate if f(y) or f(y|x) are hard.  The former can happen in intersymbol interference channels with long memories, especially under a binary (or discrete) input constraint.  The latter can happen in timing channels, when x is a vector of inputs, and the output is of the form y = sort(x+n), where n is the vector of timing noise. In this case, calculating f(y|x) requires the calculation of a matrix permanent, a classic intractable problem for vectors of practical length. (See also: the Bapat-Beg theorem.)

However, there is an elegant trick you can use to find a lower bound on I(X;Y), as long as you can (tractably) generate random variables x and y according to their true distributions f(x) and f(y|x).  Let g(y|x) be any valid conditional distribution of y given x.  Further, let

Then

where expectation is always taken with respect to the true distribution.  That is, if you can pick a tractable approximate distribution g(y|x), and you can simulate both x and y, then you can perform a Monte Carlo expectation on log g(y|x)/g(y), and get a lower bound on I(X;Y).  You can then optimize with respect to the bound to find a lower bound on capacity.

The proof is straightforward.  First let g(x|y) = g(y|x)f(x)/g(y). Then:

So the accuracy of the bound is equal to the relative entropy between the true f(x|y) and the approximate g(x|y).

This result has been around for a while, but a nice recent application is here:

D. M. Arnold, H.-A. Loeliger, P. O. Vontobel, A. Kavcic, and W. Zeng, “Simulation-based computation of information rates for channels with memory,” IEEE Trans. Inform. Theory, vol. 52, pp. 3498–3508, Aug. 2006.

List of blogs in machine learning

Here is a thread with a huge list of good machine learning blogs.

The most interesting discovery from the list: Radford Neal, the co-re-discoverer of LDPC codes, has a blog. I took his graphical inference course when I was a Ph.D. student at U of T.

Announcing the Nano Networks blog

As one of my volunteer service positions, I am chair of the IEEE ComSoc Emerging Technologies Subcommittee on Nanoscale, Molecular, and Quantum Networking.  I've decided to transform our committee's home page into a blog, to share research news and other details about this field.

You can read the blog at http://nano-networks.blogspot.com/.  You can also subscribe to our Twitter feed: @NanoNetworks.

The blog will be newsletter-style; if you have anything interesting to post (new paper, profile of yourself or your lab, upcoming conference, or anything else), please send me a short blurb, preferably something ready to post.  I will try to make use of anything sent to me.

Entropy fact of the day

It's well known that certain distributions have maximum entropy under moment constraints. For instance, maximum entropy H(X) under a variance constraint is given by the Gaussian distribution. Generally, for any positive integer k and for given constant c, there exist algorithms to find the distribution maximizing H(X) subject to E[X^k] = c.

However, here's what I learned yesterday: if we change the constraint to E[X^-k] = c, there exists no such maximum entropy distribution -- because you can always achieve unbounded entropy subject to the constraint.

At first I thought this was surprising, but then I realized it's not too hard to think of an example that shows why it's true. Think about it for a few minutes -- I'll post a hint in the comments.