# 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.

Ideally though what you're looking for is Lanczos bidiagonalization. Lanczos bidiagonlization is intimately related to the tridiagonalization of the cyclic matrix, but can also be derived on its own.

PROPACK is a good example of an existing software package that implements Lanczos bidiagonalization for SVD. It sounds like you're required to implement it yourself, but the page I'm linking to here provides a number of papers that provide an introduction to the algorithmic approach. You can likely ignore the "partial reorthogonalization" that is a key part of the PROPACK package and focus on the bidiagonalization.

Of course, if this isn't a homework assignment or educational exercise, then I would suggest considering using PROPACK or related packages instead of implementing it yourself! There's no need to reinvent the wheel. SLEPc also includes a Lanczos SVD implementation. The SLEPc documentation provides a good introduction to Lanczos bidiagonalization as well.

• 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? May 12, 2013 at 19:16
• Check Section 3.1 of the first PROPACK reference. May 12, 2013 at 22:38
• I have deleted my post, as it was about squaring up the system, what is really not recommended...
– Jan
May 28, 2013 at 13:51