Solving the multi-way matching problem by permutation synchronization
The problem of matching not just two, but m different sets of objects to each other arises in many contexts, including finding the correspondence between feature points across multiple images in computer vision. At present it is usually solved by matching the sets pairwise, in series. In contrast, we propose a new method, Permutation Synchronization, which finds all the matchings jointly, in one shot, via a relaxation to eigenvector decomposition. The resulting algorithm is both computationally efficient, and, as we demonstrate with theoretical arguments as well as experimental results, much more stable to noise than previous methods.
* Summary This manuscript studies a 
      combinatorial optimization problem that is motivated by a number of 
      applications within the scope of NIPS. It is defined w.r.t. a finite 
      number of finite sets, all of the same cardinality. A feasible solution 
      consists in as many bijections as there are pairs of distinct sets. These 
      bijections are constrained to be consistent in the following sense: For 
      any three sets, A, B, C, if "a" in A is mapped to b in B and b in B is 
      mapped to c in C, then "a" needs to be mapped to c. The objective function 
      is defined w.r.t. so-called "tentative (noisy)" matchings. Instead of 
      solving this combinatorial problem, a relaxation is proposed that can be 
      solved efficiently, by computing leading eigenvectors of a matrix. The 
      solution of the relaxed problem is shown to be robust to noise and also 
      accurate compared to ground truth in a number of practical applications. 
      * Strengths - The manuscript addresses a relevant 
      combinatorial optimization problem that has several applications within 
      the scope of NIPS. - The proposed relaxation of this problem is 
      interesting and original. - The experimental results suggest that the 
      relaxation may be tight in practice. * Weaknesses - A 
      relaxation of an integer program is proposed but not put into perspective. 
      Is it tighter than simpler relaxations? How does it compare to the optimal 
      solution of small problems that can be solved exactly? Is there a 
      guaranteed bound? - The writing can be improved. In its present 
      form, the objective function is not easy to understand because the 
      notation is convoluted. In order to understand (3), one needs to expand 
      the definitions of d, p, tau, and the inner product. As an alternative, I 
      suggest that the problem should be written as an integer program that is 
      easy to grasp, perhaps in addition to the present formulation. The 
      readability of Section 2 can be improved. I suggest that the permutations 
      sigma should be defined before the matchings tau and before stating that 
      any set of sigmas induces a set of consistent taus. The structure 
      of Section 3 can be improved. Statements should be made first informally, 
      then formally, e.g. as lemmata, and then proved. * Technical 
      questions - I do not understand the introduction of "tentative 
      (noisy)" matchings in the objective function. After reading the 
      introduction, I would have expected a formulation in terms of weights, 
      positive or negative, one for any possible match (between any two elements 
      of any two distinct sets). Is the objective function (3) a special case of 
      such a general formulation? I think the manuscript can be improved by 
      starting with the general formulation and then specializing this 
      formulation to the problem under consideration. - Can the 
      combinatorial problem not be solved to optimality by means of a 
      state-of-the-art branch-and-cut solver, at least in applications where the 
      number of elements to be matched is small? If it can be solved to 
      optimality, a comparison of run-times as well as an assessment of the 
      relaxation gap would be interesting. * Minor remarks - All 
      equations should be numbered.