Graph Matching via Multiplicative Update Algorithm

As a fundamental problem in computer vision, graph matching problem can usually be formulated as a Quadratic Programming (QP) problem with doubly stochastic and discrete (integer) constraints. Since it is NP-hard, approximate algorithms are required. In this paper, we present a new algorithm, called Multiplicative Update Graph Matching (MPGM), that develops a multiplicative update technique to solve the QP matching problem. MPGM has three main benefits: (1) theoretically, MPGM solves the general QP problem with doubly stochastic constraint naturally whose convergence and KKT optimality are guaranteed. (2) Em- pirically, MPGM generally returns a sparse solution and thus can also incorporate the discrete constraint approximately. (3) It is efficient and simple to implement. Experimental results show the benefits of MPGM algorithm.

Authors

• Bo Jiang Didi Chuxing
• Jin Tang Anhui University
• Chris Ding The School of Data Science, The Chinese University of Hong Kong, Shenzhen (CUHK-Shenzhen), China
• Yihong Gong Xi'an Jiaotong University Shenzhen University of Advanced Technology
• Bin Luo Key Laboratory of Intelligent Computing and Signal Processing of Ministry of Education, Anhui Provincial Key Laboratory of Multimodal Cognitive Computation, School of Computer Science and Technology, Anhui University, China

Keywords

No keywords are indexed for this paper.