Why is bidiagonalization necessary for SVD of large matrices? 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:


*

*Why is bidiagonalization an important step before computing SVD?

*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.
 A: 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$.
