Guest post by Andy Zhu: Alignment and Unique Games

Happy holidays! Afonso asked me a while back to write a guest blog post, and I figured this would make a decent Christmas gift. Just to quickly introduce myself, I did some undergraduate mathematical research at Princeton University with Afonso. Today’s post is on some findings in this paper (to appear in the ITCS 2014 conference proceedings), which is joint work with Afonso, Amit Singer, and Moses Charikar from Princeton.

To align a pair of rotated images on the disc ${D^2}$ , one simply measure the similarity of different rotations of the images and choose the best one (say cross-correlation in signal space, or phase correlation in frequency space). How about multiple noisy, rotated images? For a fixed noise distribution and sufficiently many observations, we certainly expect to be able to recover the underlying template. The main difficulty is that nothing is known about the rotations or the underlying image. We describe an approach to this multiple observation alignment problem using theory developed for the Unique Games problem.

Unique Games

What follows is a quick overview on Unique Games. The Unique Games problem is a constraint satisfaction problem, where a set of variables take on values from a finite set, and pairs of variables are restricted by one-to-one relations. A Unique Games instance ${\mathfrak{U}}$ is specified by a label set ${\mathcal{L}}$ of size ${L}$ , and a graph ${G}$ with ${N}$ vertices, ${M}$ edges, each of the edges ${(i,j)}$ is associated with a permutation ${\pi_{ij}: \mathcal{L} \rightarrow \mathcal{L}}$ . The objective is to find the label assignment to the vertices ${l_i \in \mathcal{L}}$ which maximizes the number of satisfied constraints ${\pi_{ij}(l_i) = l_j}$ . If a vertex labeling exists which satisfies all of the edge constraints of ${\mathfrak{U}}$ , the instance is said to be complete. ${\mathfrak{U}}$ is said to be ${\alpha}$ -satisfiable if ${\alpha}$ fraction of the edges may be satisfied by a vertex labeling. Identifying difficult from easily satisfiable Unique Game instances is conjectured to be NP-hard:

(Khot 2002) It is NP-hard to distinguish ${(1-\delta)}$ -satisfiable from at most ${\varepsilon}$ -satisfiable Unique Games instances, for all ${\delta, \varepsilon > 0}$ .

Many notable problems have since been reduced to Unique Games, notably the optimality of the Goemans-Williamson approximation ratio ${\alpha_{GW}}$ for poly-time approximation of MAX-CUT. [In the other direction, subclasses of Unique Games have been shown to be as hard as Unique Games: MAX-LIN is such a subclass, where the permutations ${\{\pi_{ij}\}}$ are group actions on ${\mathcal{L}}$ .]

The most studied approximation algorithms for Unique Games are “indicator variable” semidefinite programming relaxations. To motivate this, observe that for a choice of labels ${( l_i ) \in \mathcal{L}^N}$ , the number of satisfied edge constraints is:

$\displaystyle \sum_{i,j = 1}^N \delta (\pi_{ij}(l_i) = l_j).$

We can rewrite this by summing over ${\{0,1\}}$ indicator variables characterizing each possible label assignment ${l_i = k \in \mathcal{L}}$ ,

$\displaystyle \sum_{ k,l \in \mathcal{L}} \sum_{ i,j } u_{ik} u_{jl} \cdot \delta(\pi_{ij}(k) = l),$

where ${u_{ik}}$ is ${1}$ if ${l_i = k}$ , and ${0}$ otherwise. Let ${U \in \{0,1\}^{NL \times NL}}$ be the matrix with ${(i,k; j,l)}$ th entry ${u_{ik} u_{jl}}$ . ${U = uu^T}$ is then a rank one, positive semidefinite Gram matrix. The above expression is linear in the entries of ${U}$ , and can be expressed as $\mathrm{Tr}(CU)$ for the appropriate coefficient matrix ${C}$ . Hence, to maximize the number of satisfied constraints, we can maximize ${\mathrm{Tr}(CU)}$ over all ${U \in \mathbb{R}^{NL \times NL}}$ satisfying conditions which enforce that ${U = uu^T}$ , where ${u = \{u_{ik}\}}$ are label indicators. For example,

${U_{(i,k; i,l)} = 0}$ for each ${k \neq l}$ , (a given variable ${l_i}$ can only have one label)
${\sum_{k,l \in \mathcal{L}} U_{(i,k; j,l)} = 1}$ , (joint probability of labels also sums to one)
${U}$ is positive semidefinite,
rank ${(U) = 1}$ .

These constraints are essentially sufficiently restrictive to require ${U}$ to have the desired decomposition into label indicator vectors. The domain these constraints specify is non-convex due to the rank constraint, so this optimization problem is quite difficult to solve. If we remove this rank constraint, the result is a semidefinite program ${\max_{U \succeq 0} \mathrm{Tr}(CU)}$ subject to the first three enumerated conditions. Then this optimization problem can be solved by convex programming methods in polynomial time, and the solution matrix ${U^{SDP} = \mathrm{argmax} \mathrm{Tr}(CU)}$ can be rounded to the original non-convex search space (say by taking a rank-one approximation).

The best known poly-time approximation ratios for Unique Games are based on clever rounding approaches on solutions to more restrictive variations of this SDP (see here).

Phase correlation

A slight variation on Unique Games can be used to produce a heuristic for multi-image alignment. For simplicity, consider ${N}$ discrete images ${y_1, \ldots, y_N: \mathbb{Z}_L \rightarrow \mathbb{R}}$ on the unit circle, where each ${y_i}$ is generated by shifting a template image ${x}$ by some discrete shift ${l_i^* \in \mathbb{Z}_L}$ and adding some noise distribution ${y_i = R_{l_i^*} x + \xi_{i}}$ , where ${R_l}$ is the operator corresponding to shifting the image by ${l}$ modulo ${L}$ . From the observations, we want to recover the “labels” ${l_i^* \in \mathbb{Z}_L}$ . As in Unique Games, we have information constraining pairs of labels. For example, the larger the inner product ${\langle R_{-k} y_i, R_{-l} y_j \rangle}$ is, the more probable the labels ${\{l_i^* = k, l_j^* = l\}}$ hold. Based on this observation, we can write a similar SDP to find indicator variables for the ${l_i^*}$ ‘s:

$\displaystyle \max \sum_{ij} \sum_{kl} U_{(i,k;\,j,l)} \langle R_{-k} y_i, R_{-l} y_j \rangle$

subject to

${U_{(i,k; i,l)} = 0}$ for each ${k \neq l}$ ,
${\sum_{k,l \in \mathcal{L}} U_{(i,k; j,l)} = 1}$ ,
${U}$ is positive semidefinite.

As proof we are on the right track, it turns out that the solution to this SDP returns the same result as we would get by performing phase correlation between pairs of the observations (this is a consequence of symmetries in the structure of the coefficient matrix)! Of course, we would like to be able to do better. Empirically, with additional constraints restricting the search space, such as a positivity constraint ${U \ge 0}$ , the SDP solution quite often will return an integral instance. That is, the SDP solution can exactly be written as ${U = uu^T}$ , where ${u \in \{0,1\}^{NL}}$ is a vector of label indicators. This integrality phenomenon does appear in other similar SDP relaxations (for example, MIMO).

Some rigorous justification can be made about the integrality of this SDP. Analysis of semi-random models of Unique-Games (take a complete instance, randomly corrupt ${\varepsilon}$ of the edge constraints) can result in exact recovery for small enough ${\varepsilon}$ . Similar techniques can be used to bound the gap between the SDP solution and the integral instance for this alignment application. Can stronger tightness results be obtained? – Andy Zhu

Relax and Conquer

A math research blog by Afonso S. Bandeira

Guest post by Andy Zhu: Alignment and Unique Games

Leave a Reply Cancel reply

Share this:

Like this:

Related

Leave a Reply Cancel reply