Bidiagonalization

Remarks

The construction alternates sides. A reflection from the left zeros column $1$ below the diagonal. A reflection from the right acting on columns $2, \dots, n$ then zeros row $1$ to the right of the superdiagonal. The right reflection does not touch column $1$, so the zeros there survive. Repeating on the trailing submatrix gives $B$ after $n$ left and $n - 2$ right reflections. Singular values are preserved because multiplying by orthogonal matrices does not change $A^T A$ up to similarity: $(U^T A V)^T (U^T A V) = V^T A^T A V$.

The cost with Householder reflections is about $4 m n^2 - \tfrac{4}{3} n^3$ floating point operations. The matrix $B^T B$ is symmetric tridiagonal. So bidiagonalization is the first phase of the standard singular value decomposition algorithm, followed by an implicit QR iteration or a divide-and-conquer method on $B$. One cannot go further to a diagonal matrix in finitely many steps in general, because the singular values are roots of polynomials of arbitrary degree. Example: let $n = 2$. One left reflection maps the first column to a multiple of $e_1$, and one more acts on rows $2, \dots, m$ of the second column. This already gives an upper bidiagonal $2 \times 2$ block, with $V = I$. When $m \gg n$, it is cheaper to compute a QR factorization first and bidiagonalize the triangular factor.

Going deeper

For a student

It plays for the singular value decomposition the role that reduction to tridiagonal or Hessenberg form plays for eigenvalues. A Lanczos-type variant, Golub–Kahan–Lanczos bidiagonalization, builds $B$ one column at a time using only products with $A$ and $A^T$. It is the basis of the LSQR method for sparse least squares and of methods for a few singular values.