Linear AlgebraOrthogonality and Projections8 of 9
Orthogonality and Projections · 8

QR Factorization

Building a target vector from the columns of a matrix AA is difficult when those columns are slanted into each other and have awkward lengths.

1

Why We Want A=QRA = QR

QR factorization rewrites a matrix AA as a matrix QQ of perpendicular, length-11 vectors times an upper-triangular matrix RR that records how to rebuild the original columns of AA.

q1\first{q_1}
q2\second{q_2}
a1\first{a_1}
a2\second{a_2}
Why We Want A = QR
1\htmlClass{lc-mute}{1}
2\htmlClass{lc-mute}{2}
3\htmlClass{lc-mute}{3}
4\htmlClass{lc-mute}{4}
5\htmlClass{lc-mute}{5}
6\htmlClass{lc-mute}{6}
7\htmlClass{lc-mute}{7}
8\htmlClass{lc-mute}{8}
1\htmlClass{lc-mute}{1}
2\htmlClass{lc-mute}{2}
3\htmlClass{lc-mute}{3}
4\htmlClass{lc-mute}{4}
5\htmlClass{lc-mute}{5}
6\htmlClass{lc-mute}{6}
(3,4)\target{(3, 4)}

Rewriting the slanted columns of AA using the perpendicular unit columns of QQ separates the perpendicular directions of the space from the lengths and slants of the original columns:

A\displaystyle A =Q⏟perpendicular unitcolumns q1,q2R⏟weights thatrebuild a1,a2\displaystyle = \underbrace{Q}_{\substack{\text{perpendicular unit} \\ \text{columns } \first{q_1}, \second{q_2}}} \underbrace{R}_{\substack{\text{weights that} \\ \text{rebuild } \first{a_1}, \second{a_2}}}
2

Factoring A=QRA = QR with Gram-Schmidt

To find QQ and RR, we run Gram-Schmidt on the columns of AA and save the lengths we find along the way in RR. After scaling the first column to a unit vector q1\first{q_1}, we subtract a2\second{a_2}'s projection along q1\first{q_1} to get the part of a2\second{a_2} perpendicular to q1\first{q_1}:

leftover\displaystyle \leftover{\text{leftover}} =a2−(q1Ta2)⏟projectionlength r12q1\displaystyle = \second{a_2} - \underbrace{(\first{q_1^T} \second{a_2})}_{\substack{\text{projection} \\ \text{length } \proj{r_{12}}}} \first{q_1}

Let's factor A=[3−6417]A = \begin{bmatrix} \first{3} & \second{-6} \\ \first{4} & \second{17} \end{bmatrix} into A=QRA = QR.

Factoring A = QR with Gram-Schmidt
a1\first{a_1}
a2\second{a_2}
A=[3−6417]q1, q2, R=  ?\begin{aligned} A &= \begin{bmatrix} \first{3} & \second{-6} \\ \first{4} & \second{17} \end{bmatrix} \\[2pt] \first{q_1},\ \second{q_2},\ R &= \;? \end{aligned}
Text solution
Scale a1a_1 to unit length to get q1q_1Find the length r11r_{11} of the first column a1=[34]\first{a_1} = \first{\begin{bmatrix} 3 \\ 4 \end{bmatrix}} and divide a1\first{a_1} by r11r_{11} so our first vector q1\first{q_1} has length 11.
r11=∥a1∥=32+42=25=5,q1=15[34]=[0.60.8]\displaystyle r_{11} = \|\first{a_1}\| = \sqrt{3^2 + 4^2} = \sqrt{25} = 5, \qquad \first{q_1} = \frac{1}{5}\first{\begin{bmatrix} 3 \\ 4 \end{bmatrix}} = \first{\begin{bmatrix} 0.6 \\ 0.8 \end{bmatrix}}
Subtract the projection of a2a_2 onto q1q_1Dot the unit vector q1\first{q_1} with a2=[−617]\second{a_2} = \second{\begin{bmatrix} -6 \\ 17 \end{bmatrix}} to measure the projection length r12\proj{r_{12}} along q1\first{q_1}, then subtract the projection vector r12q1\proj{r_{12}}\first{q_1} from a2\second{a_2} to get the perpendicular leftover piece.
r12\displaystyle \proj{r_{12}} =q1Ta2\displaystyle = \first{q_1^T} \second{a_2} =(0.6)(−6)+(0.8)(17)\displaystyle = (0.6)(-6) + (0.8)(17) =−3.6+13.6\displaystyle = -3.6 + 13.6 =10\displaystyle = \proj{10}
leftover=a2−10q1=[−617]−10[0.60.8]=[−617]−[68]=[−129]\displaystyle \begin{aligned} & \leftover{\text{leftover}} = \second{a_2} - \proj{10}\first{q_1} \\ &\quad = \second{\begin{bmatrix} -6 \\ 17 \end{bmatrix}} - \proj{10}\first{\begin{bmatrix} 0.6 \\ 0.8 \end{bmatrix}} \\ &\quad = \second{\begin{bmatrix} -6 \\ 17 \end{bmatrix}} - \proj{\begin{bmatrix} 6 \\ 8 \end{bmatrix}} = \leftover{\begin{bmatrix} -12 \\ 9 \end{bmatrix}} \end{aligned}
Scale the perpendicular leftover to unit length to get q2q_2Find the length r22\leftover{r_{22}} of the leftover vector and divide by r22\leftover{r_{22}} to get the second perpendicular unit vector q2\second{q_2}.
r22=∥[−129]∥=(−12)2+92=225=15,q2=115[−129]=[−0.80.6]\displaystyle \leftover{r_{22}} = \left\|\leftover{\begin{bmatrix} -12 \\ 9 \end{bmatrix}}\right\| = \sqrt{(-12)^2 + 9^2} = \sqrt{225} = \leftover{15}, \qquad \second{q_2} = \frac{1}{15}\leftover{\begin{bmatrix} -12 \\ 9 \end{bmatrix}} = \second{\begin{bmatrix} -0.8 \\ 0.6 \end{bmatrix}}
Put the unit vectors into QQ and the rebuild weights into RRPut q1\first{q_1} and q2\second{q_2} side by side into QQ, and record how the original columns are rebuilt (a1=5q1+0q2\first{a_1} = 5\first{q_1} + 0\second{q_2} and a2=10q1+15q2\second{a_2} = \proj{10}\first{q_1} + \leftover{15}\second{q_2}) as the columns of RR.
[3−6417]⏟A=[0.6−0.80.80.6]⏟Q[510015]⏟R\displaystyle \underbrace{\begin{bmatrix} \first{3} & \second{-6} \\ \first{4} & \second{17} \end{bmatrix}}_{A} = \underbrace{\begin{bmatrix} \first{0.6} & \second{-0.8} \\ \first{0.8} & \second{0.6} \end{bmatrix}}_{Q} \underbrace{\begin{bmatrix} 5 & \proj{10} \\ 0 & \leftover{15} \end{bmatrix}}_{R}

So the first column of RR rebuilds a1\first{a_1} as 5q15\first{q_1}, and the second column rebuilds a2\second{a_2} from 10q1\proj{10}\first{q_1} (its projection along q1\first{q_1}) plus 15q2\leftover{15}\second{q_2} (its perpendicular leftover along q2\second{q_2}).

q1\first{q_1}
q2\second{q_2}
r12q1=10q1\proj{r_{12}}\first{q_1} = \proj{10}\first{q_1}
a2\second{a_2}
r22q2=15q2\leftover{r_{22}}\second{q_2} = \leftover{15}\second{q_2}

As a2\second{a_2} moves around a fixed a1\first{a_1}, its projection length r12\proj{r_{12}} along q1\first{q_1} and its perpendicular leftover length r22\leftover{r_{22}} along q2\second{q_2} update in the second column of RR, while q1\first{q_1} and the first column of RR stay unchanged.

Drag the second vector around to see how its two right-triangle legs become the second column of R, without changing the first column.
3

Finding RR Directly with QTAQ^T A

If we already have the matrix QQ of perpendicular unit columns (often called orthonormal columns) and want to find RR, we do not need to repeat Gram-Schmidt from scratch.

Finding R Directly with QᵀA
Q=[0.6−0.80.80.6]A=[3−6417]R=  ?\displaystyle \begin{aligned} Q &= \begin{bmatrix} \first{0.6} & \second{-0.8} \\ \first{0.8} & \second{0.6} \end{bmatrix} \\[6pt] A &= \begin{bmatrix} \first{3} & \second{-6} \\ \first{4} & \second{17} \end{bmatrix} \\[6pt] R &= \;? \end{aligned}

Because the columns of QQ have length 11 (q1Tq1=1\first{q_1^T} \first{q_1} = 1, q2Tq2=1\second{q_2^T} \second{q_2} = 1) and are perpendicular to each other (q1Tq2=0\first{q_1^T} \second{q_2} = 0), multiplying QTQQ^T Q takes all of those dot products at once and gives the identity matrix:

QTQ=[q1Tq1q1Tq2q2Tq1q2Tq2]=[1001]=I\displaystyle Q^T Q = \begin{bmatrix} \first{q_1^T} \first{q_1} & \first{q_1^T} \second{q_2} \\ \second{q_2^T} \first{q_1} & \second{q_2^T} \second{q_2} \end{bmatrix} = \begin{bmatrix} 1 & 0 \\ 0 & 1 \end{bmatrix} = I

Multiplying A=QRA = QR on the left by QTQ^T turns QTQQ^T Q into II and gives a direct formula for RR:

QTA=QTQ⏟IR  ⟹  R=QTA=[q1Ta1q1Ta2q2Ta1⏟0q2Ta2]\displaystyle Q^T A = \underbrace{Q^T Q}_{I} R \implies R = Q^T A = \begin{bmatrix} \first{q_1^T} \first{a_1} & \first{q_1^T} \second{a_2} \\ \underbrace{\second{q_2^T} \first{a_1}}_{0} & \second{q_2^T} \second{a_2} \end{bmatrix}

For our matrix A=[3−6417]A = \begin{bmatrix} \first{3} & \second{-6} \\ \first{4} & \second{17} \end{bmatrix}, multiplying QTAQ^T A computes every projection and leftover length in one matrix product:

R=QTA=[0.60.8−0.80.6][3−6417]=[510015]\displaystyle R = Q^T A = \begin{bmatrix} \first{0.6} & \first{0.8} \\ \second{-0.8} & \second{0.6} \end{bmatrix} \begin{bmatrix} \first{3} & \second{-6} \\ \first{4} & \second{17} \end{bmatrix} = \begin{bmatrix} 5 & \proj{10} \\ 0 & \leftover{15} \end{bmatrix}
4

QR Factorization of a Tall Matrix

In data and least squares problems, AA usually has more rows than columns. Let's factor the tall 3×23 \times 2 matrix A=[102623]A = \begin{bmatrix} \first{1} & \second{0} \\ \first{2} & \second{6} \\ \first{2} & \second{3} \end{bmatrix} into A=QRA = QR and see what shapes QQ and RR take.

QR Factorization of a Tall Matrix
A=[102623]q1, q2, R=  ?\begin{aligned} A &= \begin{bmatrix} \first{1} & \second{0} \\ \first{2} & \second{6} \\ \first{2} & \second{3} \end{bmatrix} \\[2pt] \first{q_1},\ \second{q_2},\ R &= \;? \end{aligned}
Text solution
Scale a1a_1 to unit length to get q1q_1Find the length r11r_{11} of the first column a1=[122]\first{a_1} = \first{\begin{bmatrix} 1 \\ 2 \\ 2 \end{bmatrix}} and divide by 33 to get the first 3D unit vector q1\first{q_1}.
r11=∥a1∥=12+22+22=9=3,q1=13[122]=[132323]\displaystyle r_{11} = \|\first{a_1}\| = \sqrt{1^2 + 2^2 + 2^2} = \sqrt{9} = 3, \qquad \first{q_1} = \frac{1}{3}\first{\begin{bmatrix} 1 \\ 2 \\ 2 \end{bmatrix}} = \first{\begin{bmatrix} \tfrac{1}{3} \\ \tfrac{2}{3} \\ \tfrac{2}{3} \end{bmatrix}}
Subtract the projection of a2a_2 onto q1q_1Dot q1\first{q_1} with the second column a2=[063]\second{a_2} = \second{\begin{bmatrix} 0 \\ 6 \\ 3 \end{bmatrix}} to find the projection length r12\proj{r_{12}}, then subtract r12q1\proj{r_{12}}\first{q_1} from a2\second{a_2} to get the perpendicular leftover vector.
r12\displaystyle \proj{r_{12}} =q1Ta2\displaystyle = \first{q_1^T} \second{a_2} =(13)(0)+(23)(6)+(23)(3)\displaystyle = \left(\frac{1}{3}\right)(0) + \left(\frac{2}{3}\right)(6) + \left(\frac{2}{3}\right)(3) =0+4+2\displaystyle = 0 + 4 + 2 =6\displaystyle = \proj{6}
leftover=a2−6q1=[063]−6[132323]=[063]−[244]=[−22−1]\displaystyle \begin{aligned} & \leftover{\text{leftover}} = \second{a_2} - \proj{6}\first{q_1} \\ &\quad = \second{\begin{bmatrix} 0 \\ 6 \\ 3 \end{bmatrix}} - \proj{6}\first{\begin{bmatrix} \tfrac{1}{3} \\ \tfrac{2}{3} \\ \tfrac{2}{3} \end{bmatrix}} \\ &\quad = \second{\begin{bmatrix} 0 \\ 6 \\ 3 \end{bmatrix}} - \proj{\begin{bmatrix} 2 \\ 4 \\ 4 \end{bmatrix}} = \leftover{\begin{bmatrix} -2 \\ 2 \\ -1 \end{bmatrix}} \end{aligned}
Scale the perpendicular leftover to unit length to get q2q_2Find the length r22\leftover{r_{22}} of the leftover vector and divide by 33 to get the second 3D unit vector q2\second{q_2}.
r22=∥[−22−1]∥=(−2)2+22+(−1)2=9=3,q2=13[−22−1]=[−2323−13]\displaystyle \leftover{r_{22}} = \left\|\leftover{\begin{bmatrix} -2 \\ 2 \\ -1 \end{bmatrix}}\right\| = \sqrt{(-2)^2 + 2^2 + (-1)^2} = \sqrt{9} = \leftover{3}, \qquad \second{q_2} = \frac{1}{3}\leftover{\begin{bmatrix} -2 \\ 2 \\ -1 \end{bmatrix}} = \second{\begin{bmatrix} -\tfrac{2}{3} \\ \tfrac{2}{3} \\ -\tfrac{1}{3} \end{bmatrix}}
Put together the tall matrix QQ and the square matrix RRPut the two 3D unit vectors into QQ and their two sets of rebuild weights into RR.
[102623]⏟A (3×2)=[13−23232323−13]⏟Q (3×2)[3603]⏟R (2×2)\displaystyle \underbrace{\begin{bmatrix} \first{1} & \second{0} \\ \first{2} & \second{6} \\ \first{2} & \second{3} \end{bmatrix}}_{A\ (3 \times 2)} = \underbrace{\begin{bmatrix} \first{\tfrac{1}{3}} & \second{-\tfrac{2}{3}} \\ \first{\tfrac{2}{3}} & \second{\tfrac{2}{3}} \\ \first{\tfrac{2}{3}} & \second{-\tfrac{1}{3}} \end{bmatrix}}_{Q\ (3 \times 2)} \underbrace{\begin{bmatrix} 3 & \proj{6} \\ 0 & \leftover{3} \end{bmatrix}}_{R\ (2 \times 2)}

Because each column of AA turns into one unit column of QQ in 3D space, QQ has the exact same tall 3×23 \times 2 shape as AA, while RR is a small 2×22 \times 2 upper-triangular matrix holding the weights that rebuild the two columns.

5

How QR Simplifies Least Squares

When AA is a tall matrix, a target vector b\target{b} usually does not lie in the plane spanned by the columns of AA, so Ax=bAx = \target{b} has no exact solution and we look for the least squares solution x^\hat{x}. Normally, we find x^\hat{x} by solving the Normal Equations ATAx^=ATbA^T A\hat{x} = A^T \target{b}, which requires multiplying out ATAA^T A. That is extra algebra and can also worsen rounding errors on a computer. Factoring A=QRA = QR simplifies the Normal Equations before we do any arithmetic.

How QR Simplifies Least Squares
A=QRATAx^=ATbRx^=  ?\begin{aligned} A &= QR \\ A^T A\hat{x} &= A^T \target{b} \\ R\hat{x} &= \;? \end{aligned}

Substituting A=QRA = QR into the Normal Equations and reversing the order inside the transpose, (QR)T=RTQT(QR)^T = R^T Q^T, puts QTQ=IQ^T Q = I right in the middle so it disappears:

ATAx^=ATb(QR)T(QR)x^=(QR)TbRT(QTQ)⏟IRx^=RTQTbRTRx^=RTQTbRx^=QTb\displaystyle \begin{aligned} A^T A\hat{x} &= A^T \target{b} \\ (QR)^T (QR)\hat{x} &= (QR)^T \target{b} \\ R^T \underbrace{(Q^T Q)}_{I} R\hat{x} &= R^T Q^T \target{b} \\ R^T R\hat{x} &= R^T Q^T \target{b} \\ R\hat{x} &= Q^T \target{b} \end{aligned}

In the final step, because RR is a square upper-triangular matrix with non-zero lengths on its diagonal, RTR^T is invertible and cancels from both sides.

Be careful on a test when asked to justify Rx^=QTbR\hat{x} = Q^T \target{b} for a tall matrix: never start with QRx^=bQR\hat{x} = \target{b} and write Q−1=QTQ^{-1} = Q^T. Because b\target{b} is outside the column space of AA, QRx^QR\hat{x} does not equal b\target{b}, and a tall non-square matrix QQ has no inverse Q−1Q^{-1} even though QTQ=IQ^T Q = I. Always start from the Normal Equations ATAx^=ATbA^T A\hat{x} = A^T \target{b}.

For any target vector b\target{b} in 3D space, its perpendicular shadow on the column space of AA can be built as a rectangle of independent projections (q1Tb)q1+(q2Tb)q2(\first{q_1^T} \target{b})\first{q_1} + (\second{q_2^T} \target{b})\second{q_2} or as a slanted parallelogram x^1a1+x^2a2\first{\hat{x}_1 a_1} + \second{\hat{x}_2 a_2}, and Rx^=QTbR\hat{x} = Q^T \target{b} converts between the two sets of weights.

The shadow's perpendicular coordinates work on their own, while moving the shadow along q2\second{q_2} changes both weights on the slanted columns, because the second column leans into the first.
6

Solving Least Squares with Rx^=QTbR\hat{x} = Q^T b

Now let's use our factorization of A=[102623]A = \begin{bmatrix} \first{1} & \second{0} \\ \first{2} & \second{6} \\ \first{2} & \second{3} \end{bmatrix} to find the least squares solution x^\hat{x} to Ax=bAx = \target{b} for b=[4115]\target{b} = \target{\begin{bmatrix} 4 \\ 11 \\ 5 \end{bmatrix}}.

Solving Least Squares with Rx̂ = Qᵀb
[102623]⏟A=[13−23232323−13]⏟Q[3603]⏟R\displaystyle \underbrace{\begin{bmatrix} \first{1} & \second{0} \\ \first{2} & \second{6} \\ \first{2} & \second{3} \end{bmatrix}}_{A} = \underbrace{\begin{bmatrix} \first{\tfrac{1}{3}} & \second{-\tfrac{2}{3}} \\[5pt] \first{\tfrac{2}{3}} & \second{\tfrac{2}{3}} \\[5pt] \first{\tfrac{2}{3}} & \second{-\tfrac{1}{3}} \end{bmatrix}}_{Q} \underbrace{\begin{bmatrix} 3 & \proj{6} \\ 0 & \leftover{3} \end{bmatrix}}_{R}
b=[4115]x^=  ?\displaystyle \begin{aligned} \target{b} &= \target{\begin{bmatrix} 4 \\ 11 \\ 5 \end{bmatrix}} \\[4pt] \hat{x} &= \;? \end{aligned}
Text solution
Project bb onto the columns of QQ to find QTbQ^T bMultiply QTQ^T by b\target{b} so each row takes the dot product of a unit vector qiq_i with b\target{b}.
QTb=[132323−2323−13][4115]=[4+22+103−8+22−53]=[36393]=[123]\displaystyle \begin{aligned} Q^T \target{b} &= \begin{bmatrix} \first{\tfrac{1}{3}} & \first{\tfrac{2}{3}} & \first{\tfrac{2}{3}} \\ \second{-\tfrac{2}{3}} & \second{\tfrac{2}{3}} & \second{-\tfrac{1}{3}} \end{bmatrix} \target{\begin{bmatrix} 4 \\ 11 \\ 5 \end{bmatrix}} \\ &= \begin{bmatrix} \tfrac{4 + 22 + 10}{3} \\ \tfrac{-8 + 22 - 5}{3} \end{bmatrix} = \begin{bmatrix} \tfrac{36}{3} \\ \tfrac{9}{3} \end{bmatrix} = \proj{\begin{bmatrix} 12 \\ 3 \end{bmatrix}} \end{aligned}
Solve the bottom row of Rx^=QTbR\hat{x} = Q^T b for x^2\hat{x}_2Set up the upper-triangular system [3603][x^1x^2]=[123]\begin{bmatrix} 3 & \proj{6} \\ 0 & \leftover{3} \end{bmatrix}\begin{bmatrix} \first{\hat{x}_1} \\ \second{\hat{x}_2} \end{bmatrix} = \proj{\begin{bmatrix} 12 \\ 3 \end{bmatrix}} and solve the bottom equation first since it only involves x^2\second{\hat{x}_2}.
3x^2\displaystyle \leftover{3}\second{\hat{x}_2} =3  ⟹  x^2\displaystyle = \proj{3} \implies \second{\hat{x}_2} =1\displaystyle = 1
Back-substitute x^2\hat{x}_2 into the top row to find x^1\hat{x}_1Plug x^2=1\second{\hat{x}_2} = 1 into the first row of Rx^=QTbR\hat{x} = Q^T \target{b} and solve for x^1\first{\hat{x}_1}.
3x^1+6(1)=12  ⟹  3x^1=6  ⟹  x^1=2,x^=[21]\displaystyle 3\first{\hat{x}_1} + \proj{6}(1) = \proj{12} \implies 3\first{\hat{x}_1} = 6 \implies \first{\hat{x}_1} = 2, \qquad \hat{x} = \begin{bmatrix} 2 \\ 1 \end{bmatrix}

So x^=[21]\hat{x} = \begin{bmatrix} 2 \\ 1 \end{bmatrix} is the least squares solution: 2a1+1a22\first{a_1} + 1\second{a_2} builds the exact same closest shadow in the column space of AA as 12q1+3q2\proj{12}\first{q_1} + \proj{3}\second{q_2}, without ever forming ATAA^T A.

Key concepts

To factor A=QRA = QR from scratch, run Gram-Schmidt on the columns of AA and put the lengths you find along the way directly into RR. For A=[3−6417]A = \begin{bmatrix} \first{3} & \second{-6} \\ \first{4} & \second{17} \end{bmatrix}, a1=[34]\first{a_1} = \first{\begin{bmatrix} 3 \\ 4 \end{bmatrix}} has length r11=5r_{11} = 5 (giving q1=15a1=[0.60.8]\first{q_1} = \frac{1}{5}\first{a_1} = \first{\begin{bmatrix} 0.6 \\ 0.8 \end{bmatrix}}). Next, a2=[−617]\second{a_2} = \second{\begin{bmatrix} -6 \\ 17 \end{bmatrix}} has projection length r12=q1Ta2=10\proj{r_{12}} = \first{q_1^T} \second{a_2} = \proj{10} along q1\first{q_1}, and its perpendicular leftover a2−10q1=[−129]\second{a_2} - \proj{10}\first{q_1} = \leftover{\begin{bmatrix} -12 \\ 9 \end{bmatrix}} has length r22=15\leftover{r_{22}} = \leftover{15} (giving q2=115[−129]=[−0.80.6]\second{q_2} = \frac{1}{15}\leftover{\begin{bmatrix} -12 \\ 9 \end{bmatrix}} = \second{\begin{bmatrix} -0.8 \\ 0.6 \end{bmatrix}}). If AA is a tall 3×23 \times 2 matrix, QQ keeps the tall 3×23 \times 2 shape of AA while RR is still a 2×22 \times 2 upper-triangular matrix.

Do not run Gram-Schmidt if the matrix QQ with orthonormal columns is already given: because QTQ=IQ^T Q = I, you can find RR in one step by multiplying R=QTAR = Q^T A. And if a problem gives you RR along with parts of AA and QQ, read the columns of A=QRA = QR directly as combinations of the columns of QQ: the first column says a1=r11q1\first{a_1} = r_{11}\first{q_1}, and the second column says a2=r12q1+r22q2\second{a_2} = \proj{r_{12}}\first{q_1} + \leftover{r_{22}}\second{q_2}.

When solving a least squares problem Ax=bAx = \target{b} where A=QRA = QR is already known, do not multiply out ATAA^T A for the Normal Equations. Substituting A=QRA = QR into ATAx^=ATbA^T A\hat{x} = A^T \target{b} simplifies the system to Rx^=QTbR\hat{x} = Q^T \target{b}. Take dot products to find the projection lengths QTbQ^T \target{b}, then solve the upper-triangular system from the bottom row up: for [3603][x^1x^2]=[123]\begin{bmatrix} 3 & \proj{6} \\ 0 & \leftover{3} \end{bmatrix}\begin{bmatrix} \first{\hat{x}_1} \\ \second{\hat{x}_2} \end{bmatrix} = \proj{\begin{bmatrix} 12 \\ 3 \end{bmatrix}}, 3x^2=3\leftover{3}\second{\hat{x}_2} = \proj{3} gives x^2=1\second{\hat{x}_2} = 1, and 3x^1+6(1)=123\first{\hat{x}_1} + \proj{6}(1) = \proj{12} gives x^1=2\first{\hat{x}_1} = 2.

7

Practice

1

Find the QR factorization A=QRA = QR of the matrix A=[42314]A = \begin{bmatrix} \first{4} & \second{2} \\ \first{3} & \second{14} \end{bmatrix}.

Find the length of a1=[43]\first{a_1} = \first{\begin{bmatrix} 4 \\ 3 \end{bmatrix}} to get r11r_{11} and the unit vector q1\first{q_1}; what dot product then measures how far a2=[214]\second{a_2} = \second{\begin{bmatrix} 2 \\ 14 \end{bmatrix}} goes along q1\first{q_1}?

For the first column a1=[43]\first{a_1} = \first{\begin{bmatrix} 4 \\ 3 \end{bmatrix}}, its length is
r11=∥a1∥=42+32=25=5,q1=15[43]=[0.80.6]\displaystyle r_{11} = \|\first{a_1}\| = \sqrt{4^2 + 3^2} = \sqrt{25} = 5, \qquad \first{q_1} = \frac{1}{5}\first{\begin{bmatrix} 4 \\ 3 \end{bmatrix}} = \first{\begin{bmatrix} 0.8 \\ 0.6 \end{bmatrix}}
For the second column a2=[214]\second{a_2} = \second{\begin{bmatrix} 2 \\ 14 \end{bmatrix}}, dot a2\second{a_2} with the unit vector q1\first{q_1} to find the projection length r12\proj{r_{12}}:
r12\displaystyle \proj{r_{12}} =q1Ta2\displaystyle = \first{q_1^T} \second{a_2} =(0.8)(2)+(0.6)(14)\displaystyle = (0.8)(2) + (0.6)(14) =1.6+8.4\displaystyle = 1.6 + 8.4 =10\displaystyle = \proj{10}
(Watch out: be sure to dot a2\second{a_2} with the unit vector q1\first{q_1} and subtract 10q1=[86]\proj{10}\first{q_1} = \proj{\begin{bmatrix} 8 \\ 6 \end{bmatrix}}; dotting with the unscaled column a1\first{a_1} instead gives r12=50\proj{r_{12}} = 50, and subtracting 10a1\proj{10}\first{a_1} instead of 10q1\proj{10}\first{q_1} gives the wrong leftover vector [−38−16]\begin{bmatrix} -38 \\ -16 \end{bmatrix}.)
Subtracting the projection vector 10q1=[86]\proj{10}\first{q_1} = \proj{\begin{bmatrix} 8 \\ 6 \end{bmatrix}} from a2\second{a_2} leaves the perpendicular leftover piece:
leftover=[214]−[86]=[−68]\displaystyle \leftover{\text{leftover}} = \second{\begin{bmatrix} 2 \\ 14 \end{bmatrix}} - \proj{\begin{bmatrix} 8 \\ 6 \end{bmatrix}} = \leftover{\begin{bmatrix} -6 \\ 8 \end{bmatrix}}
This leftover vector has length r22=(−6)2+82=100=10\leftover{r_{22}} = \sqrt{(-6)^2 + 8^2} = \sqrt{100} = \leftover{10}, so dividing by 1010 gives q2=110[−68]=[−0.60.8]\second{q_2} = \frac{1}{10}\leftover{\begin{bmatrix} -6 \\ 8 \end{bmatrix}} = \second{\begin{bmatrix} -0.6 \\ 0.8 \end{bmatrix}}. Putting the columns together gives
Q=[0.8−0.60.60.8],R=[510010]\displaystyle Q = \begin{bmatrix} \first{0.8} & \second{-0.6} \\ \first{0.6} & \second{0.8} \end{bmatrix}, \qquad R = \begin{bmatrix} 5 & \proj{10} \\ 0 & \leftover{10} \end{bmatrix}
2

The tall matrix A=[221−52−4]A = \begin{bmatrix} \first{2} & \second{2} \\ \first{1} & \second{-5} \\ \first{2} & \second{-4} \end{bmatrix} has QR factorization A=QRA = QR, where Q=[232313−2323−13]Q = \begin{bmatrix} \first{\tfrac{2}{3}} & \second{\tfrac{2}{3}} \\ \first{\tfrac{1}{3}} & \second{-\tfrac{2}{3}} \\ \first{\tfrac{2}{3}} & \second{-\tfrac{1}{3}} \end{bmatrix} has orthonormal columns. Give the shape of RR, compute RR directly without repeating Gram-Schmidt, and explain geometrically why the bottom-left entry of RR is 00 and what the two entries in the second column of RR mean for a2\second{a_2}.

Since QQ is already given, how does multiplying A=QRA = QR on the left by QTQ^T isolate RR, and what are the dimensions of QTQ^T and AA?

Because AA and QQ are 3×23 \times 2, RR is a 2×22 \times 2 matrix. Multiplying R=QTAR = Q^T A directly gives
R=QTA=[23132323−23−13][221−52−4]=[3−306]\displaystyle R = Q^T A = \begin{bmatrix} \first{\tfrac{2}{3}} & \first{\tfrac{1}{3}} & \first{\tfrac{2}{3}} \\ \second{\tfrac{2}{3}} & \second{-\tfrac{2}{3}} & \second{-\tfrac{1}{3}} \end{bmatrix} \begin{bmatrix} \first{2} & \second{2} \\ \first{1} & \second{-5} \\ \first{2} & \second{-4} \end{bmatrix} = \begin{bmatrix} 3 & \proj{-3} \\ 0 & \leftover{6} \end{bmatrix}
(Watch out: when computing the bottom-right entry r22=q2Ta2=(23)(2)\leftover{r_{22}} = \second{q_2^T} \second{a_2} = \left(\frac{2}{3}\right)(2) +(−23)(−5)+(−13)(−4){}+ \left(-\frac{2}{3}\right)(-5) + \left(-\frac{1}{3}\right)(-4), watch the negative signs so you don't subtract and get −103-\frac{10}{3}. Diagonal entries of RR are leftover lengths, so they are always positive.)
Geometrically, the bottom-left entry r21=q2Ta1r_{21} = \second{q_2^T} \first{a_1} is 00 because q2\second{q_2} was built to be perpendicular to a1\first{a_1}, so the projection of a1\first{a_1} onto q2\second{q_2} is 00. In the second column of RR, r12=−3\proj{r_{12}} = \proj{-3} is the signed projection length of a2\second{a_2} along q1\first{q_1}, and r22=6\leftover{r_{22}} = \leftover{6} is the length of the leftover part of a2\second{a_2} perpendicular to q1\first{q_1} along q2\second{q_2}, giving R=[3−306]R = \begin{bmatrix} 3 & \proj{-3} \\ 0 & \leftover{6} \end{bmatrix}.
3

A 3×23 \times 2 matrix AA has QR factorization A=QRA = QR, where the first column of QQ is q1=[132323]\first{q_1} = \first{\begin{bmatrix} \tfrac{1}{3} \\ \tfrac{2}{3} \\ \tfrac{2}{3} \end{bmatrix}}, the second column of AA is a2=[75−4]\second{a_2} = \second{\begin{bmatrix} 7 \\ 5 \\ -4 \end{bmatrix}}, and R=[6309]R = \begin{bmatrix} 6 & 3 \\ 0 & 9 \end{bmatrix}. Find the missing first column a1\first{a_1} of AA and the missing second column q2\second{q_2} of QQ.

Write out what each column of RR says about how a1\first{a_1} and a2\second{a_2} are built from q1\first{q_1} and q2\second{q_2}: a1=r11q1+0q2\first{a_1} = r_{11}\first{q_1} + 0\second{q_2} and a2=r12q1+r22q2\second{a_2} = \proj{r_{12}}\first{q_1} + \leftover{r_{22}}\second{q_2}.

From the first column of RR, a1\first{a_1} is built as
a1=6q1+0q2=6[132323]=[244]\displaystyle \first{a_1} = 6\first{q_1} + 0\second{q_2} = 6\first{\begin{bmatrix} \tfrac{1}{3} \\ \tfrac{2}{3} \\ \tfrac{2}{3} \end{bmatrix}} = \first{\begin{bmatrix} 2 \\ 4 \\ 4 \end{bmatrix}}
From the second column of RR, a2=3q1+9q2\second{a_2} = \proj{3}\first{q_1} + \leftover{9}\second{q_2}, so subtracting 3q1\proj{3}\first{q_1} gives 9q2\leftover{9}\second{q_2}:
9q2=a2−3q1=[75−4]−3[132323]=[75−4]−[122]=[63−6]\displaystyle \begin{aligned} \leftover{9}\second{q_2} &= \second{a_2} - \proj{3}\first{q_1} = \second{\begin{bmatrix} 7 \\ 5 \\ -4 \end{bmatrix}} - \proj{3}\first{\begin{bmatrix} \tfrac{1}{3} \\ \tfrac{2}{3} \\ \tfrac{2}{3} \end{bmatrix}} \\ &= \second{\begin{bmatrix} 7 \\ 5 \\ -4 \end{bmatrix}} - \proj{\begin{bmatrix} 1 \\ 2 \\ 2 \end{bmatrix}} = \leftover{\begin{bmatrix} 6 \\ 3 \\ -6 \end{bmatrix}} \end{aligned}
(Watch out: don't stop at [63−6]\leftover{\begin{bmatrix} 6 \\ 3 \\ -6 \end{bmatrix}}. That is the unscaled leftover vector 9q2\leftover{9}\second{q_2} of length 9\leftover{9}, so you still need to divide by r22=9\leftover{r_{22}} = \leftover{9} to make q2\second{q_2} a unit vector.)
Dividing by 99 gives
a1=[244],q2=19[63−6]=[2313−23]\displaystyle \first{a_1} = \first{\begin{bmatrix} 2 \\ 4 \\ 4 \end{bmatrix}}, \qquad \second{q_2} = \frac{1}{9}\leftover{\begin{bmatrix} 6 \\ 3 \\ -6 \end{bmatrix}} = \second{\begin{bmatrix} \tfrac{2}{3} \\ \tfrac{1}{3} \\ -\tfrac{2}{3} \end{bmatrix}}
4

Using the QR factorization A=QRA = QR with Q=[232313−2323−13]Q = \begin{bmatrix} \first{\tfrac{2}{3}} & \second{\tfrac{2}{3}} \\ \first{\tfrac{1}{3}} & \second{-\tfrac{2}{3}} \\ \first{\tfrac{2}{3}} & \second{-\tfrac{1}{3}} \end{bmatrix} and R=[3−306]R = \begin{bmatrix} 3 & -3 \\ 0 & 6 \end{bmatrix}, find the least squares solution x^\hat{x} to Ax=bAx = \target{b} for b=[1112]\target{b} = \target{\begin{bmatrix} 11 \\ 1 \\ 2 \end{bmatrix}}.

Project b\target{b} onto the columns of QQ by computing QTbQ^T \target{b}, then solve the upper-triangular system Rx^=QTbR\hat{x} = Q^T \target{b} starting from the bottom row.

First compute QTbQ^T \target{b} by dotting each column of QQ with b\target{b}:
QTb=[23132323−23−13][1112]=[22+1+4322−2−23]=[273183]=[96]\displaystyle \begin{aligned} Q^T \target{b} &= \begin{bmatrix} \first{\tfrac{2}{3}} & \first{\tfrac{1}{3}} & \first{\tfrac{2}{3}} \\ \second{\tfrac{2}{3}} & \second{-\tfrac{2}{3}} & \second{-\tfrac{1}{3}} \end{bmatrix} \target{\begin{bmatrix} 11 \\ 1 \\ 2 \end{bmatrix}} \\ &= \begin{bmatrix} \tfrac{22 + 1 + 4}{3} \\ \tfrac{22 - 2 - 2}{3} \end{bmatrix} = \begin{bmatrix} \tfrac{27}{3} \\ \tfrac{18}{3} \end{bmatrix} = \proj{\begin{bmatrix} 9 \\ 6 \end{bmatrix}} \end{aligned}
Now set up Rx^=QTbR\hat{x} = Q^T \target{b}:
[3−306][x^1x^2]=[96]\displaystyle \begin{bmatrix} 3 & \proj{-3} \\ 0 & \leftover{6} \end{bmatrix} \begin{bmatrix} \first{\hat{x}_1} \\ \second{\hat{x}_2} \end{bmatrix} = \proj{\begin{bmatrix} 9 \\ 6 \end{bmatrix}}
The bottom row gives 6x^2=6\leftover{6}\second{\hat{x}_2} = \proj{6}, so x^2=1\second{\hat{x}_2} = 1. Substituting x^2=1\second{\hat{x}_2} = 1 into the top row gives
3x^1−3(1)\displaystyle 3\first{\hat{x}_1} - \proj{3}(1) =9  ⟹  3x^1\displaystyle = \proj{9} \implies 3\first{\hat{x}_1} =12  ⟹  x^1\displaystyle = 12 \implies \first{\hat{x}_1} =4\displaystyle = 4
(Watch out: because r12=−3\proj{r_{12}} = \proj{-3} is negative, add 33 to 99 to get 3x^1=123\first{\hat{x}_1} = 12; subtracting 33 by mistake gives 3x^1=63\first{\hat{x}_1} = 6 and the wrong answer [21]\begin{bmatrix} 2 \\ 1 \end{bmatrix}.)
Thus,
x^=[41]\displaystyle \hat{x} = \begin{bmatrix} 4 \\ 1 \end{bmatrix}
5

For a tall 3×23 \times 2 matrix A=QRA = QR, a student writes: "Start with QRx^=bQR\hat{x} = \target{b}, and multiply on the left by Q−1=QTQ^{-1} = Q^T to get Rx^=QTbR\hat{x} = Q^T \target{b}." Identify the two flaws in this argument, then show how Rx^=QTbR\hat{x} = Q^T \target{b} is properly derived from the Normal Equations ATAx^=ATbA^T A\hat{x} = A^T \target{b}.

Check whether Ax=bAx = \target{b} has an exact solution when AA is tall, and whether a non-square 3×23 \times 2 matrix QQ can have an inverse Q−1Q^{-1}; then substitute A=QRA = QR into ATAx^=ATbA^T A\hat{x} = A^T \target{b} and apply (QR)T=RTQT(QR)^T = R^T Q^T.

First, when AA is tall, b\target{b} usually does not lie in the column space of AA, so Ax=bAx = \target{b} has no exact solution and QRx^QR\hat{x} does not equal b\target{b}. Second, QQ is 3×23 \times 2 (not square), so even though QTQ=IQ^T Q = I, QQ has no inverse Q−1Q^{-1}.
To derive the equation properly, substitute A=QRA = QR into the Normal Equations ATAx^=ATbA^T A\hat{x} = A^T \target{b}:
(QR)T(QR)x^\displaystyle (QR)^T (QR)\hat{x} =(QR)Tb\displaystyle = (QR)^T \target{b}
(Watch out: remember to reverse the order when taking the transpose of a product so (QR)T(QR)^T becomes RTQTR^T Q^T; writing QTRT(QR)x^Q^T R^T (QR)\hat{x} puts RTQR^T Q in the middle instead of QTQQ^T Q.)
Expanding the transposes gives
RT(QTQ)Rx^\displaystyle R^T (Q^T Q) R\hat{x} =RTQTb\displaystyle = R^T Q^T \target{b}
Since QTQ=IQ^T Q = I, this simplifies to RTRx^=RTQTbR^T R\hat{x} = R^T Q^T \target{b}, and canceling the invertible square matrix RTR^T from both sides gives
Rx^\displaystyle R\hat{x} =QTb\displaystyle = Q^T \target{b}