http://arxiv.org/pdf/1107.0789v6.pdf
The basic idea is to use randomized column sampling to divide the matrix into parts which are then decomposed using whatever method de jour you like. The decompositions of the parts can then be put back together to get a good estimate of the decomposition of the original matrix. Combined row and column decomposition can also be used and I think extension to row sampling (more convenient for us) is relatively trivial.
