BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//Memento EPFL//
BEGIN:VEVENT
SUMMARY:Algorithms for l_p Low-Rank Approximation and non-negative l_1 Col
 umn Subset Selection
DTSTART:20171023T111500
DTEND:20171023T121500
DTSTAMP:20260508T174135Z
UID:1d6a42d84781e3347159c21e18edf57e9de80ac93e86313ef548730f
CATEGORIES:Conferences - Seminars
DESCRIPTION:Silvio Lattanzi\, Google Zurich\nAbstract:\nThe problem of low
 -rank approximation and column subset selection of a matrix are usually st
 udied for the Frobenius norm. Nevertheless in practice it is often interes
 ting to study these problems also for l_1 or l_∞. Here we introduce new 
 algorithms for l_p Low-Rank Approximation and non-negative l_1 Column Subs
 et Selection.\n \nWe start by considering the problem of approximating a 
 given matrix by a low-rank matrix so as to minimize the entry-wise l_p-app
 roximation error\, for any p ≥ 1\; the case p = 2 is the classical SVD p
 roblem. We obtain the first provably good approximation algorithms for thi
 s version of low-rank approximation that work for every value of p ≥ 1\,
  including p = ∞. Our algorithms are simple\, easy to implement\, work w
 ell in practice\, and illustrate interesting tradeoffs between the approxi
 mation quality\, the running time\, and the rank of the approximating matr
 ix.\n \nThen we consider the problems of sparse regression and column sub
 set selection under l_1 error. For both problems\, we show that in the non
 -negative setting it is possible to obtain tight and efficient approximati
 ons\, without any additional structural assumptions. We then use this tech
 nique to obtain an efficient algorithm for column subset selection under l
 _1 error for non-negative matrices.\n \nJoint work with Flavio Chierichet
 ti\, Sreenivas Gollapudi\, Ravi Kumar\, Rina Panigrahy\, David P. Woodruff
  and Aditya Bhaskara.\n \nBio:\nSilvio Lattanzi received his bachelor (20
 05) and master (2007) degree both with highest honors from the Computer Sc
 ience department of Sapienza University of Rome. He received his PhD(2011)
  in Computer Science from the Computer Science department of Sapienza Univ
 ersity of Rome\, his advisor was Alessandro Panconesi. Silvio was a resear
 ch scientist at Google New York from January 2011 to March 2017. Silvio is
  a research scientist at Google Zurich since April 2017.\n\n\n 
LOCATION:BC 420 https://plan.epfl.ch/?room==BC%20420
STATUS:CONFIRMED
END:VEVENT
END:VCALENDAR