A QR factorization of a rectangular matrix with is a factorization with orthonormal and upper trapezoidal. The factor has the form , where is and upper triangular. Partitioning conformably with we have
There are therefore two forms of QR factorization:
- is the full QR factorization,
- is the reduced (also called economy-sized, or thin) QR factorization.
To prove the existence of a QR factorization note that if has full rank then is symmetric positive definite. Since implies , we can take to be the Cholesky factor of and then define . The resulting has orthonormal columns because
Therefore when has full rank there is a unique reduced QR factorization if we require to have positive diagonal elements. (Without this requirement we can multiply the th column of and the th row of by and obtain another QR factorization.)
When has full rank the columns of span the column space (or range) of . Indeed implies while implies , so . Furthermore, gives , so the columns of span the null space of .
The QR factorization provides a way of orthonormalizing the columns of a matrix. An alternative is provided by the polar decomposition , where has orthonormal columns and is positive semidefinite. The orthogonal polar factor is the closest matrix with orthonormal columns to in any unitarily invariant norm, but it is more expensive to compute than the factor.
There are three standard ways of computing a QR factorization.
Gram–Schmidt orthogonalization computes the reduced factorization. It has the disadvantage that in floating-point arithmetic the computed is not guaranteed to be orthonormal to the working precision. The modified Gram–Schmidt method (a variation of the classical method) is better behaved numerically in that for some constant , where is the unit roundoff, so the loss of orthogonality is bounded.
Householder QR factorization and Givens QR factorization both construct as a product of orthogonal matrices that are chosen to reduce to upper trapezoidal form. In both methods, at the start of the th stage we have
where is upper triangular and is a product of Householder transformations or Givens rotations. Working on we now apply a Householder transformation or Givens rotations in order to zero out the last elements of and thereby take the matrix one step closer to upper trapezoidal form.
Householder QR factorization is the method of choice for general matrices, but Givens QR factorization is preferred for structured matrices with a lot of zeros, such as upper Hessenberg matrices and tridiagonal matrices.
Both these methods produce in factored form and if the product is explicitly formed they yield a computed that is orthogonal to the working precision, that is, , for some constant .
Modified Gram–Schmidt, Householder QR, and Givens QR all have the property that there exists an exactly orthogonal such that the computed satisfies
for some constant .
Another way of computing a QR factorization is by the technique in the existence proof above, via Cholesky factorization of . This is known as the Cholesky QR algorithm and it has favorable computational cost when . In its basic form, this method is not recommended unless is extremely well conditioned, because the computed is far from orthonormal for ill conditioned matrices. The method can be made competitive with the others either by using extra precision or by iterating the process.
Column Pivoting and Rank-Revealing QR Factorization
In practice, we often want to compute a basis for the range of when is rank deficient. The basic QR factorization may not do so. Householder QR factorization with column pivoting reveals rank deficiency by incorporating column interchanges. At the th stage, before applying a Householder transformation to , the column of largest -norm of , the th say, is determined, and if its norm exceeds that of then the th and th columns of are interchanged. The result is a factorization , where is a permutation matrix and satisfies the inequalities
In particular,
If is rank deficient then has the form
with nonsingular, and the rank of is the dimension of .
Near rank deficiency of to tends to be revealed by a small trailing diagonal block of , but this is not guaranteed. Indeed for the Kahan matrix
where and , is of order times larger than the smallest singular value for small and is invariant under QR factorization with column pivoting.
In practice, column pivoting reduces the efficiency of Householder QR factorization because it limits the amount of the computation that can be expressed in terms of matrix multiplication. This has motivated the development of methods that select the pivot columns using randomized projections. These methods gain speed and produce factorizations of similar rank-revealing quality, though they give up the inequalities .
It is known that at least one permutation matrix exists such that the QR factorization of is rank-revealing. Computing such a permutation is impractical, but heuristic algorithms for producing an approximate rank-revealing factorization are available.
References
This is a minimal set of references, which contain further useful references within.
- Shivkumar Chandrasekaran and Ilse Ipsen, On Rank-Revealing Factorisations, SIAM J. Matrix Anal. Appl. 15(2), 592–622, 1994.
- Per-Gunnar Martinsson and Joel A. Tropp, Randomized Numerical Linear Algebra: Foundations and Algorithms, Acta Numerica, 2020, to appear.
- Nicholas J. Higham, Accuracy and Stability of Numerical Algorithms, second edition, Society for Industrial and Applied Mathematics, Philadelphia, PA, USA, 2002.
- Takeshi Fukaya, Ramaseshan Kannan, Yuji Nakatsukasa, Yusaku Yamamoto and Yuka Yanagisawa, Shifted Cholesky QR for Computing the QR Factorization of Ill-Conditioned Matrices, SIAM J. Sci. Comput. 42(1), A477–A503, 2020.
Related Blog Posts
- What Is a Householder Matrix? (2020)
- What Is an Orthogonal Matrix? (2020)
- What is the Polar Decomposition? (2020)
This article is part of the “What Is” series, available from https://nhigham.com/category/what-is and in PDF form from the GitHub repository https://github.com/higham/what-is.