Randomized algorithms for low-rank matrix approximation: Design, analysis, and applications

Understand

This survey explores modern approaches for computing low-rank approximations of high-dimensional matrices by means of the randomized SVD, randomized subspace iteration, and randomized block Krylov iteration.

• The paper compares the procedures via theoretical analyses and numerical studies to highlight how the best choice of algorithm depends on spectral properties of the matrix and the computational resources available.
• Despite superior performance for many problems, randomized block Krylov iteration has not been widely adopted in computational science.
• The paper strengthens the case for this method in three ways.