7.3Low-rank approximation

In Chapter 4 we discuss algorithms for obtaining a low-rank aprpoxiamtion to $\vec{A}$. These algorithms require one or more passes over the data-matrix $\vec{A}$. Remarkably, in some settings, it is possible to obtain a good low-rank approximation without even observing all of $\vec{A}$.