# normalized_spectral_map_synchronization__1abf36e4.pdf

Normalized Spectral Map Synchronization

Yanyao Shen UT Austin Austin, TX 78712 shenyanyao@utexas.edu

Qixing Huang TTI Chicago and UT Austin Austin, TX 78712 huangqx@cs.utexas.edu

Nathan Srebro TTI Chicago Chicago, IL 60637 nati@ttic.edu

Sujay Sanghavi UT Austin Austin, TX 78712 sanghavi@mail.utexas.edu

Estimating maps among large collections of objects (e.g., dense correspondences across images and 3D shapes) is a fundamental problem across a wide range of domains. In this paper, we provide theoretical justifications of spectral techniques for the map synchronization problem, i.e., it takes as input a collection of objects and noisy maps estimated between pairs of objects along a connected object graph, and outputs clean maps between all pairs of objects. We show that a simple normalized spectral method (or Norm Spec Sync) that projects the blocks of the top eigenvectors of a data matrix to the map space, exhibits surprisingly good behavior Norm Spec Sync is much more efficient than state-of-the-art convex optimization techniques, yet still admitting similar exact recovery conditions. We demonstrate the usefulness of Norm Spec Sync on both synthetic and real datasets.

1 Introduction

The problem of establishing maps (e.g., point correspondences or transformations) among a collection of objects is connected with a wide range of scientific problems, including fusing partially overlapped range scans [1], multi-view structure from motion [2], re-assembling fractured objects [3], analyzing and organizing geometric data collections [4] as well as DNA sequencing and modeling [5]. A fundamental problem in this domain is the so-called map synchronization, which takes as input noisy maps computed between pairs of objects, and utilizes the natural constraint that composite maps along cycles are identity maps to obtain improved maps.

Despite the importance of map synchronization, the algorithmic advancements on this problem remain limited. Earlier works formulate map synchronization as solving combinatorial optimizations [1, 6, 7, 8]. These formulations are restricted to small-scale problems and are susceptible to local minimums. Recent works establish the connection between the cycle-consistency constraint and the low-rank property of the matrix that stores pairwise maps in blocks; they cast map synchronization as low-rank matrix inference [9, 10, 11]. These techniques exhibit improvements on both the theoretical and practical sides. In particular, they admit exact recovery conditions (i.e., on the underlying maps can be recovered from noisy input maps). Yet due to the limitations of convex optimization, all of these methods do not scale well to large-scale datasets.

In contrast to convex optimizations, we demonstrate that spectral techniques work remarkably well for map synchronization. We focus on the problem of synchronizing permutations and introduce a robust and efficient algorithm that consists of two simple steps. The first step computes the top eigenvectors of a data matrix that encodes the input maps, and the second step rounds each block of

30th Conference on Neural Information Processing Systems (NIPS 2016), Barcelona, Spain.

the top-eigenvector matrix into a permutation matrix. We show that such a simple algorithm possesses a remarkable denoising ability. In particular, its exact recovery conditions match the state-of-the-art convex optimization techniques. Yet computation-wise, it is much more efficient, and such a property enables us to apply the proposed algorithm on large-scale dataset (e.g., many thousands of objects). Spectral map synchronization has been considered in [12, 13] for input observations between all pairs of objects. In contrast to these techniques, we consider incomplete pair-wise observations, and provide theoretical justifications on a much more practical noise model.

2 Algorithm

In this section, we describe the proposed algorithm for permutation synchronization. We begin with the problem setup in Section 2.1. Then we introduce the algorithmic details in Section 2.2.

2.1 Problem Setup

Suppose we have n objects S1, , Sn. Each object is represented by m points (e.g., feature points on images and shapes). We consider bijective maps φij : Si Sj, 1 i, j n between pairs of objects. Following the convention, we encode each such map φij as a permutation matrix Xij Pm, where Pm is the space of permutation matrices of dimension m:

Pm := {X|X [0, 1]m m, X1m = 1m, XT 1m = 1m},

where 1m = (1, , 1)T Rm is the vector whose elements are 1.

The input permutation synchronization consists of noisy permutations Xin ij G along a connected object graph G. As described in [4, 9], a widely used pipeline to generate such input is to 1) establish the object graph G by connecting each object and similar objects using object descriptors (e.g., HOG [14] for images) , and 2) apply off-the-shelf pair-wise object matching methods to compute the input pair-wise maps (e.g., SIFTFlow [15] for images and BIM [16] for 3D shapes).

The output consists of improved maps between all of objects

Xij, 1 i, j n.

2.2 Algorithm

We begin with defining a data matrix Xobs Rnm nm that encodes the initial pairwise maps in blocks:

didj Xin ij, (i, j) G

0, otherwise (1)

where di := |{Sj|(Si, Sj) G}| is the degree of object Si in graph G. Remark 1. Note that the way we encode the data matrix is different from [12, 13] in the sense that we follow the common strategy for handling irregular graphs and use a normalized data matrix.

The proposed algorithm is motivated from the fact that when the input pair-wise maps are correct, the correct maps between all pairs of objects can be recovered from the leading eigenvectors of Xobs: Proposition 2.1. Suppose there exist latent maps (e.g., the ground-truth maps to one object) Xi, 1 i n so that Xin ij = XT j Xi, (i, j) G. Denote W Rnm m as the matrix that collects the first m eigenvectors of Xobs in its columns. Then the underlying pair-wise maps can be computed from the corresponding matrix blocks of matrix WW T :

XT j Xi = Pn i=1 di p

didj (WW T )ij, 1 i, j n. (2)

The key insight of the proposed approach is that even when the input maps are noisy (i.e., the blocks of Xobs are corrupted), the leading eigenvectors of Xobs are still stable under these perturbations (we will analyze this stability property in Section 3). This motivates us to design a simple two-step permutation synchronization approach called Norm Spec Sync. The first step of Norm Spec Sync computes the leading eigenvectors of W; the second step of Norm Spec Sync rounds the induced

Algorithm 1 Norm Spec Sync

Input: Xobs based on (1), δmax Initialize W0: set W0 as an initial guess for the top-m orthonormal eigenvectors, k 0 while W (k) W (k 1) > δmax do

W (k+1)+ = Xobs W (k), W (k+1)R(k+1) = W (k+1)+, (QR factorization), k k + 1. end while Set W = W (k) and X spec i1 = (WW T )i1. Round each X spec i1 into the corresponding Xi1 by solving (3). Output: Xij = XT j1Xi1, 1 i, j n.

matrix blocks (2) into permutations. In the following, we elaborate these two steps and analyze the complexity. Algorithm 1 provides the pseudo-code.

Leading eigenvector computation. Since we only need to compute the leading m eigenvectors of Xobs, we propose to use generalized power method. This is justified by the observation that usually there exists a gap between λm and λm+1. In fact, when the input pair-wise maps are correct, it is easy to derive that the leading eigenvectors of Xobs are given by:

λ1(Xobs) = = λm(Xobs) = 1, λm+1(Xobs) = λn 1(G),

where λn 1(G) is the second largest eigenvalue of the normalized adjacency matrix of G. As we will see later, the eigen-gap λm(Xobs) λm+1(Xobs) is still persistent in the presence of corrupted pair-wise maps, due to the stability of eigenvalues under perturbation.

Projection onto Pm. Denote Xspec ij :=

didj (WW T )ij. Since the underlying ground-truth maps

Xij, 1 i, j n obey Xij = XT jk Xik, 1 i, j n for any fixed k, we only need to round Xspec ik into Xik. Without losing generality, we set k = 1 in this paper.

The rounding is done by solving the following constrained optimization problem, which projects Xobs i1 onto the space of permutations via the Frobenius norm:

Xi1 = arg min X Pm X Xobs i1 2 F = arg min X Pm

X 2 F + Xobs i1 2 F 2 X, Xobs i1

= arg max X Pm X, Xobs i1 . (3)

The optimization problem described in (3) is the so-called linear assignment problem, which can be solved exactly using the Hungarian algorithm whose complexity is O(m3) (c.f. [17]). Note that the optimal solution of (3) is invariant under global scaling and shifting of Xobs i1 , so we omit

1 m11T when generating Xobs ij (See Algorithm 1).

Time complexity of Norm Spec Sync. Each step of the generalized power method consists of a matrixvector multiplication and a QR factorization. The complexity of the matrix-vector multiplication, which leverages of the sparsity in Xobs, is O(n E m2), where n E is the number of edges in G. The complexity of each QR factorization is O(nm3). As we will analyze laser, generalized power method converges linearly, and setting δmax = 1/n provides a sufficiently accurate estimation of the leading eigenvectors. So the total time complexity of the Generalized power method is O (n Em2 + nm3 log(n)). The time complexity of the rounding step is O(nm3). In summary, the total complexity of Norm Spec Sync is O (n Em2 + nm3 log(n)). In comparison, the complexity of the SDP formulation [9], even when it is solved using the fast ADMM method (alternating direction of multiplier method), is at least O(n3m3nadmm. So Norm Spec Sync exhibits significant speedups when compared to SDP formulations.

In this section, we provide an analysis of Norm Spec Sync under a generalized Erd os-Rényi noise model.

3.1 Noise Model

The noise model we consider is given by two parameters m and p. Specifically, we assume the observation graph G is fixed. Then independently for each edge (i, j) E,

Xin ij = Im with probability p Pij with probability 1 p (4)

where Pij Pm is a random permutation. Remark 2. The noise model described above assumes the underlying permutations are identity maps. In fact, one can assume a generalized noise model

Xin ij = XT j1Xi1 with probability p Pij with probability 1 p

where Xi1, 1 i n are pre-defined underlying permutations from object Si to the first object S1. However, since Pij are independent of Xi1. It turns out the model described above is equivalent to

Xj1Xin ij XT i1 = Im with probability p Pij with probability 1 p

Where Pij are independent random permutations. This means it is sufficient to consider the model described in (4). Remark 3. The fundamental difference between our model and the one proposed in [11] or the ones used in low-rank matrix recovery [18] is that the observation pattern (i.e., G) is fixed, while in other models it also follows a random model. We argue that our assumption is more practical because the observation graph is constructed by comparing object descriptors and it is dependent on the distribution of the input objects. On the other hand, fixing G significantly complicates the analysis of Norm Spec Sync, which is the main contribution of this paper.

3.2 Main Theorem

Now we state the main result of the paper.

Theorem 3.1. Let dmin := min1 i n di, davg := P i di/n, and denote ρ as the second top eigenvalue of normalized adjacency matrix of G. Assume dmin = Ω( n ln3 n), davg = O(dmin), ρ < min{p, 1/2}. Then under the noise model described above, Norm Spec Sync recovers the underlying pair-wise maps with high probability if

p > C ln3 n dmin/ n, (5)

for some constant C.

Proof Roadmap. The proof of Theorem 3.1 combines two stability bounds. The first one considers the projection step:

Proposition 3.1. Consider a permutation matrix X = (xij) Pm and another matrix X = (xij) Rm m. If X X < 1

2, then X = arg min Y Pm Y X 2 F .

Proof. The proof is quite straight-forward. In fact,

X X X X < 1

Varying graph density

Graph density

0.1 0.3 0.5 0.7 0.9

Varying graph density

Graph density 0.1 0.3 0.5 0.7 0.9

Varying graph density

Graph density

0.1 0.3 0.5 0.7 0.9

(a) Norm Spec Sync (2.25 seconds) (b) SDP (203.12 seconds) (c) Diff Sync(1.07 seconds)

Figure 1: Comparisons between Norm Spec Sync, SDP[9], Diff Sync[13] on the noise model described in Sec. 2.

This means the corresponding element xij of each non-zero element in xij is dominant in its row and column, i.e., xij = 0 xij > max(max k =j xik, max k =i xkj),

which ends the proof.

The second bound concerns the block-wise stability of the leading eigenvectors of Xobs:

Lemma 3.1. Under the assumption of Theorem 3.1, then w.h.p.,

Pn i=1 di did1 (WW T )i1 Im

3, 1 i n. (6)

It is easy to see that we can prove Theorem 3.1 by combing Lemma 3.1 and Prop. 3.1. Yet unlike Prop. 3.1, the proof of Lemma 3.1 is much harder. The major difficulty is that (6) requires controlling each block of the leading eigenvectors, namely, it requires a L bound, whereas most stability results on eigenvectors are based on the L2-norm. Due to space constraint, we defer the proof of Lemma 3.1 to Appendix A and the supplemental material.

Near-optimality of Norm Spec Sync. Theorem 3.1 implies that Norm Spec Sync is near-optimal with respect to the information theoretical bound described in [19]. In fact, when G is a clique, (5) becomes p > C ln3(n) n , which aligns with the lower bound in [19] up to a polylogarithmic factor. Following the model described in [19], we can also assume that the observation graph G is sampled with a density factor q, namely, two objects are connected independently with probability q. In this case, it is easy to see that dmin > O(nq/ ln n) w.h.p., and (5) becomes p > C ln4 n nq . This bound also stays within a polylogarithmic factor from the lower bound in [19], indicating the near-optimality of Norm Spec Sync.

4 Experiments

In this section, we perform quantitative evaluations of Norm Spec Sync on both synthetic and real examples. Experimental results show that Norm Spec Sync is superior to state-of-the-art map synchronization methods in the literature. We organize the remainder of this section as follows. In Section 4.1, we evaluate Norm Spec Sync on synthetic examples. Then in section 4.2, we evaluate Norm Spec Sync on real examples.

4.1 Quantitative Evaluations on Synthetic Examples

We generate synthetic data by following the same procedure described in Section 2. Specifically, each synthetic example is controlled by three parameters G, m, and p. Here G specifies the input graph; m describes the size of each permutation matrix; p controls the noise level of the input maps. The input maps follow a generalized Erdos-Renyi model, i.e., independently for each edge (i, j) G in the input graph, with probability p the input map Xin ij = Im, and otherwise Xin ij is a random permutation. To simplify the discussion, we fix m = 10, n = 200 and vary the observation graph G and p to evaluate Norm Spec Sync and existing algorithms.

Varying vertex degrees

Irregularty

0.0 0.1 0.2 0.3 0.4

Varying vertex degrees

Irregularty

0.0 0.1 0.2 0.3 0.4

(a) Norm Spec Sync (b) Spec Sync

Figure 2: Comparison between Nor Spec Sync and Spec Sync on irregular observation graphs.

Dense graph versus sparse graph. We first study the performance of Norm Spec Sync with respect to the density of the graph. In this experiment, we control the density of G by following a standard Erd os-Rényi model with parameter q, namely independently, each edge is connected with probability q. For each pair of fixed p and q, we generate 10 examples. We then apply Norm Spec Sync and count the ratio that the underlying permutations are recovered. Figure 1(a) illustrates the success rate of Norm Spec Sync on a grid of samples for p and q. Blue and yellow colors indicate it succeeded and failed on all the examples, respectively, and the colors in between indicate a mixture of success and failure. We can see that Norm Spec Sync tolerates more noise when the graph becomes denser. This aligns with our theoretical analysis result.

Norm Spec Sync versus Spec Sync. We also compare Norm Spec Sync with Spec Sync [12], and show the advantage of Norm Spec Sync on irregular observation graphs. To this end, we generate G using a different model. Specifically, we let the degree of the vertex to be uniformly distribute between ( 1

2 q)n and ( 1

2 + q)n. As illustrated in Figure 2, when q is small, i.e., all the vertices have similar degrees, the performance of Norm Spec Sync and Spec Sync are similar. When q is large, i.e., G is irregular, Norm Spec Sync tend to tolerate more noise than Spec Sync. This shows the advantage of utilizing a normalized data matrix.

Norm Spec Sync versus Diff Sync. We proceed to compare Norm Spec Sync with Diff Sync [13], which is a permutation synchronization method based on diffusion distances. Norm Spec Sync and Diff Sync exhibit similar computation efficiency. However, Norm Spec Sync can tolerate significantly more noise than Diff Sync, as illustrated in Figure 1(c).

Norm Spec Sync versus SDP. Finally, we compare Norm Spec Sync with SDP [9], which formulates permutation synchronization as solving a semidefinite program. As illustrated in Figure 1(b), the exact recovery ability of Norm Spec Sync and SDP are similar. This aligns with our theoretical analysis result, which shows the near-optimality of Norm Spec Sync under the noise model of consideration. Yet computationally, Norm Spec Sync is much more efficient than SDP. The averaged running time for Spec Sync is 2.25 second. In contrast, SDP takes 203.12 seconds in average.

4.2 Quantitative Evaluations on Real Examples

In this section, we present quantitative evaluation of Norm Spec Sync on real datasets.

CMU Hotel/House. We first evaluate Norm Spec Sync on CMU Hotel and CMU House datasets [20]. The CMU Hotel dataset contains 110 images, where each image has 30 marked feature points. In our experiment, we estimate the initial map between a pair of images using RANSAC [21]. We consider two observation graphs: a clique observation graph Gfull, where we have initial maps computed between all pairs of images, and a sparse observation graph Gsparse. Gsparse is constructed to only connect similar images. In this experiment, we connect an edge between two images if the difference in their HOG descriptors [22] is smaller than 1

2 of the average descriptor differences among all pairs of images. Note that Gsparse shows high variance in terms of vertex

Euclidean distance (pixels)

0 1 2 3 4 5 6

% correspondences

100 CMU-G-Full

RANSAC Diff Sync Spec Sync Non Spec Sync SDP

Euclidean distance (pixels)

0 1 2 3 4 5 6

% correspondences

100 CMU-G-Sparse

RANSAC Diff Sync Spec Sync Non Spec Sync SDP

Geodesic distance (diameter)

0 0.05 0.1 0.15 0.2

% correspondences

100 SCAPE-G-Full

RANSAC Diff Sync Spec Sync Non Spec Sync SDP

Geodesic distance (diameter)

0 0.05 0.1 0.15 0.2

% correspondences

100 SCAPE-G-Sparse

RANSAC Diff Sync Spec Sync Non Spec Sync SDP

Figure 3: Comparison between Nor Spec Sync, Spec Sync, Diff Sync and SDP on CMU Hotel/House and SCAPE. In each dataset, we consider a full observation graph and a sparse observation graph that only connects potentially similar objects.

degree. The CMU House dataset is similar to CMU Hotel, containing 100 images and exhibiting slightly bigger intra-cluster variability than CMU Hotel. We construct the observation graphs and the initial maps in a similar fashion. For quantitative evaluation, we measure the cumulative distribution of distances between the predicted target points and the ground-truth target points.

Figure 3(Left) compares Norm Spec Sync with the SDP formulation, Spec Sync, and Diff Sync. On both full and sparse observation graphs, we can see that Norm Spec Sync, SDP and Spec Sync are superior to Diff Sync. The performance of Norm Spec Sync and Spec Sync on Gfull is similar, while on Gsparse, Norm Spec Sync shows a slight advantage, due to its ability to handle irregular graphs. Moreover, although the performance of Norm Spec Sync and SDP are similar, SDP is much slower than Norm Spec Sync. For example, on Gsparse, SDP took 1002.4 seconds, while Norm Spec Sync only took 3.4 seconds.

SCAPE. Next we evaluate Norm Spec Sync on the SCAPE dataset. SCAPE consists of 71 different poses of a human subject. We uniformly sample 128 points on each model. Again we consider a full observation graph Gfull and a sparse observation graph Gsparse. Gsparse is constructed in the same way as above, except we use the shape context descriptor [4] for measuring the similarity between 3D models. In addition, the initial maps are computed from blended-intrinsic-map [16], which is the state-of-the-art technique for computing dense correspondences between organic shapes. For quantitative evaluation, we measure the cumulative distribution of geodesic distances between the predicted target points and the ground-truth target points. As illustrated in Figure 3(Right), the relative performance between Norm Spec Sync and the other three algorithms is similar to CMU Hotel and CMU House. In particular, Norm Spec Sync shows an advantage over Spec Sync on Gsparse. Yet in terms of computational efficiency, Norm Spec Sync is far better than SDP.

5 Conclusions In this paper, we propose an efficient algorithm named Norm Spec Sync towards solving the permutation synchronization problem. The algorithm adopts a spectral view of the mapping problem and exhibits surprising behavior both in terms of computation complexity and exact recovery conditions. The theoretical result improves upon existing methods from several aspects, including a fixed obser-

vation graph and a practical noise method. Experimental results demonstrate the usefulness of the proposed approach.

There are multiple opportunities for future research. For example, we would like to extend Norm Spec Sync to handle the case where input objects only partially overlap with each other. In this scenario, developing and analyzing suitable rounding procedures become subtle. Another example is to extend Norm Spec Sync for rotation synchronization, e.g., by applying Spectral decomposition and rounding in an iterative manner.

Acknowledgement. We would like to thank the anonymous reviewers for detailed comments on how to improve the paper. The authors would like to thank the support of DMS-1700234, CCF-1302435, CCF-1320175, CCF-1564000, CNS-0954059, IIS-1302662, and IIS-1546500.

A Proof Architecture of Lemma 3.1

In this section, we provide a roadmap for the proof of Lemma 3.1. The detailed proofs are deferred to the supplemental material.

Reformulate the observation matrix. The normalized adjacency matrix A = D 1

2 can be decomposed as A = ss T + V ΛV T , where the dominant eigenvalue is 1 and corresponding eigenvector is s. We reformulate the observation matrix as 1

p M = A Im + N, and it is clear to see that the ground truth result relates to the term (ss T ) Im, while the noise comes from two terms: (V ΛV T ) Im and N. More specifically, the noise not only comes from the randomness of uncertainty of the measurements, but also from the graph structure, and we use ρ to represent the spectral norm of Λ. When the graph is disconnected or near disconnected, ρ is close to 1 and it is impossible to recover the ground truth.

Bound the spectral norm of N. The noise term N consists of random matrices with mean zero in each block. In a complete graph, the spectral norm is bounded by O( 1 p n), however, when considering the graph structure, we give a O( 1 p dmin ) bound.

Measure the block-wise distance between U and s Im. Let M = UΣU T + U2Σ2U T 2 , we want to show the distance between U and s 1m is small, where the distance function dist( ) is defined as: dist(U, V ) = min R:RRT =I

U V R B, (7)

and this B norm for any matrix X represented in the form X = [XT 1 , , XT n ]T Rmn m is defined as X B = max i Xi F . (8)

More specifically, we bound the distance between U and s Im by constructing a series of matrix {Ak}, and we can show for some k = O(log n), the distances from s Ak to both U and s Im are small. Therefore, by using the triangle inequality, we can show that U and s Im is close.

Sketch proof of Lemma 3.1. Once we are able to show that there exists some rotation matrix R, such that dist(U, s Im) is in the order of o( 1 n), then it is straightforward to prove Lemma 3.1. Intuitively, this is because the measurements from the eigenvectors is close enough to the ground truth, hence their second moment will still be close. Formally speaking, Ui U T j (si Im)(sj Im) (9)

= Ui RRT U T j (si Im)(sj Im) (10)

= Ui R(RT U T j (sj Im)T ) + (Ui R si Im)(sj Im)T (11)

Ui dist(U, s Im) + dist(U, s Im) sj Im (12) On the other hand, notice that Pn i=1 di p

didj Ui U T j Im = Pn i=1 di p

Ui U T j (si Im)(sj Im) , (13)

and we only need to show that (13) is in the order of o(1). The details are included in the supplemental material.

[1] D. F. Huber, Automatic three-dimensional modeling from reality, Tech. Rep., 2002.

[2] D. Crandall, A. Owens, N. Snavely, and D. Huttenlocher, Discrete-continuous optimization for large-scale structure from motion, in IEEE Conference on Computer Vision and Pattern Recognition (CVPR), 2011, pp. 3001 3008.

[3] Q.-X. Huang, S. Flöry, N. Gelfand, M. Hofer, and H. Pottmann, Reassembling fractured objects by geometric matching, in ACM SIGGRAPH 2006 Papers, 2006, pp. 569 578.

[4] V. G. Kim, W. Li, N. Mitra, S. Di Verdi, and T. Funkhouser, Exploring collections of 3D models using fuzzy correspondences, Transactions on Graphics (Proc. of SIGGRAPH 2012), vol. 31, no. 4, Aug. 2012.

[5] W. Marande and G. Burger, Mitochondrial dna as a genomic jigsaw puzzle, Science, vol. 318, Jul. 2007.

[6] C. Zach, M. Klopschitz, and M. Pollefeys, Disambiguating visual relations using loop constraints. in IEEE Conference on Computer Vision and Pattern Recognition (CVPR), 2010, pp. 1426 1433.

[7] D. Crandall, A. Owens, N. Snavely, and D. Huttenlocher, Discrete-continuous optimization for large-scale structure from motion, in IEEE Conference on Computer Vision and Pattern Recognition (CVPR). IEEE, 2011, pp. 3001 3008.

[8] A. Nguyen, M. Ben-Chen, K. Welnicka, Y. Ye, and L. Guibas, An optimization approach to improving collections of shape maps, in Eurographics Symposium on Geometry Processing (SGP), 2011, pp. 1481 1491.

[9] Q. Huang and L. Guibas, Consistent shape maps via semidefinite programming, Computer Graphics Forum, Proc. Eurographics Symposium on Geometry Processing (SGP), vol. 32, no. 5, pp. 177 186, 2013.

[10] L. Wang and A. Singer, Exact and stable recovery of rotations for robust synchronization, Co RR, vol. abs/1211.2441, 2012.

[11] Y. Chen, L. J. Guibas, and Q. Huang, Near-optimal joint object matching via convex relaxation, 2014. [Online]. Available: http://arxiv.org/abs/1402.1473

[12] D. Pachauri, R. Kondor, and V. Singh, Solving the multi-way matching problem by permutation synchronization, in Advances in Neural Information Processing Systems, 2013, pp. 1860 1868.

[13] D. Pachauri, R. Kondor, G. Sargur, and V. Singh, Permutation diffusion maps (pdm) with application to the image association problem in computer vision, in Advances in Neural Information Processing Systems, 2014, pp. 541 549.

[14] N. Dalal and B. Triggs, Histograms of oriented gradients for human detection, in Proceedings of the 2005 IEEE Computer Society Conference on Computer Vision and Pattern Recognition (CVPR 05) - Volume 1 - Volume 01, ser. CVPR 05, 2005, pp. 886 893.

[15] C. Liu, J. Yuen, A. Torralba, J. Sivic, and W. T. Freeman, Sift flow: Dense correspondence across different scenes, in Proceedings of the 10th European Conference on Computer Vision: Part III, ser. ECCV 08, 2008, pp. 28 42.

[16] V. G. Kim, Y. Lipman, and T. Funkhouser, Blended intrinsic maps, in ACM Transactions on Graphics (TOG), vol. 30, no. 4. ACM, 2011, p. 79.

[17] R. Burkard, M. Dell Amico, and S. Martello, Assignment Problems. Philadelphia, PA, USA: Society for Industrial and Applied Mathematics, 2009.

[18] E. J. Candès, X. Li, Y. Ma, and J. Wright, Robust principal component analysis? J. ACM, vol. 58, no. 3, pp. 11:1 11:37, Jun. 2011. [Online]. Available: http://doi.acm.org/10.1145/1970392.1970395

[19] Y. Chen, C. Suh, and A. J. Goldsmith, Information recovery from pairwise measurements: A shannontheoretic approach, Co RR, vol. abs/1504.01369, 2015.

[20] T. S. Caetano, L. Cheng, Q. V. Le, and A. J. Smola, Learning graph matching, in Computer Vision, 2007. ICCV 2007. IEEE 11th International Conference on. IEEE, 2007, pp. 1 8.

[21] M. A. Fischler and R. C. Bolles, Random sample consensus: A paradigm for model fitting with applications to image analysis and automated cartography, Commun. ACM, vol. 24, no. 6, pp. 381 395, Jun. 1981.

[22] R. Osada, T. Funkhouser, B. Chazelle, and D. Dobkin, ACM Trans. Graph., vol. 21, no. 4, pp. 807 832, 2002.