Singular value decomposition (SVD) is a powerful tool but can be very slow for large dense matrices that may be stored on disk rather than in memory. Over the past decade or so, new algorithms have been proposed that allow for a speed up by first assuming we only want \(k\) singular values, and then exploiting randomization.

Check out my presentation on Randomized SVDs for the Algorithm Interest Group over at UIUC.

I also wrote up a short ipython notebook with some implementations:
html / ipynb.