Gram-Schmidt

Goal: $A=QR$

Summary of the different approaches:

1. Householder/Givens: Find $Q$ such that $Q^{T}A=R$. Orthogonal triangularization.
2. Gram-Schmidt: Find $R$ such that $A{R}^{-1}=Q$. This is preferred when $A$ is tall and thin. This is a triangular orthogonalization process.

Square matrix case

Regular QR factorization with a square matrix:

Thin matrix case

QR factorization of a thin matrix $A$. The matrix $Q$ is square. $R$ is thin. $R$ has 0 below the diagonal. This is a transformation typically obtained using Householder or Givens transformations.

Thin QR factorization. $Q$ is thin and has the same size as $A$. $R$ is upper triangular and square. This is a factorization that can be obtained using Gram-Schmidt.

Steps in the algorithm

The computational strategy is similar to LU and Cholesky.

We start with the product $QR$ in outer-form:

$$A=\sum _k{q}_{,k}{r}_{k,}$$

The first column is simple. We just need it to be of norm 1. Define

$$r_{11}=\Vert a_{,1}{\Vert }_2,q_{,1}=\frac{a_{,1}}{\Vert a_{,1}{\Vert }_2}$$

How do we get $r_{1,}$?

Consider column $j$ of $A$:

$$a_{,j}=r_{1j}{q}_{,1}+\cdots +r_{jj}{q}_{,j}$$

Use the fact that the $q_{,k}$ are orthogonal.

$r_{1j}=q_{,1}^T{a}_{,j}$

We are projecting $a_{,j}$ onto $q_{,1}$.

Then subtract:

$A\leftarrow A-q_{,1}{r}_{1,}$

The first column of $A$ is now zero. Repeat to get all the other columns.

Complete algorithm

Assume $A$ is $m\times n$.

Loop: $k$ from 1 to $n$

• $r_{kk}=\Vert a_{,k}{\Vert }_2$
• $q_{,k}=\Vert a_{,k}{\Vert }_2^{-1}{a}_{,k}$
• $r_{kj}=q_{,k}^T{a}_{,j}$, $j>k$.
• $A\leftarrow A-q_{,k}{r}_{k,}$

Each iteration requires $O(mn)$ flops. So the total computational cost is $O(m{n}^2)$ flops.

QR factorization, QR using Householder transformations, QR using Givens transformations