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?
