Title: Near-Optimal Column-Based Matrix Reconstruction 
Speaker: Christos Boutsidis (IBM T. J. Watson Research Center)

We consider low-rank reconstruction of a matrix using its columns and
we present asymptotically optimal algorithms for both spectral norm
and Frobenius norm reconstruction. The main tools we introduce to
obtain our results are: (i) the use of fast approximate SVD-like
decompositions for column reconstruction, and (ii) two deter ministic
algorithms for selecting rows from matrices with orthonormal columns,
building upon the sparse representation theorem for decompositions of
the identity that appeared in [BSS09].

This is joint work with Petros Drineas and Malik Magdon-Ismail