Please use this identifier to cite or link to this item: http://hdl.handle.net/10397/74155
Title: A quadratic penalty method for hypergraph matching
Authors: Cui, C
Li, Q
Qi, L 
Yan, H
Keywords: Hypergraph matching
Projected gradient method
Quadratic penalty method
Sparse optimization
Issue Date: 2018
Publisher: Springer
Source: Journal of global optimization, 2018, v. 70, no. 1, p. 237-259 How to cite?
Journal: Journal of global optimization 
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.
URI: http://hdl.handle.net/10397/74155
ISSN: 0925-5001
EISSN: 1573-2916
DOI: 10.1007/s10898-017-0583-0
Appears in Collections:Journal/Magazine Article

Access
View full-text via PolyU eLinks SFX Query
Show full item record

Page view(s)

89
Citations as of Nov 20, 2019

Google ScholarTM

Check

Altmetric


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.