Near-Optimal Joint Object Matching via Convex Relaxation
Tuesday, April 1, 2014
12:00 pm - 1:00 pm
Gross Hall 330
Yuxin Chen Electrical Engineering, Stanford University
lunch/talk at noon This talk delivers some encouraging news by transforming this NP-hard combinatorial problem into tractable convex programs. Our approach is inspired by the success of matrix completion and robust PCA, and builds upon a low-rank matrix representation of the global consistency criterion. Specifically, we propose to recover the ground-truth maps via a parameter-free convex program called MatchLift, following a spectral method that pre-estimates the total number of distinct elements to be matched. Encouragingly, MatchLift exhibits near-optimal error-correction ability, i.e. in the high-dimensional regime it is guaranteed to work even when a dominant fraction $1¿¿(1 / \sqrt(n))$ of the input maps behave like random outliers. The algorithm and results are well suited for the scenario when the collection of objects exhibit only partial similarity to each other. Furthermore, MatchLift succeeds with minimal input complexity, namely, perfect matching can be achieved as soon as the provided pairwise maps form a connected map graph. On the practical side, we evaluate the proposed algorithm on various benchmark data sets including synthetic examples and real-world examples, all of which confirm the practical applicability of MatchLift.