5
$\begingroup$

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?

$\endgroup$
6
$\begingroup$

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.

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.