Normalized Spectral Map Synchronization
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 NormSpecSync) that projects the blocks of the top eigenvectors of a data matrix to the map space, exhibits surprisingly good behavior -NormSpecSync is much more efficient than state-of-the-art convex optimization techniques, yet still admitting similar exact recovery conditions. We demonstrate the usefulness of NormSpecSync on both synthetic and real datasets.
This paper concentrates on a normalized spectral technique for solving the joint shape mapping / synchronization problem.  It provides a theory towards understanding the performance guarantees of the spectral technique.  It was claimed by the authors that the spectral technique achieves nearly equivalent performance as SDP,  while enjoying much lower computational complexity.  Extensive numerical simulations have been carried out to verify the theoretical findings.   Overall speaking, spectral technique is definitely a very interesting and efficient paradigm for this joint mapping problem, and hence an attempt to provide rigorous theoretical justification is a very timely and valuable contribution to this field.   One of my concerns is that the key sufficient recovery condition (11) is not very easy to interpret,  and does not seem to match the prior results well (but I could be wrong).  The authors might want to provide more detailed explanation about (11),  ideally specializing it to several concrete examples and then comparing each of them with prior results.  
1.  The observation matrix X_obs is approximately low-rank as well without normalization.  What is the advantage of "normalized" spectral method compared to "unnormalized" spectral method?   2.  For the benefits of those not familiar with this subject,  it would be good to provide a simple yet concrete example to explain X_{ij}.    3.  Define \otimes (Kronecker product) in Equation (2).   4. 3rd paragraph of Section 2.1:   {d_i} should be formally defined.  What if some d_i = 0?   5. I think in the initialization stage of Algorithm 1, it suffices to say "compute the first few eigenvectors of M using a block power method" (and perhaps provide some reference for the block power method).  There is no need to write out all details for the power method as this is fairly standard.   6.  For the projection step (i.e.the sentence after Equation (3)):  please either explain in detail how to compute it by solving a block-wise linear assignment or cite an appropriate reference, if any.   7.  Last sentence of the "Complexity" paragraph in Page 3: For concreteness, the authors might want to mention that full SVD takes time O(n^3) in order to make it more concrete.   8.  Equation (5):  P_ij has not been formally defined.   9.  The authors might need to state explicitly that {X_ij} are independently generated.  10.  It is not completely clear to me what Equation (7) means; please define s, V, Lambda more precisely.   11.  The notation seems to be inconsistent from here to there. For instance, In Algorithm 1, it says computing the first n eigenvectors, while in the last paragraph of Section 2.3, it says top-m eigenvectors. Please correct the inconsistency.   12.  Condition (11), which is perhaps the most important condition herein, is not easy to interpret at least to me.  Can the authors specialize it to some simple case (e.g. when the noise is a uniformly random permutation), and then provide a condition in terms of the parameters p, m, and n rather than rho and || N ||?    13.  In fact, I'm not sure I understand (11) correctly.  The author says rho is the spectral norm of \overline{A},  which is the normalized adjacency matrix of G.  Why can we "interpret rho as the noise from the adjacency graph"?  The noise is usually thought of as the variance term; what about the mean component?  14.  On the other hand, suppose G is a complete graph, then it seems that the adjacency graph is very close to an all-one matrix, and hence  \overline{A}  is close to  1/n* ones(n,n), and hence rho is almost 1.  In this case, what happens to the second condition of (11) if p is bounded away from 1?   In prior results, however,  G being a complete graph is actually the easiest case, in the sense it can tolerate the largest possible noise (or smallest possible p which is much smaller than 1).   15.  In Lemma 3.2, the last sentence reads strange, as "Show that" sounds like an exercise rather than a result.  Also, you might want to define "converges linearly" somewhere,  as there could be two different interpretation (i.e. geometric convergence rate vs. a convergence rate of O(1/t) ) depending on whether the readers are from the optimization society or not.   16. Typos and minor things:  (1) Abstract:  "as random permutation matrix" --> "as a random ..." (2) Abstract:  "this algorithm NormSpecSync" --> "the proposed NormSpecSync algorithm" (3) 2nd paragraph:  "leads remarkable denoising ability" --> "leads to ..." (4) 2nd paragraph:  "then find the top eigenvectors" --> "then finds the top eigenvectors";  "project each block" --> "projects each block" (5) 3rd paragraph:  "have been considered" --> "has been considered" (6) Section 2.1:  "need not obey the consistency property" --> "needs not ..."