Bidiagonalization is one of unitary (orthogonal)
matrix decomposition
In the mathematical discipline of linear algebra, a matrix decomposition or matrix factorization is a factorization of a matrix into a product of matrices. There are many different matrix decompositions; each finds use among a particular class of ...
s such that U* A V = B, where U and V are
unitary (
orthogonal
In mathematics, orthogonality is the generalization of the geometric notion of '' perpendicularity''.
By extension, orthogonality is also used to refer to the separation of specific features of a system. The term also has specialized meanings in ...
) matrices; * denotes
Hermitian transpose
In mathematics, the conjugate transpose, also known as the Hermitian transpose, of an m \times n complex matrix \boldsymbol is an n \times m matrix obtained by transposing \boldsymbol and applying complex conjugate on each entry (the complex co ...
; and B is upper
bidiagonal. A is allowed to be rectangular.
For
dense matrices, the left and right unitary matrices are obtained by a series of
Householder reflection
In linear algebra, a Householder transformation (also known as a Householder reflection or elementary reflector) is a linear transformation that describes a reflection (mathematics), reflection about a plane (mathematics), plane or hyperplane conta ...
s alternately applied from the left and right. This is known as Golub-Kahan bidiagonalization. For large matrices, they are calculated iteratively by using
Lanczos method
The Lanczos algorithm is an iterative method devised by Cornelius Lanczos that is an adaptation of power methods to find the m "most useful" (tending towards extreme highest/lowest) eigenvalues and eigenvectors of an n \times n Hermitian matrix ...
, referred to as Golub-Kahan-Lanczos method.
Bidiagonalization has a very similar structure to the
singular value decomposition
In linear algebra, the singular value decomposition (SVD) is a factorization of a real or complex matrix. It generalizes the eigendecomposition of a square normal matrix with an orthonormal eigenbasis to any \ m \times n\ matrix. It is r ...
(SVD). However, it is computed within finite operations, while SVD requires iterative schemes to find singular values. The latter is because the squared singular values are the roots of
characteristic polynomial
In linear algebra, the characteristic polynomial of a square matrix is a polynomial which is invariant under matrix similarity and has the eigenvalues as roots. It has the determinant and the trace of the matrix among its coefficients. The ...
s of A* A, where A is assumed to be tall.
References
* .
External links
Golub-Kahan-Lanczos Bidiagonalization Procedure
{{Numerical linear algebra
Matrix theory
Numerical linear algebra