Finding structure with randomness: Probabilistic algorithms for constructing approximate matrix decompositions

Understand

Low-rank matrix approximations, such as the truncated singular value decomposition and the rank-revealing QR decomposition, play a central role in data analysis and scientific computing.

• This work surveys and extends recent research which demonstrates that randomization offers a powerful tool for performing low-rank matrix approximation.
• These techniques exploit modern computational architectures more fully than classical methods and open the possibility of dealing with truly massive data sets.
• This paper presents a modular framework for constructing randomized algorithms that compute partial matrix decompositions.