Golub-Kahan-Lanczos Method

We have seen that the Hermitian eigenvalue problem and the singular value decomposition are closely related. The singular values of a matrix $A$ are the square roots of the eigenvalues of Hermitian matrix $A^{\ast} A$. Consequently, we can calculate singular values by applying the Hermitian Lanczos method to $A^{\ast} A$. The matrix-vector product required by the algorithm can be computed in the form $A^{\ast} (A q)$.

In this section we consider applying the Lanczos method of §4.4 to $H(A)$. The special structure of $H(A)$ lets us choose a special starting vector that leads to a cheaper algorithm that produces two sequences of vectors, one intended to span the left singular vectors and one for the right singular vectors. In addition, it reduces $A$ to bidiagonal form $B$; i.e., $B$ is nonzero only on the main diagonal and first superdiagonal. We derive it from first principles and then show how it is related to Lanczos as described in §4.4.