* Faculty       * Staff       * Students & Alumni       * Committees       * Contact       * Institute Directory
* Undergraduate Program       * Graduate Program       * Courses       * Institute Catalog      
* Undergraduate       * Graduate       * Institute Admissions: Undergraduate | Graduate      
* Colloquia       * Seminars       * News       * Events       * Institute Events      
* Overview       * Lab Manual       * Institute Computing      
No Menu Selected

* News


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 Magdon-Ismail (x4857)


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 M-estimators. I'll also discuss low rank approximation, and a number of variants of these problems such as kernel and communication-efficient solutions. Finally, I'll mention limitations of the method.


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