Poor covergence with clustered large singular values.
bwlewis opened this issue · 1 comments
Giuseppe Rodriguez pointed out a pathology when the singular values cluster near the largest value. In this case it's hard to pick out a truncated space containing the largest few singular values because they are all very similar. This is the mirror image of the problem detecting the smallest singular values for discrete ill-posed problems.
We implemented an additional convergence tolerance requiring the estimated singular values to converge (along with the estimated spaces) to help improve this a bit. The convergence criteria are now:
- (tol) subspace convergence when ||A^T U - VS|| < tol*||A||, where the spectral norm ||A|| is approximated by the largest estimated singular value, and U, V, S are the matrices corresponding to the estimated left and right singular vectors, and diagonal matrix of estimated singular values, respectively.
- (svtol) singular value convergence when the maximum absolute relative change in each singular value from one iteration to the next is at most svtol.
See https://github.com/bwlewis/irlba/blob/master/tests/test.R#L130 for a good example of this problem.
The new convergence criterion comes at increased cost, two or more Lanczos iterations are always required.
The improvement outlined above is only a partial fix. A better solution will use block methods, which we plan on adding soon.