Randomised numerical linear algebra: foundations and algorithms (arxiv.org)

I just discovered this field; I needed an algorithm to compute a low rank approximation of a large covariance matrix without first building the matrix. I'm using algorithm 16 in this paper which is simple but very good!