Initialization and Coordinate Optimization for Multi-way Matching
  We consider the problem of consistently matching multiple sets of elements to
each other, which is a common task in fields such as computer vision. To solve
the underlying NP-hard objective, existing methods often relax or approximate
it, but end up with unsatisfying empirical performance due to a misaligned
objective. We propose a coordinate update algorithm that directly optimizes the
target objective. By using pairwise alignment information to build an
undirected graph and initializing the permutation matrices along the edges of
its Maximum Spanning Tree, our algorithm successfully avoids bad local optima.
Theoretically, with high probability our algorithm guarantees an optimal
solution under reasonable noise assumptions. Empirically, our algorithm
consistently and significantly outperforms existing methods on several
benchmark tasks on real datasets.
