A quadratic penalty method for hypergraph matching

Chunfeng Cui, Qingna Li, Liqun Qi, Hong Yan

Research output: Journal article publicationJournal articleAcademic researchpeer-review

3 Citations (Scopus)

Abstract

Hypergraph matching is a fundamental problem in computer vision. Mathematically, it maximizes a polynomial objective function, subject to assignment constraints. In this paper, we reformulate the hypergraph matching problem as a sparse constrained optimization problem. By dropping the sparse constraint, we show that the resulting relaxation problem can recover the global minimizer of the original problem. This property heavily depends on the special structures of hypergraph matching. The critical step in solving the original problem is to identify the location of nonzero entries (referred to as the support set) in a global minimizer. Inspired by such observation, we apply the quadratic penalty method to solve the relaxation problem. Under reasonable assumptions, we show that the support set of the global minimizer in a 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 the support set indeed happens, and the proposed algorithm is efficient in terms of both accuracy and CPU time.
Original languageEnglish
Pages (from-to)237-259
Number of pages23
JournalJournal of Global Optimization
Volume70
Issue number1
DOIs
Publication statusPublished - 1 Jan 2018

Keywords

  • Hypergraph matching
  • Projected gradient method
  • Quadratic penalty method
  • Sparse optimization

ASJC Scopus subject areas

  • Computer Science Applications
  • Control and Optimization
  • Management Science and Operations Research
  • Applied Mathematics

Cite this