Title: Non-convex Analysis of Multi-Graph Matching
Abstract: We propose an iterative algorithm together with its theoretical analysis for the Multi-Graph Matching (MGM) problem. The latter problem assumes a set of graphs, each of which have the same number of vertices and further assumes that for each pair of graphs there exists a one-to-one correspondence map between their vertices. Given only noisy measurements of the mutual correspondences, the MGM problem asks to recover the correspondence maps between pairs of them. Our proposed algorithm iteratively solves the non-convex optimization problem associated with the MGM problem. We prove that for specific noise model, if the initial point of our proposed iterative algorithm is good enough, the algorithm linearly converges to the unique solution. Furthermore, we show how to find such an initial point. Numerical experiments demonstrate that our method is much faster and more accurate than the state-of-the-art methods.