Reorthogonalization for the Golub-Kahan-Lanczos bidiagonal reduction.

The Golub-Kahan-Lanczos (GKL) bidiagonal reduction generates, by recurrence, the matrix factorization of $$X \in \mathbb{R }^{m \times n}, m \ge n$$, given by where $$U \in \mathbb{R }^{m \times n}$$ is left orthogonal, $$V \in \mathbb{R }^{n \times n}$$ is orthogonal, and $$B \in \mathbb{R }^{n \times 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, ) 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 $$\left( \begin{array}{c} 0_{n \times k} \\ X V_k \end{array}\right) $$ where $$V_k = V(:,1:k)$$. That model is used to show that if $$\varepsilon _M $$ is the machine unit and where $$\mathbf{tril }(\cdot )$$ is the strictly lower triangular part of the contents, then: (1) the GKL recurrence produces Krylov spaces generated by a nearby matrix $$X + \delta X$$, $$\Vert \delta X\Vert _F = \mathcal O (\varepsilon _M + \bar{\eta }) \Vert X\Vert _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. [ABSTRACT FROM AUTHOR]