Randomized methods for matrix computations and analysis of high dimensional data

This report surveys a number of randomized techniques that have recently been proposed for computing matrix factorizations and for analyzing high dimensional data sets. It presents some modifications to algorithms that have previously been published that increase efficiency and broaden the range of applicability of the methods. The report also describes classical (non-randomized) techniques for solving the same problems such as, e.g., Krylov methods, subspace iteration, and rank-revealing QR factorizations. Differences and similarities between classical and new methods are discussed, and guidance is provided on when to use which set of techniques. One chapter discusses so called structure preserving factorizations such as the Interpolative Decomposition (ID) and the CUR decomposition. The factors in these decompositions preserve certain properties of the original matrix such as sparsity of non-negativity, which both improves computational efficiency and helps with data interpretation.