# James Gregson's Website

## QR Decomposition Notes

I find this easier to reason through by writing out a small 3-column version explicitly:

\begin{equation*} \begin{bmatrix} A_{*0} & A_{*1} & A_{*2} \end{bmatrix} = \begin{bmatrix} Q_{*0} & Q_{*1} & Q_{*2} \end{bmatrix} \begin{bmatrix} R_{00} & R_{01} & R_{02} \\ & R_{11} & R_{12} \\ & & R_{22} \end{bmatrix} \end{equation*}

which gives:

\begin{align*} &A_{*0} = Q_{*0} R_{00} \\ &A_{*1} = Q_{*0} R_{01} + Q_{*1} R_{11} \\ &A_{*2} = Q_{*0} R_{02} + Q_{*1} R_{12} + Q_{*2} R_{22} \end{align*}

From this and the orthonormal properties of $$Q$$, the meaning of the $$R_{ji}$$ values are clear, the projection of the $$i$$'th column of $$A$$ onto the $$j$$'th column of $$Q$$. These allows fixing the values of $$R_{ji}$$ and norms of $$Q_{*i}$$:

• $$Q_{*i}^T Q_{*j} = 0, \forall i \neq j$$: columns of $$Q$$ are orthogonal so each $$R_{j*}$$ value must account for entire parallel component of $$A_{*j}$$ onto each column of $$Q$$.
• $$\|Q_{*i}\|_2 = 1, \forall i$$: constrains $$\|Q_{*i}\|$$ and corresponding $$R_{ji}$$ values.

Therefore:

• $$R_{00} = \|A_{*0}\|_2$$ and $$Q_{*0} = A_{*0}/R_{00}$$
• $$R_{01} = Q_{*0}^T A_{*1}$$, $$s_1 = A_{*1} - R_{01} Q_{*0}$$, $$R_{11} = \|s_1\|_2$$ $$Q_{*1} = s_1/R_{11}$$
• $$R_{02} = Q_{*0}^T A_{*2},~R_{12} = Q_{*1}^T A_{*2}, s_2 = A_{*2} - R_{02} Q_{*0} - R_{12} Q_{*1}, R_{22} = \| s_2 \|_2, Q_{*2} = s_2/R_{22}$$

or in general:

• $$R_{ji} = Q_{*j}^T A_{*i}, \forall j < i$$
• $$s_{i} = A_{*i} - \sum_j R_{ji} Q_{*j}$$
• $$R_{ii} = \| s_{i} \|_2, Q_{*i} = s_i/R_{ii}$$

and in python:

def qr_gs( A, inplace=True ):
'''Decompose A into Q*R with Q orthonormal and R upper triangular using classical Gram-Schmidt (unstable)'''
A = A if inplace else A.copy()
R = np.zeros((A.shape[1],A.shape[1]))
for i in range( A.shape[1] ):
for j in range(i):
R[j,i] = np.sum(A[:,j]*A[:,i])
A[:,i] -= R[j,i]*A[:,j]
R[i,i] = np.linalg.norm(A[:,i])
A[:,i] /= R[i,i]
return A,R


The form above generates $$Q$$ column by column but has stability issues due to the use of classical Gram-Schmidt. It can be improved by replacing classical Gram-Schmidt with modified Gram-Schmidt:

def qr_mgs( A, inplace=True ):
'''Decompose A into Q*R with Q orthonormal and R upper triangular using modified Gram-Schmidt

Assumes columns of A are linearly independent.
'''
A = A if inplace else A.copy()
R = np.zeros((A.shape[1],A.shape[1]))
for i in range( A.shape[1] ):
R[i,i] = np.linalg.norm(A[:,i])
A[:,i] /= R[i,i]
for j in range(i+1,A.shape[1]):
R[i,j] = np.dot(A[:,j],A[:,i])
A[:,j] -= R[i,j]*A[:,i]
return A,R


The inner loop of this can be replaced entirely with vectorization in python but the above form gives a reasonable starting point for porting to another language like C or C++. These implementations should also check for $$R_{ii} = 0$$ which indicate a rank deficient system.