For AI agents: use /llms.txt for the Nakafa content index.
We want to transform a matrix into upper triangular form, but not through elementary row operations, rather through orthogonal transformations that have better conditioning. Imagine rotating and reflecting geometric space to simplify the matrix, without changing its fundamental properties.
Let be a rectangular matrix with and . Then there exists an orthogonal matrix with and an upper triangular matrix with diagonal elements for , such that:
This representation is called the QR decomposition of .
The columns for of matrix can be orthonormalized using the Gram-Schmidt process:
We obtain orthonormal vectors for as columns of the orthogonal matrix . Conversely:
Thus with upper triangular matrix whose diagonal elements are .
If is completed with additional columns to become orthogonal matrix and becomes , then .
When we have a matrix with , there are two ways to represent the QR decomposition. The difference lies in the size of the matrices used.
Full QR decomposition uses full-sized matrices:
with being a full-sized orthogonal matrix and being an upper triangular matrix.
Since the lower part of matrix only contains zeros, we can save storage and computation. Economical QR decomposition only uses the parts that are actually needed:
Here only takes the first through -th columns from , and is a square upper triangular matrix.
Why is it called economical? Because we save storage space and computational time. Instead of storing matrix of size which can be very large, we only need of size .
The columns of matrix that we don't use form an orthonormal basis of :
The economical QR decomposition with condition for all is unique for matrix that has full rank.
Although the Gram-Schmidt process provides an elegant theoretical way to obtain QR decomposition, this method is not suitable for practical computation. The main problem is numerical instability due to cancellation, orthogonality of columns is quickly lost during computation.
To overcome this problem, we need a method that is more numerically stable. One of the most successful approaches is the Householder procedure, which uses orthogonal reflection transformations. Another alternative is the Givens procedure with rotation transformations.
For a vector with , we can define the Householder transformation matrix:
Note that is a dyadic product, which is the multiplication of column vector with row vector . The result of this multiplication is an matrix with rank for . Don't confuse this with scalar multiplication .
Let be a Householder transformation matrix for vector with . Then it holds:
is symmetric:
is an orthogonal matrix:
Multiplication of from the left with vector causes reflection of in the subspace , that is, in the hyperplane with normal vector
Given matrix with and . For QR decomposition computation, matrix is transformed column by column through Householder reflections into upper triangular form.
Start with and reflect the first column of with respect to a vector using reflection plane with:
Householder transformation matrix . We obtain:
with and .
Continue with reflection of the first column of the submatrix with reflection plane:
With transformation matrix:
We obtain:
with and , and so on until:
Finally we obtain the upper triangular matrix:
Thus we obtain the factorization:
with being an orthogonal matrix.
Implementation of the Householder procedure:
Start with:
For :
Compute:
and:
Then:
So we obtain:
Finally we obtain:
The numerical complexity for computing QR decomposition of matrix with Householder procedure is essentially:
Due to orthogonal transformation, it holds that
The diagonal elements of are the numbers from the -th step. Choosing the transformation so that all are positive gives the QR decomposition. If , does not have full rank and the algorithm stops.
For numerical reasons choose the sign so that cancellation is avoided:
Instead of constructing , in compact storage one can also store only the information needed for the transformation:
If you only want to compute economical QR decomposition, remove the corresponding columns of and rows of .
in the free space of below the diagonal and diagonal elements in an additional vector.
