The Angular Synchronization problem and a Cheeger Inequality

The good news: this week, my paper with Amit Singer and Daniel A. Spielman, A Cheeger Inequality for the Graph Connection Laplacian, was accepted for publication in the SIAM Journal on Matrix Analysis and Applications (SIMAX), so I thought this would be a good time to finally blog about it.

Let’s say we have a collection of two-dimensional photos of a three-dimensional object that are taken from many angles as it spins in mid-air. If we knew the angles from which the pictures were taken we could use the pictures to attempt to build a 3d model of the object. Unfortunately, in several applications (such as Cryo-electron microscopy) the angles are unknown. This post deals with the problem of estimating the angles.

Associated to each image , there is a unknown angle/rotation in , the space of special orthogonal matrices. By applying simple transformations, such as in-plane rotations, we will discover similarities between pairs of photos, say , , that will allow us to make an estimate , of the relative rotational between the two photos. We can organize this information on a graph where each vertex corresponds to a picture and where, to each relative rotation estimate, corresponds an edge .

Although the paper deals with general orthogonal groups I will restrict the discussion for in this post, and say a few words in the end about how the results generalize to . We can identify with , the set of unit-norm complex numbers. We will formulate the problem of obtaining estimates for the angles as

Let us assume for simplicity that the graph is -regular and let . Similarly to the way the Graph Laplacian is associated with Spectral Clustering, we can build a matrix that corresponds to the quadratic form in (1), the Graph Connection Laplacian . It varies from the Graph Laplacian as, in the off-diagonal , if , . This means we can rewrite (1) as

Let us denote , the optimal value of (2).

Note that if we relax the constraint in (2) to we get the spectral problem

whose optimum is given by , the smallest eigenvalue of . This optimum is achieved by the eigenvector of associated with which is efficient to compute. Note that, since is a relaxation of we have

This fact suggests the following (spectral) approximation algorithm which essentially consists of computing , the first eigenvector of and, for each compute an estimate for as,

This algorithm was first proposed in a paper by Amit Singer. Let us denote the performance of by

In the Cheeger Inequality for the Graph Connection Laplacian paper we show that, as long as the graph has good connectivity properties, the value of is in the order of . This implies that, there exists a constant , that dependents on the connectivity properties of the Graph, such that

Note that (5) has two important implications: First of all, it gives a guarantee for the spectral algorithm described assuring that the computed estimate has an error that is on the order of the optimal achievable. Secondly, it gives a Cheeger-type inequality relating the spectrum of the graph Connection Laplacian and the optimal value of the problem (2),

Theorem 1 [ Cheeger inequality for the Graph Connection Laplacian] As long as the graph is connected, there exists a constant depending only on the connectivity properties of the graph such that,

 

The spectral algorithm described above and, in particular, the guarantees explained above, play an important role in the Polarization approach to Phase Retrieval (you can read all about it on either the paper or Dustin Mixon’s blog post about it).

The same ideas can be used in when considering high-dimensional orthogonal groups . In this case, eigenvectors of need to be computed and the rounding scheme isn’t as simple as normalizing the entries as it needs to make use of the Polar Decomposition. In any way, a result completely analogous the SO(2) case (both the algorithmic guarantee and a Cheeger Inequality similar to Theorem 1) can be obtained (see the paper for more details).