Reorthogonalization for the Golub-Kahan-Lanczos bidiagonal reduction

The Golub-Kahan-Lanczos (GKL) bidiagonal reduction generates, by recurrence, the matrix factorization of X ∈ ℝ^m×n, m≥n, given by X = UBV^T where U ∈ ℝ^m×n is left orthogonal, V ∈ ℝ^m×n is orthogonal, and B ∈ ℝ^m×n is bidiagonal. When the GKL recurrence is implemented in finite precision arithmetic, the columns of U and V tend to lose orthogonality, making a reorthogonalization strategy necessary to preserve convergence of the singular values. The use of an approach started by Simon and Zha (SIAM J Sci Stat Comput, 21:2257-2274, 2000) that reorthogonalizes only one of the two left orthogonal matrices U and V is shown to be very effective by the results presented here. Supposing that V is the matrix reorthogonalized, the reorthogonalized GKL algorithm proposed here is modeled as the Householder Q-R factorization of, where V_k = V(:,1:k). That model is used to show that if ε_M is the machine unit and, where tril(·) is the strictly lower triangular part of the contents, then: (1) the GKL recurrence produces Krylov spaces generated by a nearby matrix X + δX, {double pipe}δ X{double pipe}_F = O (ε_M + n̄) {double pipe}X{double pipe}_F; (2) singular values converge in the Lanczos process at the rate expected from the GKL algorithm in exact arithmetic on a nearby matrix; (3) a new proposed algorithm for recovering leading left singular vectors produces better bounds on loss of orthogonality and residual errors.