Timezone: »

Graph Matching via Multiplicative Update Algorithm
Bo Jiang · Jin Tang · Chris Ding · Yihong Gong · Bin Luo

Tue Dec 05 06:30 PM -- 10:30 PM (PST) @ Pacific Ballroom #98

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)

More from the Same Authors