QR Factorization

From Engineering Math

General Gram-Schmidt procedure[edit]

The standard Gram-Schmidt procedure assumes that the input vectors are independent. If we remove the requirement of independence, what we have is the general Gram-Schmidt procedure. Clearly, the in the factorization is not an upper triangular vector anymore, but it has the upper staircase form. Of course, we can always permute the columns via permutation matrices such that the in becomes an upper triangular matrix concatenated to the right with some other matrix.

Full QR Factorization[edit]

Assume that the factorization of is . Note that the set columns of have to be orthonormal, but does not have to be an orthogonal matrix. Sometimes we want to "complete" it to an orthogonal matrix ; this leads to the full QR factorization:

.

This is pretty simple to achieve. Find any matrix such that is full rank (e.g. ) and apply general Gram-Schmidt to . This operation would be called extending the original input set of vectors to an orthonormal basis.

and are very interesting: The ranges and are complementary subspaces, since

  • They are orthogonal, i.e. with an overloaded notation of , we can write
  • Their sum is , i.e. with the over-loaded notation of , .

This can also be written as

and .

Clearly, and, less clearly, [1].

Connection to Least-squares and projection[edit]

The matrix is the projection matrix in the context of least-squares.

References[edit]

  1. Stephen Boyd, EE263 Lecture Notes 4