In this paper we formulate multi-target tracking
(MTT) as a high-order graph matching problem and propose a l1-norm tensor power iteration solution. Concretely, the search for trajectory-observation correspondences in MTT task is casted as a hypergraph matching problem to maximize a multilinear objective function over all permutations of the associations. This function is defined by a tensor representing the affinity between association tuples where pair-wise similarities, motion consistency and spatial structural information can be embedded expediently. To solve the matching problem, a dual-direction unit l1-norm constrained tensor power iteration algorithm is proposed. Additionally, as measuring the appearance affinity with features extracted from the rectangle patch, which is adopted in most methods, has a weak discrimination when bounding boxes overlap each other heavily, we present a deep pair-wise appearance similarity metric based on object mask in this paper where just the features from true target region are utilized. Experimental evaluation shows that our approach achieves an accuracy comparable to state-of-the-art online trackers1. Our code will be made available soon.