QR Decomposition

1. Gram Schmidt Process

For with , we define:

Then, for , we have:

This means that, based on , we can constructed a vector that is orthogonal to .

Let for be linearly independent vectors. The Gram-Schmidt process builds (iteratively) an orthonormal basis () for the subspace spanned by . The algorithm is as follows:

1. Find , where .
2. To find , we first find . Then, we set .
3. To find , we first find . Then, we set .
4. And so on...

For the general term where , we have:

2. QR Decomposition

Let be a matrix with linearly independent columns. We can apply Gram-Schmidt to construct an orthonormal basis for the column space of . Then, we can write:

We also notice that if then .

If we let , then we notice that is semi orthogonal: .

Finally, we can write where is an upper triangular matrix. This is the QR Decomposition of :

3. Householder Maps

Suppose we have a hyper-plane going through the origin with unit normal , s.t. . Then, the Householder Matrix is incudes a reflection about .

We can verify that:

• is involutory: .
• is ortho-normal: $H_\vec{u}^T=H_\vec{u}^{-1}
• preserves the euclidean length of vectors: .

These can also be used to calulcate the QR decomposition of a matrix.