Why is bidiagonalization necessary for SVD of large matrices?

Question

I have been reading about Singular Value Decomposition (SVD) for my ML project. It is quite evident that it is an important algorithm with numerous applications.

I have come across Golub-Kahan Bidiagonalization approach numerous times in computation of SVD. It is one of the oldest and widest used (with some tweaking) algorithm in libraries like LAPACK.

I have understood most of the things related to SVD, but there are certain pieces which I am not able to connect properly and hence require help:

1. Why is bidiagonalization an important step before computing SVD?
2. Does Golub-Kahan Bidiagonalization approach utilize Householder Bidiagonalization in any way? I have come across various answers on this platform related to SVD and Golub-Kahan which suggests the same. But I came across the LAPACK's User Guide which seems not be using Householder Bidiagonalization approach for diagonalization even when it is explicitly stating that Golub-Kahan-Lanczos approach is used.

P.S: I am aware that there are a lot of questions similar to mine on the forum, and I would not mind if you use them here to clear out my doubts,I tried to understand them but couldn't figure more than what I know.

Answer 1

Computing the SVD of a matrix $A$ is equivalent to computing the eigenvalue decomposition of the symmetric matrix $$H = \begin{bmatrix} 0 & A^T \\ A & 0 \end{bmatrix}.$$ In principle, this can be done using the $QR$ algorithm, but the cost is significantly reduced if $A$ has already been reduced to bidiagonal form $B$. In this case $H$ is only a row and column permutation away from a tridiagonal matrix.

In short, the Golub-Kahan bidiagonalization procedure is a preprocessing step which significantly lowers the cost of the (implicit) application of the QR algorithm to the permuted form of $H$.

If $A$ is a dense matrix, then this initial reduction is typically performed using Householder reflectors.

If $A$ is a sparse matrix, then the explicit reduction to bidiagonal form will typically overwhelm the storage capacity of the computer. Instead, we can use the Golub-Kahan-Lanczos algorithm to compute a smaller bidiagonal matrix which can in turn be used to extract approximations of the dominant singular values of $A$.