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
input.
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.