An efficient algorithm for bounded spectral matching with affine constraint

摘要

Graph matching problem appears frequently in the applications of computer vision and machine learning. In this work, based on the spectral matching with affine constraint (SMAC) formulation, we present a new formulation, named bounded SMAC (BSMAC), for the graph matching problem by adding an upper-bound constraint on the solution norm. We demonstrate the existence of a unique solution with BSMAC, whereas SMAC needs not to have any meaningful solution in general. We develop an effective numerical method to solve the BSMAC formulation as an optimization problem. Numerical experiments are presented to verify feasibility and to show the performance of the proposed numerical method.