Hypergraph matching is a fundamental problem in computer vision.
Mathematically speaking, it maximizes a polynomial objective function, subject to assignment constraints. Existing methods generally solve the relaxation problem, however, there is no theoretical analysis on the relation of the relaxation problem and the original problem. In this talk, we show that the resulting relaxation problem can recover the global minimizer of the original problem. The critical step in solving the original problem is to identify the location of nonzero entries (referred as support set) in a global minimizer. Inspired by such observations, we penalize the equality constraints and apply the quadratic penalty method to solve the relaxation problem. This is the second contribution of our talk. Under reasonable assumptions, we show that the support set of the global minimizer in hypergraph matching problem can be correctly identified when the number of iterations is sufficiently large. This can be viewed as the exact penalty in terms of support set. Numerical results demonstrate that the exact recovery of support set indeed happens, and the proposed algorithm is efficient in terms of both accuracy and speed. This is a joint work with C.F. Cui, L.Q. Qi and H. Yan.