Lecture Notes on Randomized Linear Algebra (2013)
This stuff is incredibly useful when dealing with large matrices. The idea is that an n-by-n matrix often doesn't contain n^2 pieces of independent information, but can be written a product of matrices of size at most n-by-r (for r << n). A famous example of this is the Netflix recommendation matrix. In this case, you can often avoid O(n^2) complexity by only dealing with such low-rank approximations.<p>It should be noted that this overview dates from 2013 and that a lot of new results have appeared since then. The author gives some good references in the abstract.