Linkage

Troubles in how science is marketed to girls.

Human remains at Richard III’s grave! (That sounds like a cryptic clue but it isn’t).

An interesting take on Karachi, but I’d want a local’s opinion of it…

The case of Aseem Trivedi is a real travesty.

Bad Lip Reading does a number on Mitt Romney. They’ve also done Obama.

Irving S. Reed

USC announced today: “Professor Irving S. Reed passed away this morning, September 11, 2012, at the age of 88.  Professor Reed was a member of the Ming Hsieh Department of Electrical Engineering faculty from 1963 until his retirement in 1993 as Powell Chair of Engineering Emeritus.”

Prof. Reed had made significant contributions in radar design theory, programming languages and, of course, coding theory.  Reed-Muller and Reed-Solomon codes have been incredibly influential in electrical engineering, theoretical computer science and mathematics.

Reed-Solomon codes are used to protect data in countless applications including CDs, DVDs, DSL and RAID. They were also used to encode the digital images sent back by space probes like the Voyager. RS codes are my favorite example of something practically useful and at the same time theoretically deep.

The announcement mentions: “Millions of people today enjoy the benefits of Reed’s many inventions and contributions of technology, without being aware of their remarkable benefactor.”

What we want are young fresh faces

Via SEK I read about a job ad at Colorado State which specifies that applicants should have received their PhD from 2010 onwards. Sorry 2009-ers, you’re not eligible.

According to the Colorado State jobs site:

Colorado State University does not discriminate on the basis of race, age, color, religion, national origin or ancestry, sex, gender, disability, veteran status, genetic information, sexual orientation, or gender identity or expression. Colorado State University is an equal opportunity/equal access/affirmative action employer fully committed to achieving a diverse workforce and complies with all Federal and Colorado State laws, regulations, and executive orders regarding non-discrimination and affirmative action. The Office of Equal Opportunity is located in 101 Student Services.

Because I was interested, I called the Office of Equal Opportunity at (970) 491-5836 to see if their office had vetted the ad and whether or not requiring a post-2010 PhD constituted age discrimination. This is what they told me, not specifically about this position, but in general about ads of this type:

  • Fort Collins is a nice place to live and they get lots of people who apply to jobs who have more experience (even at the associate level, so they claim). They want to make it very clear that those people are not welcome to apply.
  • It’s a salary thing where they don’t want to pay for the experience of someone with a PhD pre-2010.
  • They want to be “very clear about what they are looking for” (sounds ominous!)
  • This is a way of cutting down on the number of applications they have to read. Sure they may lose out on some qualified candidates. Implicit in this is that it’s an employer’s market out there.

All in all, this is not a sanguine situation for job applicants. I bet it would be nice if Michael Bérubé could weigh in on this in his capacity as MLA President.

Linkage

I’m a big fan of 99% Invisible, a podcast about design and architecture and… stuff. They rebroadcast a longer piece about U.N. Plaza in San Francisco, and it’s fascinating. I was living in Berkeley at the time much of this went down, and I was semi-unaware of it.

A post from the new desi blog, Brown Town, about Freddie Mercury.

My cousin Supriya has e-books in Hindi, Marathi, and Gujarati available. You know, for kids!

My very dear (but not so near) friend Charlotte has a new blog : Mary Magdalene Girl in which she will discuss gender and her un-diasporaing (not a word) by moving to Ireland.

Photos of yakuza. Unrelatedly, construction worker fashion in Japan.

Approaches to the research statement

It’s job season again and I am revising my research statement. I was pretty happy with the last iteration of it, but as things change I might need to find a new story for my life. As I get farther along, it has become a bit harder to cram all of the things I’ve worked on into a single consistent story. There are even some grad students I know who have worked on several distinct things and they probably have the same problem. There’s a tension in the research statement between coming up with a coherent story and accurately representing your work. There are a few generic ways of handling this, it seems.

The omnibus. You can write many mini-stories, one about each of the major projects, and then have a section for “miscellaneous other papers.” This approach eschews the overarching framework idea and instead just goes for local internal consistency.

The proposal. Instead of talking about all of your work (or mentioning it), you propose one research direction and give short shrift to the rest. This has the advantage of letting you write more fully about one topic and provide sufficient context and exciting new research directions, but then again you’re mis-representing the actual balance of your research interests.

The tractatus. You develop some principles or philosophical underpinnings for your work and then try to connect everything you’ve done to these and explain your future work ideas as further developing these themes. This approach goes for consistency above all else. The advantage is coherence, and the disadvantage is that some projects may have to get strong-armed into it.

I am sure there are more varieties out there, but on the whole the research statement is a weird document — part description, part proposal. You can’t make it only about your existing work because that’s looking to the past, but you can’t make it a proposal because the reader is actually trying to learn what you are interested in.

Broadcast gossip revisited : companion variables and convergence to consensus

Mike Rabbat pointed out his new preprint on ArXiv:

Broadcast Gossip Algorithms for Consensus on Strongly Connected Digraphs
Wu Shaochuan, Michael G. Rabbat

The basic starting point is the unidirectional Broadcast Gossip algorithm — we have n nodes in a graph and each node i starts with a value x_i(0). At each time, a random node broadcasts its value to its neighbors in the graph and they each update their value with the weighted average of their current value and the received value. Eventually, this process converges almost surely and all nodes i will have a common value \hat{x}. However, in general \hat{x} \ne \bar{x}, where \bar{x} = \frac{1}{n} \sum x_i(0), but \mathbb{E}[\hat{x}] = \bar{x}. So this process achieves consensus but only computes the average in expectation.

The reason broadcast gossip does’t compute the average is pretty clear — since the communication and updates are unidirectional, the average of the nodes’ values changes over time. One way around this is to use companion variables \{y_i(t)\} to track the effect of the broadcast. These have been studied before, but in this paper they set the initial values y_i(0) = 0 and perform updates as follows : if node k broadcasts at time t and node j is a neighbor, then

x_j(t+1) = (1 - a_{j,k}) x_j(t) + a_{j,k} x_k(t) + \epsilon d_j^{(k)} y_j(t)
y_j(t+1) = a_{j,k} (x_j(t) - x_k(t)) + (1 - \epsilon d_j^{(k)}) y_j(t) + b_{j,k} y_k(t)
x_k(t+1) = x_k(t)
y_j(t+1) = 0

So what’s going on here? Each time a node transmits it resets its companion variable to 0. Each time it receives a broadcast it accumulates an offset in y_j. The actual value estimate at the nodes is weighted average of the current and received value plus some of the local offset.

The parameters of the algorithm are matrices A = (a_{j,k}) and B = (b_{j,k}) and per-node matrices D_k = (d_j^{(k)}). Let

A_k = A e_k e_k^T
B_j = B e_k e_k^T
L_k = \mathrm{diag}(A_k \mathbf{1}) - A_k
S_k = I - e_k e_k^T + B_k

When node k broadcasts) we can write a matrix

W_k \left[ \begin{array}{cc} I - L_k & \epsilon D_k \\ L_k & S_k - \epsilon D_k \end{array} \right]

such that

\left[ \begin{array}{c} \mathbf{x}(t+1) \\ \mathbf{y}(t+1) \end{array} \right]^T = W(t) \left[ \begin{array}{c} \mathbf{x}(t) \\ \mathbf{y}(t) \end{array} \right]^T

where W(t) = W_k if node k broadcasts at time $t$.

The main results are:

  1. If we choose \epsilon small enough, then \lim_{t \to \infty} \mathbb{E}[ \mathbf{x}(t) | \mathbf{x}(0) ] = \hat{x} \mathbf{1} and \hat{x} = \bar{x} under more conditions.
  2. A sufficient condition for the second moment of the error to go to 0.
  3. Rules on how to pick the parameters, especially \epsilon.

There are also some nice simulations. Broadcast gossip is nice because of its simplicity, and adding a little monitoring/control variable y_j(t) seems to buy a lot in terms of controlling bad sample paths for the process.