Initialization and Coordinate Optimization for Multi-way Matching
This addresses the problem of multi-way matching for applications like computer vision, offering improved performance over existing methods, though it appears incremental as it builds on prior optimization approaches.
The paper tackles the NP-hard problem of consistently matching multiple sets of elements by proposing a coordinate update algorithm that directly optimizes the target objective, using pairwise alignment to build a graph and initializing along its Maximum Spanning Tree to avoid bad local optima. Theoretically, it guarantees an optimal solution with high probability under noise assumptions, and empirically, it consistently and significantly outperforms existing methods on real benchmark datasets.
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.