1
$\begingroup$

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!

$\endgroup$
2
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.