  Hypergraph matching is a fundamental problem in computer vision.
Mathematically speaking, it maximizes a polynomial objective function, subject
to assignment constraints. In this paper, we reformulate the hypergraph
matching problem as a sparse constrained tensor optimization problem. The
optimality conditions are characterized based on the sparse constrained
optimization theory. By dropping the sparsity constraint, 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. 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. A projected gradient method is applied as a subsolver to
solve the quadratic penalty subproblem. Numerical results demonstrate that the
exact recovery of support set indeed happens, and the proposed algorithms are
efficient in terms of both accuracy and speed.
