LFCS seminar: Mihai Cucuringu: Robust ranking via eigenvector and semidefinite programming synchronization
What 


When 
May 22, 2018 from 04:00 PM to 05:00 PM 
Where  IF 4.31/4.33 
Add event to calendar 
vCal iCal 
We consider the classic problem of establishing a statistical ranking of a set of n items given a set of inconsistent and incomplete pairwise comparisons between such items. Instantiations of this problem occur in numerous applications in data analysis (e.g., ranking teams in sports data), computer vision, and machine learning. We formulate the above problem of ranking with incomplete noisy information as an instance of the group synchronization problem over the group SO(2) of planar rotations, whose usefulness has been demonstrated in numerous applications in recent years. Its least squares solution can be approximated by either a spectral or a semidefinite programming (SDP) relaxation, followed by a rounding procedure. We perform extensive numerical simulations on both synthetic and realworld data sets showing that our proposed method compares favorably to other algorithms from the recent literature, and also discuss an application to extracting leaders and laggers in multivariate time time series data.
We propose a similar synchronizationbased algorithm for the rankaggregation problem, which integrates in a globally consistent ranking pairwise comparisons given by different rating systems on the same set of items. We also discuss the problem of semisupervised ranking when there is available information on the ground truth rank of a subset of players, and propose an algorithm based on SDP which recovers the ranks of the remaining players. Finally, synchronizationbased ranking, combined with a spectral technique for the densest subgraph problem, allows one to extract consistent partial rankings, in other words, to identify the rank of a small subset of players whose pairwise comparisons are less noisy than the rest of the data, which other methods are not able to identify.
Time permitting, we briefly discuss ongoing work on extensions and applications of the group synchronization framework to kway synchronization, list synchronization, synchronization with heterogeneous information, and phase unwrapping.