BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//Memento EPFL//
BEGIN:VEVENT
SUMMARY:Relative Error Tensor Low Rank Approximation
DTSTART:20170614T160000
DTEND:20170614T164500
DTSTAMP:20260406T211347Z
UID:4bf0b96d946dfc3fbc446c92376b81b8e80c43760475841473ac5afb
CATEGORIES:Conferences - Seminars
DESCRIPTION:David Woodruff\, IBM Research\nWe consider relative error low 
 rank approximation of tensors with respect to the Frobenius norm: given an
  order-$q$ tensor $A$\, output a rank-$k$ tensor $B$ for which $\\|A-B\\|_
 F^2 \\leq (1+\\epsilon)$OPT\, where OPT $= \\inf_{\\textrm{rank-}k~A'} \\|
 A-A'\\|_F^2$. Despite the success on obtaining relative error low rank app
 roximations for matrices\, no such results were known for tensors. One str
 uctural issue is that there may be no rank-$k$ tensor $A_k$ achieving the 
 above infinum. Another\, computational issue\, is that an efficient relati
 ve error low rank approximation algorithm for tensors would allow one to c
 ompute the rank of a tensor\, which is NP-hard. We bypass these issues via
  (1) bicriteria and (2) parameterized complexity solutions. Our results gi
 ve the first relative error low rank approximations for tensors for a larg
 e number of robust error measures for which nothing was known\, as well as
  column row and tube subset selection.
LOCATION:BC 420 https://plan.epfl.ch/?room==BC%20420
STATUS:CONFIRMED
END:VEVENT
END:VCALENDAR