Ken Clarkson: More Near-Linear Linear Algebra, via Sketching

Tuesday, May 3, 2016 - 4:00pm to 5:00pm
Cookies and Milk at 3:45pm
Patil/Kiva G449
Ken Clarkson, IBM Research, Almaden

Abstract:  In recent years there have been significant improvements in matrix
algorithms for data analysis, including several cases where the running
times are nearly linear: for an input matrix A, the running time is
dominated by a term within log factors of the number nnz(A) of nonzero
entries of A.

One category of such speedup techniques, yielding approximation algorithms,
is *sketching*, where A is compressed to a matrix with fewer rows and/or
columns, such that the compressed version preserves key properties of the

I will briefly survey results and techniques involving sketching, and
outline results for two variations of the classical problem of finding the
best rank-k approximation to a matrix A under the Frobenius (sum of

squares) norm.