# SVD and Lanczos method

I have been given the task of implementing SVD using the Lanczos method.

As I understand it only helps to find eigenvalues using a sequence of tridiagonal matrices, but i don't know how to apply this to actually computing the SVD.

Do I need to approximate the given matrix with tridiagonal and then compute SVD with different algorithm or something different?

In theory, you can "square up" $A$ as Jan illustrates in his answer, but you really don't want to do that when actually computing the SVD, as it comes at a significant cost of accuracy. A better approach that leverages standard Lanczos tridiagonalization is to perform the tridiagonalization of the matrix $\left[\begin{smallmatrix} 0 & A \\ A^T & 0 \end{smallmatrix}\right]$. This avoids the accuracy loss from squaring up, and you can extract both the singular values and their accompanying left and right vectors from the eigendecomposition of this larger matrix.
• I can't understand how will the eigenvectors of tridiagonalized $\begin{matrix} 0 & A \\ A^T & 0 \\ \end{matrix}$ will help to find left and right singular vectors of $A$. What do I need to do with them? – John Smith May 12 '13 at 19:16