*********************************
There is now a CONTENT FREEZE for Mercury while we switch to a new platform. It began on Friday, March 10 at 6pm and will end on Wednesday, March 15 at noon. No new content can be created during this time, but all material in the system as of the beginning of the freeze will be migrated to the new platform, including users and groups. Functionally the new site is identical to the old one. webteam@gatech.edu
*********************************
Speaker: Yuxin Chen
Title:
Near-Optimal Joint Object Matching via Convex Relaxation
Abstract:
Joint object / graph matching is a fundamental scientific problem -- given a collection of (partially) similar objects drawn from the same universe, we wish to recover globally compatible mapping over them. This is a central task spanning a wide spectrum of scientific problems, including structure from motion, re-assembling fragmented objects, solving jigsaw puzzles, fusing partially overlapped Kinect scans, to name just a few. One popular approach is to perform pairwise matching between each object pair, and then exploit information from all pairwise maps computed in isolation to assist in global matching. Unfortunately, global refinement of noisy pairwise maps is computationally prohibitive in general.
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.
Speaker Bio:
Yuxin Chen is a Ph.D. candidate in the Department of Electrical Engineering at Stanford University, under supervision of Prof. Andrea Goldsmith. He has received the M.S. in statistics from Stanford University in 2013, the M.S. in electrical and computer engineering from the University of Texas at Austin in 2010, and the B.S. in microelectronics with high distinction from Tsinghua University in 2008. His research interests include high-dimensional statistics, information theory, convex analysis, statistical learning, and network science.
