Timezone: »
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.
Author Information
Bo Jiang (Anhui University)
Jin Tang
Chris Ding (University of Texas at Arlington)
Yihong Gong
Bin Luo
Related Events (a corresponding poster, oral, or spotlight)
-
2017 Spotlight: Graph Matching via Multiplicative Update Algorithm »
Wed. Dec 6th 01:45 -- 01:50 AM Room Hall A
More from the Same Authors
-
2014 Poster: Exclusive Feature Learning on Arbitrary Structures via $\ell_{1,2}$-norm »
Deguang Kong · Ryohei Fujimaki · Ji Liu · Feiping Nie · Chris Ding -
2012 Poster: Selective Labeling via Error Bound Minimization »
Quanquan Gu · Tong Zhang · Chris Ding · Jiawei Han -
2012 Poster: Forging The Graphs: A Low Rank and Positive Semidefinite Graph Learning Approach »
Dijun Luo · Chris Ding · Heng Huang -
2011 Poster: A Maximum Margin Multi-Instance Learning Framework for Image Categorization »
Hua Wang · Heng Huang · Farhad Kamangar · Feiping Nie · Chris Ding -
2010 Poster: Efficient and Robust Feature Selection via Joint ℓ2,1-Norms Minimization »
Feiping Nie · Heng Huang · Xiao Cai · Chris Ding