2
$\begingroup$

I am trying to implement a fast SVD algorithm for obtaining the first $k$ singular values/vectors of an $M\times N$ matrix ($k < \min(M,N)$) using the following 2-step process:

1) bidiagonalize the matrix using Lanczos bidiagonalization (e.g. R. M. Larsen, 1998)

2) diagonalize the bidiagonal matrix via QR decomposition or divide and conquer algorithm.

Here is where I am confused. My understanding is that the first step (Lanczos bidiagonalization) is the most expensive step. Therefore, I should perform as few Lanczos iterations as possible in order to keep the algorithm fast/efficient. Since I am only trying to find the first $k$ singular values/vectors, my initial thought was that I only need to perform $k$ iterations of Lanczos bidiagonalization (i.e. recover only the first $k$ Lanczos vectors). If I do this, and then take the svd of the resulting bidiagonal matrix, I find that only the first couple singular values are accurate. This leads me to believe that if I want to compute the first $k$ singular values/vectors accurately, I need to perform $L$ iterations of Lanczos bidiagonalization ($L>k$) in order to obtain reasonably accurate singular values. For example, choosing $L=2k$ seems to produce reasonable results for the few tests I have done.

Is there a technique or rule of thumb for choosing a reasonable number of Lanczos iterations?

$\endgroup$
  • $\begingroup$ I don't know enough to explain the algorithm, but I know that the Spectra library implements similar ideas. $\endgroup$ – Nicholas Mancuso Aug 11 '17 at 16:43

Your Answer

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

Browse other questions tagged or ask your own question.