
News
Colloquia
Sketching as a Tool for Numerical Linear Algebra
Speaker: David Woodruff
IBM Watson
December 15, 2014  3:00 p.m. to 4:00 p.m.
Location: CII (Low) 3051
Hosted By: Dr. Malik MagdonIsmail (x4857)
Abstract:
I'll highlight recent advances in algorithms for numerical linear algebra that have come from the technique of linear sketching, whereby given an n x d matrix A, one first compresses A to an m x d matrix S*A, where S is a certain m x n random matrix with m much less than n. Much of the expensive computation is then performed on S*A, thereby accelerating the solution for the original problem involving A. I'll discuss recent advances in least squares as well as robust regression, including least absolute deviation and Mestimators. I'll also discuss low rank approximation, and a number of variants of these problems such as kernel and communicationefficient solutions. Finally, I'll mention limitations of the method.
Bio:
David Woodruff received his Ph.D. from MIT in 2007 and has been a research scientist at IBM Almaden since then. His research interests are in the area of big data, including communication complexity, compressed sensing, data streams, machine learning, and numerical linear algebra. He received best paper awards in STOC and PODS, and the Presburger award. He is the author of the monograph "Sketching as a Tool for Numerical Linear Algebra".
Last updated: November 24, 2014

