Amit Singer just gave a very cool talk at Wisconsin’s Applied Algebra Day. Slides from a similar talk he gave at ICERM are here.

Briefly: the problem is to reconstruct an image (so let’s say a function f in L^2(R^3) measuring density, or potential, or whatever) from a bunch of linear 2d projections. This is what you get when you try to do cryo-EM on molecules of biological origin; you have no control of how the molecules are oriented, so when you pass a beam through them and record the shape of the “shadow” you get, you’re looking at a projection of the molecule in an unknown direction. But of course you may have 10,000 of the molecules, so you have 10,000 of these (noisy) projections at a bunch of different angles, and one may hope that this is enough information to reconstruct the original 3d shape!

Suppose f’ is one of these projections. If F is the Fourier transform of f, and F’ the Fourier transform of f’, then F’ is just the restriction of F to some plane through the origin.

So we have the following problem: there’s a mystery function F on R^3, and we have a bunch of functions F’_1, .. F’_n on R^2 which are restrictions of F to planes, but we don’t know *which* planes. How to reconstruct those planes, and F?

Let G = SO(3). We can set this problem up as an optimization problem over G^n as follows. We want to find F and g_1, … g_n in G such that F’_i matches the restriction to the xy-plane of g_i F.

But optimizing over G^n is hard — an essentially exponential problem. So what Singer and his collaborators do is discretize and convexize the problem in a very clever way. You put a net of L points on S^2; then every rotation is going to induce (after some rounding) a permutation of these points, i.e. an LxL permutation matrix. What’s more, n rotations just give you n permutations, which is an L x Ln matrix.

But optimizing over permutation matrices has a nice convex relaxation; the convex hull of the permutation matrices is the polytope of doubly stochastic matrices, which is very manageable. It gets better: a general permutation of the witness points on the sphere, of course, looks nothing at all like a rotation. But the fact that a rotation preserves distances means that the corresponding permutation approximately commutes with the LxL covariance matrix of the points; this is a linear condition on the permutation matrices, so we end up optimizing over a linear slice of the doubly stochastic matrices. And the point is that the difficulty now scales polynomially in n instead of exponentially. Very nice! (Of course, you also have to show that the cost function you’re actually optimizing can be made linear in this setup.)

Idle question: how essential is the discretization? In other words, is there a way to optimize directly over the convex hull of SO(3)^n, an object I know people like Bernd Sturmfels like to think about?

Hi Jordan,

Glad you liked these ideas, and congratulations for the great blog!

Just to briefly answer your question, the issue with optimizing over the SO(3) is not just the nonconvexity of the space (which could potentially be dealt with by relaxing to the convex hull) but also the fact that the objective function is not linear (or convex!) over SO(3). This goes back to your comment above, that one still needs to show that the objective is indeed linear when written as a function of the induced permutation matrices, the function indeed is linear but it is not obvious. What would be easier to see is that it would be linear in permutations of a (near) discretization of SO(3) instead of S^2, but it is indeed possible to do it over S^2 as well and this really helps with the dimensionality of the optimization problems.

We are in the process of writing up these ideas, and hopefully everything will be clearer there. I’ll let you know when it is ready. I’ll also write a blog post explaining these ideas more informally :)

Just a side comment: One could try to directly optimize the non-linear function over SO(3) (or its convex hull) using local methods for optimization on manifolds. The issue with this methods is that they risk getting stuck in local optima (and often do) and tend to lack theoretical guarantees. In any way, these methods are very useful to do local refinements of solutions obtained by relaxation procedures such as the one described.

Best,

Afonso

http://afonsobandeira.wordpress.com/