Help with a lower-rank approximation algorithm. Is this for the sake of stability?

Question

The algorithm to compute SVD of a matrix $A$ is as the following,

1. Compute an orthogonal basis $Q$ for the range of $A$.
2. Do singular value decomposition on matrix $B=Q^TA$.
3. Let $B_k$ be the rank-$k$ truncated SVD of $B$, return $QB_k$.

Is there any name for this algorithm, can anyone help provide some reference? Why we don't directly compute lower-rank approximation by SVD on $A$? Is this for the reason of numerical stability? Thanks!

Answer 1

Let $A$ been an $m$ by $n$ matrix. If $m \gg n$, then your algorithm is a sensible preprocessing step. Specifically, one computes a $QR$ factorization of $A$ with column pivoting, say, $AP = QR$, where $P$ is a permutation matrix. Ideally, $R$ is small enough to fix inside the cache and the SVD of $R$ can now be computed rapidly with good cache reuse. A similar idea applies, if $m \ll n$.

More information, including references and a brief description of the "standard" SVD algorithm (LAPACK) can be found at this (very stable) link

http://www.netlib.org/lapack/lug/node53.html