Golub-Kahan-Lanczos Bidiagonalization Procedure.

As discussed in §6.2, the first phase of a transformation method for the SVD is to compute unitary matrices $U$ and $V$ such that $U^*AV$ is in bidiagonal form. In fact, the first column $v_1$ of $V$ can be chosen as an arbitrary unit vector, after which the other columns of $U$ and $V$ are generally determined uniquely. We write this as

$$U^{*} A V = B = \left[ \begin{array}{cccccc} \alpha_1 & \be... ...\beta_{n-1} \\ & & & & &\alpha_{n} \\ \end{array} \right].$$ (111)

All $\alpha$s and $\beta$s are real even if $A$ was complex.

The constants $\alpha_k$ and $\beta_k$ are given by

$$\alpha_k = u^{\ast}_k A v_k \quad\mbox{and}\quad \beta_k = u^{\ast}_k A v_{k+1}.$$

From the bidiagonal form (6.4) we may derive a double recursion for the columns $u_k$ and $v_k$ of $U$ and $V$. Multiplying by $U$, we have

$$A \left[\begin{array}{cccc} v_1 & v_2 & \ldots & v_n \e... ... & \beta_{n-1} \\ & & & & \alpha_n \\ \end{array} \right].$$

Equating the $k$th columns on both sides, we get

$$Av_k = \beta_{k-1}u_{k-1} + \alpha_k u_k$$

or

$$\alpha_k u_k = Av_k - \beta_{k-1}u_{k-1}, \quad\quad \beta_0 = 0.$$ (112)

On the other hand, from the relation

$$A^{\ast} \left[\begin{array}{cccc} u_1 & u_2 & \ldots & u_n... ... & \\ & & & \beta_{n-1} & \alpha_n \\ \end{array} \right],$$

we get

$$A^{\ast} u_k = {\alpha}_k v_k + {\beta}_k v_{k+1}$$

or

$${\beta}_k v_{k+1} = A^{\ast} u_k - {\alpha}_k v_k.$$ (113)

Since the columns of $U$ and $V$ are normalized, we must have

$$\alpha_k = \Vert Av_k - \beta_{k-1}u_{k-1}\Vert _2$$

and

$$\beta_k = \Vert A^* u_k - \alpha_k v_k\Vert _2.$$

We summarize the recursion in the following algorithm.

Collecting the computed quantities from the first $k$ steps of the algorithm, we have the following important relations:

$$A V_k = U_k B_k,$$ (114)

$$A^{\ast} U_{k} = V_k B^*_k + \beta_{k}v_{k+1}e^*_k,$$ (115)

and

$$U^{\ast}_k U_k = I, \quad V^{\ast}_k V_k = I, \quad \mbox{and} \quad V^{\ast}_k v_{k+1} = 0,$$ (116)

where $B_k$ is the $k$ by $k$ leading principal submatrix of $B$ defined in (6.4).