The Angular Synchronization problem and a Cheeger Inequality

The good news: this week, my paper with Amit Singer and Daniel A. SpielmanA 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 {i}, there is a unknown angle/rotation {g_i} in {SO(3)}, the space of {3\times 3} special orthogonal matrices. By applying simple transformations, such as in-plane rotations, we will discover similarities between pairs of photos, say {i}, {j}, that will allow us to make an estimate {\rho_{ij}}, of the relative rotational {g_ig_j^{-1}} between the two photos. We can organize this information on a graph where each vertex {i\in V} corresponds to a picture and where, to each relative rotation estimate, corresponds an edge {e\in E}.

Although the paper deals with general orthogonal groups I will restrict the discussion for {SO(2)} in this post, and say a few words in the end about how the results generalize to {O(d)}. We can identify {SO(2)} with {\mathbb{T}}, the set of unit-norm complex numbers. We will formulate the problem of obtaining estimates for the angles {g_i} as

\displaystyle \min_{g:V\rightarrow \mathbb{T}}\sum_{(i,j)\in E}\| g_i - \rho_{ij}g_j\|^2. \ \ \ \ \ (1)

Let us assume for simplicity that the graph is {d}-regular and let {n=|V|}. 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 {L_1}. It varies from the Graph Laplacian as, in the off-diagonal {(i,j)}, if {(i,j)\mathop{\mathbb E}}, {L_1(i,j) = -\rho_{ij}}. This means we can rewrite (1) as

\displaystyle \min_{\substack{|g_i|^2 = 1 \\ g\in\mathbb{C}^n}}g^T L_1 g. \ \ \ \ \ (2)

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

Note that if we relax the constraint {|g_i|^2 = 1} in (2) to {\|g\|^2 = n} we get the spectral problem

\displaystyle \min_{\substack{\|g\| = 1 \\ g\in\mathbb{C}^n}}g^T L_1 g, \ \ \ \ \ (3)

whose optimum is given by {opt(3) = n\lambda_1(L_1)}, the smallest eigenvalue of {L_1}. This optimum is achieved by the eigenvector {x} of {L_1} associated with {\lambda_1(L_1)} which is efficient to compute. Note that, since {(3)} is a relaxation of {(2)} we have

\displaystyle n\lambda_1(L_1) \leq opt(2).

This fact suggests the following (spectral) approximation algorithm which essentially consists of computing {x}, the first eigenvector of {L_1} and, for each {i\in V} compute an estimate for {g_i} as,

\displaystyle \hat{g}_i = \frac{x_i}{|x_i|}.

This algorithm was first proposed in a paper by Amit Singer. Let us denote the performance of {\hat{g}} by

\displaystyle \mu = \hat{g}^TL_1\hat{g}. \ \ \ \ \ (4)

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 {\mu} is in the order of {n\lambda_1(L_1)}. This implies that, there exists a constant {c}, that dependents on the connectivity properties of the Graph, such that

\displaystyle n\lambda_1(L_1) \leq opt(2) \leq \mu \leq cn\lambda_1(L_1)\leq c\ opt(2). \ \ \ \ \ (5)

Note that (5) has two important implications: First of all, it gives a guarantee for the spectral algorithm described assuring that the computed estimate {\hat{g}} 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 {L_1} and the optimal value of the problem (2),

Theorem 1 [{SO(2)} Cheeger inequality for the Graph Connection Laplacian] As long as the graph {G=(V,E)} is connected, there exists a constant {c} depending only on the connectivity properties of the graph such that,

\displaystyle n\lambda_1(L_1) \leq opt(2) \leq c\ opt(2).

 

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 {O(d)}. In this case, {d} eigenvectors of {L_1} 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).

Advertisements

One thought on “The Angular Synchronization problem and a Cheeger Inequality

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s