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)

Sariel Har-Peled talked about the interface between Operations Research and low-dimensional geometry. The bottom line is that there is a ton of problems from OR that one can restrict for the case of low-dimensions, and they are pretty much largely unanswered or unaddressed. Primarily, he said, because they usually require tools from both ends. Here’s one that he discussed in detail.

Discrete unit-circle cover in the plane

A problem instance is given by a set of points in the plane and a set of unit discs. The goal is to find the smallest subset of the discs that covers all points. This problem is NP-complete (surprisingly). The open question is: Can you -approximate the optimum (for any )?

Bicriteria unit-circle cover in the plane

My recollection on this one may be slightly off. It’s the same problem as above, but you are shooting for a bicriteria algorithm where you are allowed to expand the given discs by a small , so the bicriteria is in . The question here may have been, what is the smallest disc expansion for which you can get a bicriteria solution equal to the optimum (without disc expansion).

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.

Vershynin gave a talk at MIT today on a beautiful recent result. Recall that the condition number of a matrix is . Where is the norm of defined as . Generalizing a long line of prior work Vershynin and Rudelson show that

For a random matrix , and with high probability (approaching 1). Here, the matrix is random in the sense that its entries are i.i.d. random variables, where the only restriction (if I recall correctly) is that the distribution of the matrix entries has a 4-th moment.

The pivotal technical theorem that leads to this result is yet again a generalization of a line of prior results, which informally goes like this

Let be given, and let be randomly chosen signs. If , then can be “embedded” (with small error) in an arithmetic progression of size at most .

This theorem is the key ingredient to proving anti-concentration results – the opposite of what we usually do in Probability Theory – you want to prove that measure is spread out, not focused.

The talk was a very nice walk through the connection between a few fields: geometry, functional analysis, probability and combinatorics. What was interesting to me was how crisp-and-clear the connection between continuous objects (i.e. random real matrices) and additive combinatorics (i.e. arithmetic progression business) becomes after listening to this result.