University of Minnesota
University Relations
myU OneStop

Go to unit's home.

Home | Seminars and Symposia | Past seminars/symposia: Thursday, November 5, 2015

DTC Seminar Series

Sketching as a Tool for Numerical Linear Algebra


David P. Woodruff
Almaden Research Center

Thursday, November 5, 2015
4:30 p.m. reception
5:00 p.m. seminar

401/402 Walter Library

View webcast of this lecture (Webex format) audio is missing in the first 5 minutes.

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. Such techniques lead to the fastest known algorithms for least squares regression and low rank approximation. I'll also discuss robust regression and robust low rank approximation, including least absolute deviation and M-estimators loss functions.