5Low-Rank Approximation

It is well-known that the solution to Low-rank Approximation can be obtained by computing the singular value decomposition (SVD) of $\vec{A}$. In particular, if $\vec{A} = \vec{U} \vec{\Sigma} \vec{V}^\T$ is the SVD of $\vec{A}$, then the optimal low-rank approximation of rank $k$ is given by

where $\vec{U}_k$ contains the first $k$ columns of $\vec{U}$, $\vec{\Sigma}_k$ is the diagonal matrix containing the first $k$ singular values, and $\vec{V}_k$ contains the first $k$ columns of $\vec{V}$.

This chapter focuses on algorithms which work with matrices stored in memory. When reading individual entries of $\vec{A}$ is expensive, a related class of sampling-based low-rank approximation methods may be more appropriate. We discuss these methods along side other sampling-based methods in Chapter 7.

Further reading¶

• Halko et al. (2011): Early survey on the Randomized SVD and Randomized Subspace Iteration that that popularized RandNLA for low-rank approximation.

• Musco & Musco (2015): First analysis of Randomized Block Krylov Iteration

• Tropp & Webber (2023): Recent explicit analysis of a number of low-rank approximation algorithms,

• Meyer et al. (2024), Chen et al. (2025): Line of work in TCS which study Randomized Block Krylov Iteration in the “small-block” setting (where the block size is smaller than the target rank).