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:Microsoft Research Machine Learning and Perception
Seminars
SUMMARY:Lifts of Convex Sets and Cone Factorizations - Rek
ha R. Thomas\, University of Washington\, Seattle
DTSTART;TZID=Europe/London:20130802T150000
DTEND;TZID=Europe/London:20130802T160000
UID:TALK46513AThttp://talks.cam.ac.uk
URL:http://talks.cam.ac.uk/talk/index/46513
DESCRIPTION:The representation of a convex set is crucial for
the efficiency of linear optimization algorithms.
A common idea to optimize a linear function over
a complicated convex set is to express the set as
the projection of a much simpler convex set in a h
igher dimension\, called\na ``lift'' of the origin
al set. In the early 1990s Yannakakis showed that
there is a remarkable connection between the size
of the smallest polyhedral lift of a polytope and
the nonnegative rank of the slack\nmatrix of the p
olytope. I will show how this theorem can be gener
alized to convex sets via cone factorizations of n
onnegative operators. In practice\, one usually on
ly has a numerical approximation to a cone factori
zation. I will also show how such\napproximate fac
torizations can be used to construct efficient app
roximations of polytopes\, and mention some of the
many open questions in this area.\n\nJoint work w
ith Joao Gouveia (University of Coimbra) and Pablo
Parrilo\n(MIT)\n
LOCATION:Microsoft Research Ltd\, 21 Station Road\, Cambrid
ge\, CB1 2FB
CONTACT:Microsoft Research Cambridge Talks Admins
END:VEVENT
END:VCALENDAR