BEGIN:VCALENDAR
PRODID:-//Mercury//HGEvent//EN
VERSION:2.0
METHOD:PUBLISH
BEGIN:VEVENT
STATUS:CONFIRMED
LAST-MODIFIED:20140426T231511
PRIORITY:0
CLASS:PUBLIC
UID:ATEvent-eed436ece7e23bbcfe0d4623c4969225
SUMMARY:ARC Colloquium: David Woodruff\, IBM Almaden Research Center\, San Jose\, CA.
DESCRIPTION:Title: Low Rank Approximation and Regression in Input Sparsity Time \nAbstract:\nWe improve the running times of algorithms for least squares regression and low-rank approximation to account for the sparsity of the input matrix. Namely\, if nnz (A) denotes the number of non-zero entries of an input matrix A: \nwe show how to solve approximate least squares regression given an n x d matrix A in nnz(A) + poly(d log n) time we show how to find an approximate best rank-k approximation of an n x n matrix in nnz(A) + n*poly(k log n) time All approximations are relative error. Previous algorithms based on fast Johnson-Lindenstrauss transforms took at least ndlog d or nnz(A)*k time. We have implemented our algorithms\, and preliminary results suggest the algorithms are competitive in practice. \nJoint work with Ken Clarkson.\n \n
DTSTART:20130426T100000
DTEND:20130426T100000
CREATED:20130416T141505
DTSTAMP:20130416T141505
SEQUENCE:0
LOCATION:
END:VEVENT
END:VCALENDAR