Alex Samorodnitsky talked about LP bounds for coding at MIT. A few small things I wanted to jot down follow. Delsarte was the first one to attempt an LP-type bound for coding. It sounded that his work would be interesting to read as establishing the actual bound went through some algebra and some geometry. In 1989 Kalai-Linial publish a Fourier-based approach to the analysis of Delsarte’s LP. Alex suggested that this may be the first time Fourier is used in Computer Science. The LP bound, which is essentially a packing bound for the Hamming cube, has counterparts in Mathematics regarding packings in metric spaces. Alex’s latest paper (S’08) has references to all these, but it is not available yet. So a related link is a previous paper of his and Navon’s.

Guillermo Sapiro has done some quite fascinating work on applications of compressed sensing to photography (and one might say to practice in general) which he spoke about at MIT last week. The tagline is this: In compressed sensing one proves that using a random basis (i.e. random sensing matrix) one can recover signals (after the measurement) as long as one knows any basis where the signal is sparse. In other words, random matrices have this universality property. In practice, however, if you sense with a random matrix the recovery quality of, say, images is somewhat horrible — images come out as if you added Gaussian noise to them. Sapiro’s work addresses this problem.

The key idea in his work is to learn a basis that is good for images. Such basis will have to give up the universality property, but this is OK. Learning such a basis is done by taking a big collection of images and trying to find a basis where all images have sparse representations that are not too far (in L2 sense) from the original images. It turns out that a relatively simple iterative algorithm, involving linear regression at each step, does the job just fine. The results are stunning! Images come out with practically perfect quality. 

··· Read more (and comment)

I was very pleasantly surprised today to discover that what I call (the class of) Population Algorithms has recently (this past year) been considered (not under this name) by Khandekar and Awerbuch. I am delighted to put links to their relevant papers:

• Stateless Distributed Gradient Descent for Positive Linear Programs, Awerbuch, Khandekar, STOC’08
• Stateless Near Optimal Flow Control with Poly-logarithmic Convergence, Awerbuch, Khandekar, LATIN’08

The crazy title up there means “recovering a 3D model of a molecule, using multiple 2D images/projections”. This was a talk at MIT by Yoel Shkolnisky. The talk was really neat, but the bottom line is this. From a CS point of view he was solving the following question. We have n points that (we know) come from some finite metric. We are given the pairwise distances (+ noise) between points that are within each other’s vicinity (in that metric). The goal is to reconstruct the metric. I’ve phrased this problem a little more generally then the form in which it is addressed in Yoel’s work.

The cool thing is that Yoel et al. solve this problem using a very natural appeal to graph Laplacians. This is found in a technical report on his page. Amit Singer (a collaborator) additionally has a paper on using these techniques to recover the global metric of sensor networks, based on local distance information. This is found in the form of a paper on Amit’s webpage.

There might be an opportunity for a new paper lurking in there. In particular, it is interesting to ask under what noise conditions (and noise can be correlated in real-world examples) is the recovery good. Having heard the talk, I believe that the answer to this question will also depend on the type of metric being recovered, i.e. it may depend on its doubling dimension e.g.

Oh, I should also mention that Yoel seems to have some cool papers involving the discrete Radon transform. This is probably a good place to read about it, while avoiding the continuous lingo.

Spectral Graph theory has various methods of bounding the Laplacian eigenvalues of a graph G (say by embedding another graph H into G and computing the congestion). Usually we look at the ordered eigenvalues , and usually we simplify things a little by assuming a bounded-degree graph, which gives us for free, where is the maximum vertex degree. So really, it is mostly just interesting to bound from below. When this is done, it is very often used as (when bounding energy of electrical flows in G) or as (when bounding mixing times of random walks on G).

We are interested in a new type of Laplacian bounds. It turns out that L1 bounds of the sort relate directly to how good electrical flow is when used for oblivious routing on G. Note that it is required here that since is the kernel of the Laplacian of any connected graph. This sort of bound is atypical in two ways. First, it is an L1 bound, and second, it is a lower-bound.

It is trivial to see that where is the Laplacian of the n-clique. What we are after is proving that

where H is an expander and and .

This statement holds true in experiments with random bounded-degree expanders, and in particular it has natural interpretations in terms of electrical flow (which I am going to omit here). One can even give a pseudo-proof of this fact by simply observing that .

I am curious if someone has come across similar types of inequalities and/or has an interesting proof idea.

Note that the above conjecture was recently proven and its proof will soon appear in a publication. I will post a link to it here when this happens. At this stage will be happy to hear of applications of this (now) theorem if you come across any.

I’d like to spell out a conjecture of Feige (which is pretty elegant and simple to state) if for no better reason so that I don’t forget it:

Let be independent random non-negative variables with (and arbitrary variance). Then .

The conjecture is a little more general than that, but I’ve purified it for simplicity and, in fact, the above statement is the crux of the conjecture. Feige already proved the conjecture when is replaced by using a, well, horrendous case analysis. So the goal here is really to get the constant and hopefully with a more natural argument.

This conjecture appears in On the sum of nonnegative independent random variables with unbounded variance, Feige’03. I believe that solving implies a better approximation constant for a certain sub-modular optimization problem.

In a recent paper “Graph sparsification by effective resistances”, Spielman, Srivastava (STOC’08) show that one can sparsify a graph by essentially randomly getting rid of edges with very low effective resistance. Here we discuss an interesting corollary of one of the lemmas in this paper, which is not explicitly mentioned in the paper. In particular, we show a direct connection between the edge density of a graph and the smallest effective resistance.

For a graph define . This is all standard notation: is the diagonal edge-weights matrix, is the edge orientation matrix, and is the Laplacian. (Note we have that .)

The matrix has the property that , where is the effective resistance of edge , and is its weight. We’ll focus on the case when all for simplicity. We prove the following statement:

If graph has vertices and edges, then there is an edge of effective resistance at most . 
 

To see this, we use Lemma 3 in the paper which states that has eigenvalue of multiplicity , and eigenvalue 0 of multiplicity . The sum of the eigenvalues thus equals . On the other hand, the trace of equals . Equating the two (and using ) we get . Therefore . Thus, there must exist at least one edge with effective resistance at most .

This inequality is tight in various small-graph cases that one could think of. And it is asymptotically tight in others (a long cycle with a shortcut in the middle). It is interesting to find out whether it is tight for large graphs of intermediate density (more than linear, less than quadratic).

Let’s see how this equality relates (directly) to sparsification. A close inspection of Lemma 4 in the paper asserts the following statement:

If we remove an edge from a graph, then the Laplacian of the new and the old graph are related by . This inequality is tight on both sides.

On the left equality is attained when considering the vector of potentials corresponding to a unit electric flow between the endpoints of . On the right equality is attained by considering any vector that equals 0 over the endpoints of .

The last statement combined with the inequality (that relates effective resistance to density) beg the question whether one can sparsify a graph by removing one edge at a time (and re-weighting the rest appropriately). If this is indeed a possibility, it would also have to be true that any sequence of removed edges that leads to a best sparsification must contain the edge of smallest effective resistance in the original graph.

The questions mentioned here are important since they relate to the conjecture that all graphs have linear-size sparsifiers. It is also a possibility that a one-edge-at-a-time procedure may lead to a more practical sparsification (in the Laplacian sense) algorithm than the currently available alternatives.

I will reward a $10 prize to the first person who (dis)proves the following simple conjecture:

Let be uniformly distributed on the ball . Then, for every the variance of is independent of , i.e. is a universal constant.

If you are wondering why I am posting simple conjectures for prize money — it is because I would have hated to spend the time (which I am short on) to discover they are false, while I would become immediately excited about them (and their consequences) if they are true

I will post the first correct solution as soon as it arrives, so if you are not seeing a solution below, get cracking. As a bonus for resolving this problem in the positive, I will share with you why it is important. I do require a complete formal argument!

(Prize has been awarded, see below!)

In fact, a slight variation on Alex’ argument (below) gives:

No distribution on has the property that depends only and non-trivially on .

Here’s why. Write , and . Expand and using and combine to get . Substitute the latter back into to obtain . The latter, combined with the requirement , holds only when or thus giving a contradiction.

Applied programmers tend to dread the prospect of having to write parsers because the process is usually laborious, error-prone and unclean — all due to the computational complexities of parsing Context Free Grammars (CFG’s) in practice. A great new alternative has emerged in recent years, which makes design and implementation of complex expressive languages a pleasant exercise accessible to most.

Why are CFG’s a mess in practice?

The most expressive, widely-used and familiar notion of a language formalism are CFG’s. They are easy to think of (in theory), since the following example rule essentially summarizes them completely:

A → AxByC | Dz | xy

Lower- and upper-case letters denote terminals and non-terminals, respectively, while the “|” symbol denotes non-deterministic choice. Nice and simple. However, parsing CFGs is computationally expensive (quadratic time), which has lead to two (complicating) trade-offs in practice:

··· Read more (and comment)