BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//talks.cam.ac.uk//v3//EN
BEGIN:VTIMEZONE
TZID:Europe/London
BEGIN:DAYLIGHT
TZOFFSETFROM:+0000
TZOFFSETTO:+0100
TZNAME:BST
DTSTART:19700329T010000
RRULE:FREQ=YEARLY;BYMONTH=3;BYDAY=-1SU
END:DAYLIGHT
BEGIN:STANDARD
TZOFFSETFROM:+0100
TZOFFSETTO:+0000
TZNAME:GMT
DTSTART:19701025T020000
RRULE:FREQ=YEARLY;BYMONTH=10;BYDAY=-1SU
END:STANDARD
END:VTIMEZONE
BEGIN:VEVENT
CATEGORIES:Statistics
SUMMARY:Robust ranking\, constrained ranking and rank aggr
egation via eigenvector and semidefinite programmi
ng synchronization - Mihai Cucuringu (Oxford)
DTSTART;TZID=Europe/London:20170519T160000
DTEND;TZID=Europe/London:20170519T170000
UID:TALK71961AThttp://talks.cam.ac.uk
URL:http://talks.cam.ac.uk/talk/index/71961
DESCRIPTION:We consider the classic problem of establishing a
statistical ranking of a set of n items given a se
t of inconsistent and incomplete pairwise comparis
ons between such items. Instantiations of this pro
blem occur in numerous applications in data analys
is (e.g.\, ranking teams in sports data)\, compute
r vision\, and machine learning. We formulate the
above problem of ranking with incomplete noisy inf
ormation as an instance of the group synchronizati
on problem over the group SO(2) of planar rotation
s\, whose usefulness has been demonstrated in nume
rous applications in recent years. Its least squar
es solution can be approximated by either a spectr
al or a semidefinite programming (SDP) relaxation\
, followed by a rounding procedure. We perform ext
ensive numerical simulations on both synthetic and
real-world data sets showing that our proposed me
thod compares favorably to other algorithms from t
he recent literature\, and also discuss an applica
tion to extracting leaders and laggers in multivar
iate time time series data.\n\nWe propose a simila
r synchronization-based algorithm for the rank-agg
regation problem\, which integrates in a globally
consistent ranking pairwise comparisons given by d
ifferent rating systems on the same set of items.
We also discuss the problem of semi-supervised ran
king when there is available information on the gr
ound truth rank of a subset of players\, and propo
se an algorithm based on SDP which recovers the ra
nks of the remaining players. Finally\, synchroniz
ation-based ranking\, combined with a spectral tec
hnique for the densest subgraph problem\, allows o
ne to extract consistent partial rankings\, in oth
er words\, to identify the rank of a small subset
of players whose pairwise comparisons are less noi
sy than the rest of the data\, which other methods
are not able to identify.
LOCATION:MR12\, Centre for Mathematical Sciences\, Wilberfo
rce Road\, Cambridge.
CONTACT:Quentin Berthet
END:VEVENT
END:VCALENDAR