QR decomposition and Gram-Schmidt

Building an orthonormal basis

Orthonormal columns are the best-behaved columns a matrix can have: $Q^{T}Q=I$ , so $Q$ keeps lengths and angles and never amplifies errors. Gram-Schmidt turns any independent columns $\mathbf{a}_1,\dots,\mathbf{a}_n$ into orthonormal ones: take $\mathbf{q}_1=\mathbf{a}_1/\|\mathbf{a}_1\|$ , then for each next column subtract its projections onto the $\mathbf{q}$ 's found so far and normalise what remains.

A=QR,\qquad R_{ij}=\mathbf{q}_i\cdot\mathbf{a}_j\ (i\le j),\qquad \mathbf{q}_j=\frac{\mathbf{a}_j-\sum_{i<j}R_{ij}\mathbf{q}_i}{R_{jj}}

(1)

Recording the numbers you used gives the QR decomposition: $Q$ has the orthonormal columns and $R$ is upper triangular, with $R_{ij}=\mathbf{q}_i\cdot\mathbf{a}_j$ and the lengths $R_{jj}$ on its diagonal. For least squares, $\|A\mathbf{x}-\mathbf{b}\|=\|QR\mathbf{x}-\mathbf{b}\|$ is minimised by $R\hat{\mathbf{x}}=Q^{T}\mathbf{b}$ , a triangular system solved by back substitution, without ever forming $A^{T}A$ . This is why $\kappa(R)=\kappa(A)$ instead of $\kappa(A)^2$ .

Gram-Schmidt on two columnsTake

A=\begin{pmatrix}3&1\\4&2\end{pmatrix}

, with columns

\mathbf{a}_1=(3,4)

and

\mathbf{a}_2=(1,2)

. Then

R_{11}=\|\mathbf{a}_1\|=5

and

\mathbf{q}_1=(0.6,\,0.8)

. Next

R_{12}=\mathbf{q}_1\cdot\mathbf{a}_2=2.2

, and

\mathbf{a}_2-2.2\,\mathbf{q}_1=(-0.32,\,0.24)

has length

R_{22}=0.4

, so

\mathbf{q}_2=(-0.8,\,0.6)

. Thus

Q=\begin{pmatrix}0.6&-0.8\\0.8&0.6\end{pmatrix}

and

R=\begin{pmatrix}5&2.2\\0&0.4\end{pmatrix}

. Check:

\det A=2=\det R

Q: orthonormal columns, $Q^{T}Q=I$ , no error amplification.
R: upper triangular; its diagonal holds the lengths left after removing earlier directions.
Modified Gram-Schmidt (or Householder reflections in libraries) keeps $Q$ orthogonal in floating point; the textbook version loses orthogonality on nearly dependent columns.

Why libraries use QR for regressionRegressors in finance are often nearly collinear (many correlated factors, polynomial features). The normal equations would square that condition number and silently return garbage, while QR (or the SVD) copes. That is the algorithm behind the least squares routines of NumPy and statsmodels, and the one you will build in the capstone.

Lab · what's graded

The first diagonal entry10 pts
The matrix Q20 pts
The matrix R20 pts
A determinant from R15 pts
Least squares with QR15 pts
Why QR is more accurate20 pts

Building an orthonormal basis

A=QR,\qquad R_{ij}=\mathbf{q}_i\cdot\mathbf{a}_j\ (i\le j),\qquad \mathbf{q}_j=\frac{\mathbf{a}_j-\sum_{i<j}R_{ij}\mathbf{q}_i}{R_{jj}}

(1)

Gram-Schmidt on two columnsTake

A=\begin{pmatrix}3&1\\4&2\end{pmatrix}

, with columns

\mathbf{a}_1=(3,4)

and

\mathbf{a}_2=(1,2)

. Then

R_{11}=\|\mathbf{a}_1\|=5

and

\mathbf{q}_1=(0.6,\,0.8)

. Next

R_{12}=\mathbf{q}_1\cdot\mathbf{a}_2=2.2

, and

\mathbf{a}_2-2.2\,\mathbf{q}_1=(-0.32,\,0.24)

has length

R_{22}=0.4

, so

\mathbf{q}_2=(-0.8,\,0.6)

. Thus

Q=\begin{pmatrix}0.6&-0.8\\0.8&0.6\end{pmatrix}

and

R=\begin{pmatrix}5&2.2\\0&0.4\end{pmatrix}

. Check:

\det A=2=\det R

Q: orthonormal columns, $Q^{T}Q=I$ , no error amplification.
R: upper triangular; its diagonal holds the lengths left after removing earlier directions.
Modified Gram-Schmidt (or Householder reflections in libraries) keeps $Q$ orthogonal in floating point; the textbook version loses orthogonality on nearly dependent columns.

Lab · what's graded

The first diagonal entry10 pts
The matrix Q20 pts
The matrix R20 pts
A determinant from R15 pts
Least squares with QR15 pts
Why QR is more accurate20 pts

QR decomposition and Gram-Schmidt

Building an orthonormal basis

Lab · what's graded

Log in to run your code.

QR decomposition and Gram-Schmidt

Building an orthonormal basis

Lab · what's graded

Log in to run your code.