Information Recovery from Pairwise Measurements: From Joint Object Matching to Fundamental Statistical Limits

Yuxin Chen - Stanford University
Apr 2 2014 - 3:00pm
Event type: 
110 Fine Hall

A variety of inference tasks in practice require recovering multiple objects from pairwise measurements over some measurement graph. A small sample of applications include rotation registration, joint object matching based on noisy pairwise maps, etc. In general, the challenges arise from the imperfection of measurements: 1) inaccuracy: a dominant fraction of measurements are corrupted; 2) incompleteness: a significant fraction of object pairs are unobservable. 
This talk starts with a special scientific problem called joint object matching. Specifically, joint object / graph matching concerns the following problem:  given multiple similar objects drawn from the same universe and a collection of pairwise matches computed in isolation,  one wishes to recover globally compatible matching across all objects. 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 remarkable error-correction ability, i.e. it is guaranteed to work even when a dominant fraction of the input maps behave like random outliers.
We then develop a fundamental statistical limits on the non-corruption rate of measurements on a general setup defined over a group containing M different values. For a large class of homogenous graphs, the fundamental error-tolerance limits depend almost only on the edge sparsity of the measurement graph irrespective of other graphical metrics.  Encouragingly, when M is small, the convex program MatchLift achieves near-optimal error-correction ability for the most natural Erdos-Renyi random graph models.
Short 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.