Randomized algorithms for the approximation of matrices.

I will discuss recent algorithmic developments for the classical problem
of approximating a given matrix by a low-rank matrix. This is motivated
by the need of faster algorithms for very large data and certain applications
that want the approximating matrix to have rows living in the span of only
a few rows of the original matrix, which adds a combinatorial twist to the
problem. The novel algorithms are based on sampling rows randomly (but
non-uniformly) and random projection, while showing that such a sample is
close to the top principal components, leading to a low rank approximation.