Population Algorithms by Petar Maymounkov

Learning sensing bases and photography – 2

Under Compressed sensing, Computer Science, Talk

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 the rest (and comment)

Two problems in geometric set cover – No Comments

Under Open problems, Talk

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 $(1+\epsilon)$ -approximate the optimum (for any $\epsilon>0$ )?

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 $\delta>0$ , so the bicriteria is in $(\epsilon,\delta)$ . The question here may have been, what is the smallest disc expansion $1+\delta$ for which you can get a bicriteria solution equal to the optimum (without disc expansion).

Paul’s Canonical Tester – No Comments

Under Computer Science, Mathematics, PR: Probability, Property testing

Paul Valiant’s Canonical Tester is a one-stop-shop solution for testing any symmetric property of a distribution. If the Canonical Tester can’t do it, neither can you. The additional upshot is that the Canonical Tester is quite simple an algorithm, so proving lower bounds (impossibility results) usually takes short 5-line arguments explaining why the Canonical Tester can’t do it.

Testing asymmetric properties is now the next interesting question. Interesting it is indeed because most practical questions actually tend to involve asymmetric properties. A modified example of Paul’s talk goes like this. Imagine Amazon makes a change on their website, and they like to know whether more books compared to electronics were sold after the change. This is an asymmetric test.

Population algorithms – No Comments

Under Computer Science, Linear programming, Population algorithms

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

Cryo-EM structure determination – No Comments

Under Computer Science, FA: Functional Analysis, Graph spectra, Mathematics, Spontaneous, Talk

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.

MIT Theory Lunch 5/7/08 – No Comments

Under Spontaneous

MIT has a lunch for students and professors in the Theory of Computation group, where one can eat pizza and here other people’s casual open problems. Sometimes really cute problems and/or discussions fall out. Today (non-exhaustive):

Alexandr Andoni asked — Consider the following Shifted Hamming (SH) distance on bit strings. The distance between two strings is defined as the Hamming distance after shifting (really rotating) one of the strings by an arbitrary amount (which produces the smallest Hamming distance). The questions are. Can we embed the SH metric into the Hamming metric with low distortion? If I am not mistaken, Alex knows a lower bound on the distortion of O(log n) using a Fourier argument. And, can we embed SH into $\ell_2^2$ (the squared Euclidean norm)? I believe no lower bound is known here and O(1) may be possible.
Ron Rivest is working on an intentionally very simple election auditing system, which hinges on a pseudorandom function that can be computed on a handheld calculator in a few strokes. The detailed description of the procedure is on his website (I couldn’t find, but it is there!). Ron asked if there are any obvious attacks/problems with his design. His question brought up a somewhat simpler question that seems very curios to me: Pick a random integer between 1 and 1000, take its square root, and consider the first bit of its fractional part. How far is the distribution of that bit from uniform?

L1 bounds for Laplacians – No Comments

Under Computer Science, Graph spectra, Question, Spontaneous

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 $0=\lambda_1<\lambda_2\le \cdots \le \lambda_n$ , and usually we simplify things a little by assuming a bounded-degree graph, which gives us $\lambda_n\le D_{\max}=O(1)$ for free, where $D_{\max}$ is the maximum vertex degree. So really, it is mostly just interesting to bound $\lambda_2$ from below. When this is done, it is very often used as $\|L^{-1}x\|_2 \le \lambda_2^{-1} \|x\|_2$ (when bounding energy of electrical flows in G) or as $\|(I-L)^kx\|_2\le (1-\lambda_2)^k \|x\|_2$ (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 $\min_{x\bot\vi,\|x\|_1=1}\|Lx\|_1\ge \eta$ relate directly to how good electrical flow is when used for oblivious routing on G. Note that it is required here that $x\bot\vi$ since $\vi$ 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 $\|L_{K_n}x\|_1=n$ where $L_{K_n}$ is the Laplacian of the n-clique. What we are after is proving that

$\|L_H x\|_1\ge (\log n)^{-1}$ where H is an expander and $\|x\|_1=1$ and $x\bot\vi$ .

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 $L_H \approx L_{K_n} / n\log n$ .

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

Fonts are … – No Comments

Under Typography

… infinitely fascinating, and have been so since I was a kid. They are one (of many) lenses through which one perceives abstract information. And they influence the sentiment attached to what we read, as well as the fluidity with which we absorb it. Aren’t them special? Here I am giving my short list of enjoyable typography links on the Internet, which hopefully make for a pleasant introduction to the business of fonts. My list of links, designers and fonts is significantly non-exhaustive. It is more of a random sample of good things.

··· Read the rest (and comment)

Feige’s conjecture for sums with unbounded variance – 2

Under Combinatorial optimization, Computer Science, Mathematics, PR: Probability

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 $X_1,\dots,X_n$ be independent random non-negative variables with $\E [X_i]=1$ (and arbitrary variance). Then $\Pr[\sum X_i < n + 1] \ge 1/e$ .

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 $1/e$ is replaced by $1/13$ using a, well, horrendous case analysis. So the goal here is really to get the constant $1/e$ 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.

Positive semidefinite operators and norm polytopes – 5

Under FA: Functional Analysis, Question

I’ve been obsessing over the following conjecture. And to be honest I haven’t been able to find any counterexamples, nor make any significant progress towards proving it. So, here goes:

If $A,B$ are positive semidefinite and $A\preccurlyeq B$ , then $\|A\|_{1\rightarrow 1} \le \|B\|_{1\rightarrow 1}$ .

In fact, it seems that if this is true for the $\|\cdot\|_{1\rightarrow 1}$ -norm, it probably is true for all norms of the form $\|\cdot\|_{p\rightarrow p}$ . Any ideas or references would be greatly appreciated.