BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//Talks.cam//talks.cam.ac.uk//
X-WR-CALNAME:Talks.cam
BEGIN:VEVENT
SUMMARY:Robust ranking\, constrained ranking and rank aggregation via eige
 nvector and semidefinite programming synchronization - Mihai Cucuringu (Ox
 ford)
DTSTART:20170519T150000Z
DTEND:20170519T160000Z
UID:TALK71961@talks.cam.ac.uk
CONTACT:Quentin Berthet
DESCRIPTION:We consider the classic problem of establishing a statistical 
 ranking of a set of n items given a set of inconsistent and incomplete pai
 rwise 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 pr
 oblem of ranking with incomplete noisy information as an instance of the g
 roup synchronization problem over the group SO(2) of planar rotations\, wh
 ose usefulness has been demonstrated in numerous applications in recent ye
 ars. Its least squares solution can be approximated by either a spectral o
 r a semidefinite programming (SDP) relaxation\, followed by a rounding pro
 cedure. We perform extensive numerical simulations on both synthetic and r
 eal-world data sets showing that our proposed method compares favorably to
  other algorithms from the recent literature\, and also discuss an applica
 tion to extracting leaders and laggers in multivariate time time series da
 ta.\n\nWe propose a similar synchronization-based algorithm for the rank-a
 ggregation problem\, which integrates in a globally consistent ranking pai
 rwise comparisons given by different rating systems on the same set of ite
 ms. We also discuss the problem of semi-supervised ranking when there is a
 vailable information on the ground truth rank of a subset of players\, and
  propose an algorithm based on SDP which recovers the ranks of the remaini
 ng players. Finally\, synchronization-based ranking\, combined with a spec
 tral technique for the densest subgraph problem\, allows one to extract co
 nsistent partial rankings\, in other words\, to identify the rank of a sma
 ll subset of players whose pairwise comparisons are less noisy than the re
 st of the data\, which other methods are not able to identify.
LOCATION:MR12\, Centre for Mathematical Sciences\, Wilberforce Road\, Camb
 ridge.
END:VEVENT
END:VCALENDAR