Bidiagonalization

Bidiagonalization is a procedure in numerical linear algebra that transforms a given matrix into a bidiagonal form using unitary (or orthogonal in the real case) transformations on the left and right. For an m-by-n matrix A, bidiagonalization seeks orthogonal matrices Q ∈ R^{m×m} and P ∈ R^{n×n} such that A = Q B P^T, where B is bidiagonal (nonzero only on the main diagonal and either the superdiagonal or the subdiagonal). In the common upper bidiagonal form, B has nonzero entries on the diagonal b1, …, bk and on the superdiagonal c1, …, c_{k-1}.

The standard method uses Householder reflections, often implemented as the Golub–Kahan bidiagonalization. This algorithm applies a sequence of left and right reflections: a left reflector is used to annihilate the subdiagonal elements of the current column, followed by a right reflector to annihilate the off-diagonal elements of the current row, and this process repeats for subsequent columns. The result is a matrix B that is upper bidiagonal (or lower, if a variant is used). The reflectors are stored implicitly, allowing the factorization to be applied without forming Q and P explicitly.

Properties and applications: If A is m-by-n, Q and P are unitary, and B contains only the diagonal and first superdiagonal (for the standard form). Bidiagonalization is the first major step in computing the singular value decomposition (SVD): after reducing A to bidiagonal form, the singular values are obtained via an iterative procedure (e.g., QR iterations) applied to B. The process preserves numerical stability when implemented with orthogonal transformations and costs about O(m n min(m, n)) floating-point operations. The bidiagonal form also provides a compact representation useful in certain eigenvalue and low-rank approximation algorithms.