[Ml-stat-talks] Ken Clarkson's talk

Sebastien Bubeck sbubeck at Princeton.EDU
Mon Mar 31 15:26:59 EDT 2014


=== ORFE Colloquium ===

DATE:   Tuesday, April 1st

TIME:   4:30pm

LOCATION:   Sherrerd Hall 101

SPEAKER:   Ken Clarkson, IBM Almaden

TITLE:   Sketching Algorithms for Numerical Linear Algebra

ABSTRACT: Many tasks in machine learning and statistics ultimately end up being problems that involve large matrices, and that do not require solutions that are extremely precise. Such problems are well-suited for applying the technique of *sketching*.

Sketching is a way to compress matrices that approximately preserves key matrix properties; it takes a given matrix A, and applies a sketching matrix S to produce a  sketch matrix B = SA that has fewer rows than A. (Sketching by multiplying on the right can also be used to reduce the number of columns.) For a good sketch B, if we solve a problem with input B, the solution will also be pretty good for input A. Moreover, for some problems, methods based on sketches can quickly find high-precision solutions to the original problem. In other cases, sketches can be used to summarize the data by identifying the most important rows or columns. Classical techniques for sketching include row and/or column sampling, and random projections. In recent years some techniques for sketching have been proposed with higher performance than these methods; these techniques have been applied to least-squares and robust regression, low-rank approximation, leverage score computation, and other problems.

I will describe some sketching techniques, and some recent theoretical results for applying sketching to robust regression, for which a single sketch is enough to allow approximate estimation of a broad class of M-estimators. This is joint work with David Woodruff, also at IBM Almaden.
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.cs.princeton.edu/pipermail/ml-stat-talks/attachments/20140331/9bbf1c0c/attachment.html>


More information about the Ml-stat-talks mailing list