Building a target vector from the columns of a matrix A is difficult when those columns are slanted into each other and have awkward lengths.
1
Why We Want A=QR
QR factorization rewrites a matrix A as a matrix Q of perpendicular, length-1 vectors times an upper-triangular matrix R that records how to rebuild the original columns of A.
Why We Want A = QR
Rewriting the slanted columns of A using the perpendicular unit columns of Q separates the perpendicular directions of the space from the lengths and slants of the original columns:
To find Q and R, we run Gram-Schmidt on the columns of A and save the lengths we find along the way in R. After scaling the first column to a unit vector q1, we subtract a2's projection along q1 to get the part of a2 perpendicular to q1:
leftover=a2−projectionlength r12(q1Ta2)q1
Let's factor A=[34−617] into A=QR.
Factoring A = QR with Gram-Schmidt
Text solution
Scale a1 to unit length to get q1Find the length r11 of the first column a1=[34] and divide a1 by r11 so our first vector q1 has length 1.
r11=∥a1∥=32+42=25=5,q1=51[34]=[0.60.8]
Subtract the projection of a2 onto q1Dot the unit vector q1 with a2=[−617] to measure the projection length r12 along q1, then subtract the projection vector r12q1 from a2 to get the perpendicular leftover piece.
Scale the perpendicular leftover to unit length to get q2Find the length r22 of the leftover vector and divide by r22 to get the second perpendicular unit vector q2.
Put the unit vectors into Q and the rebuild weights into RPut q1 and q2 side by side into Q, and record how the original columns are rebuilt (a1=5q1+0q2 and a2=10q1+15q2) as the columns of R.
A[34−617]=Q[0.60.8−0.80.6]R[501015]
So the first column of R rebuilds a1 as 5q1, and the second column rebuilds a2 from 10q1 (its projection along q1) plus 15q2 (its perpendicular leftover along q2).
As a2 moves around a fixed a1, its projection length r12 along q1 and its perpendicular leftover length r22 along q2 update in the second column of R, while q1 and the first column of R 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 R Directly with QTA
If we already have the matrix Q of perpendicular unit columns (often called orthonormal columns) and want to find R, we do not need to repeat Gram-Schmidt from scratch.
Finding R Directly with QᵀA
QAR=[0.60.8−0.80.6]=[34−617]=?
Because the columns of Q have length 1 (q1Tq1=1,q2Tq2=1) and are perpendicular to each other (q1Tq2=0), multiplying QTQ takes all of those dot products at once and gives the identity matrix:
QTQ=[q1Tq1q2Tq1q1Tq2q2Tq2]=[1001]=I
Multiplying A=QR on the left by QT turns QTQ into I and gives a direct formula for R:
For our matrix A=[34−617], multiplying QTA computes every projection and leftover length in one matrix product:
R=QTA=[0.6−0.80.80.6][34−617]=[501015]
4
QR Factorization of a Tall Matrix
In data and least squares problems, A usually has more rows than columns. Let's factor the tall 3×2 matrix A=122063 into A=QR and see what shapes Q and R take.
QR Factorization of a Tall Matrix
Text solution
Scale a1 to unit length to get q1Find the length r11 of the first column a1=122 and divide by 3 to get the first 3D unit vector q1.
Subtract the projection of a2 onto q1Dot q1 with the second column a2=063 to find the projection length r12, then subtract r12q1 from a2 to get the perpendicular leftover vector.
Scale the perpendicular leftover to unit length to get q2Find the length r22 of the leftover vector and divide by 3 to get the second 3D unit vector q2.
Because each column of A turns into one unit column of Q in 3D space, Q has the exact same tall 3×2 shape as A, while R is a small 2×2 upper-triangular matrix holding the weights that rebuild the two columns.
5
How QR Simplifies Least Squares
When A is a tall matrix, a target vector b usually does not lie in the plane spanned by the columns of A, so Ax=b has no exact solution and we look for the least squares solution x^. Normally, we find x^ by solving the Normal Equations ATAx^=ATb, which requires multiplying out ATA. That is extra algebra and can also worsen rounding errors on a computer. Factoring A=QR simplifies the Normal Equations before we do any arithmetic.
How QR Simplifies Least Squares
a1
a2
b
AATAx^Rx^=QR=ATb=?
Substituting A=QR into the Normal Equations and reversing the order inside the transpose, (QR)T=RTQT, puts QTQ=I right in the middle so it disappears:
In the final step, because R is a square upper-triangular matrix with non-zero lengths on its diagonal, RT is invertible and cancels from both sides.
Be careful on a test when asked to justify Rx^=QTb for a tall matrix: never start with QRx^=b and write Q−1=QT. Because b is outside the column space of A,QRx^ does not equal b, and a tall non-square matrix Q has no inverse Q−1 even though QTQ=I. Always start from the Normal Equations ATAx^=ATb.
For any target vector b in 3D space, its perpendicular shadow on the column space of A can be built as a rectangle of independent projections (q1Tb)q1+(q2Tb)q2 or as a slanted parallelogram x^1a1+x^2a2, and Rx^=QTb converts between the two sets of weights.
The shadow's perpendicular coordinates work on their own, while moving the shadow along q2 changes both weights on the slanted columns, because the second column leans into the first.
6
Solving Least Squares with Rx^=QTb
Now let's use our factorization of A=122063 to find the least squares solution x^ to Ax=b for b=4115.
Solve the bottom row of Rx^=QTb for x^2Set up the upper-triangular system [3063][x^1x^2]=[123] and solve the bottom equation first since it only involves x^2.
3x^2=3⟹x^2=1
Back-substitute x^2 into the top row to find x^1Plug x^2=1 into the first row of Rx^=QTb and solve for x^1.
3x^1+6(1)=12⟹3x^1=6⟹x^1=2,x^=[21]
So x^=[21] is the least squares solution: 2a1+1a2 builds the exact same closest shadow in the column space of A as 12q1+3q2, without ever forming ATA.
Key concepts
To factor A=QR from scratch, run Gram-Schmidt on the columns of A and put the lengths you find along the way directly into R. For A=[34−617],a1=[34] has length r11=5 (giving q1=51a1=[0.60.8]). Next, a2=[−617] has projection length r12=q1Ta2=10 along q1, and its perpendicular leftover a2−10q1=[−129] has length r22=15 (giving q2=151[−129]=[−0.80.6]). If A is a tall 3×2 matrix, Q keeps the tall 3×2 shape of A while R is still a 2×2 upper-triangular matrix.
Do not run Gram-Schmidt if the matrix Q with orthonormal columns is already given: because QTQ=I, you can find R in one step by multiplying R=QTA. And if a problem gives you R along with parts of A and Q, read the columns of A=QR directly as combinations of the columns of Q: the first column says a1=r11q1, and the second column says a2=r12q1+r22q2.
When solving a least squares problem Ax=b where A=QR is already known, do not multiply out ATA for the Normal Equations. Substituting A=QR into ATAx^=ATb simplifies the system to Rx^=QTb. Take dot products to find the projection lengths QTb, then solve the upper-triangular system from the bottom row up: for [3063][x^1x^2]=[123],3x^2=3 gives x^2=1, and 3x^1+6(1)=12 gives x^1=2.
7
Practice
1
Find the QR factorization A=QR of the matrix A=[43214].
Find the length of a1=[43] to get r11 and the unit vector q1; what dot product then measures how far a2=[214] goes along q1?
For the first column a1=[43], its length is
r11=∥a1∥=42+32=25=5,q1=51[43]=[0.80.6]
For the second column a2=[214], dot a2 with the unit vector q1 to find the projection length r12:
r12=q1Ta2=(0.8)(2)+(0.6)(14)=1.6+8.4=10
(Watch out: be sure to dot a2 with the unit vector q1 and subtract 10q1=[86]; dotting with the unscaled column a1 instead gives r12=50, and subtracting 10a1 instead of 10q1 gives the wrong leftover vector [−38−16].)
Subtracting the projection vector 10q1=[86] from a2 leaves the perpendicular leftover piece:
leftover=[214]−[86]=[−68]
This leftover vector has length r22=(−6)2+82=100=10, so dividing by 10 gives q2=101[−68]=[−0.60.8]. Putting the columns together gives
Q=[0.80.6−0.60.8],R=[501010]
2
The tall matrix A=2122−5−4 has QR factorization A=QR, where Q=32313232−32−31 has orthonormal columns. Give the shape of R, compute R directly without repeating Gram-Schmidt, and explain geometrically why the bottom-left entry of R is 0 and what the two entries in the second column of R mean for a2.
Since Q is already given, how does multiplying A=QR on the left by QT isolate R, and what are the dimensions of QT and A?
Because A and Q are 3×2,R is a 2×2 matrix. Multiplying R=QTA directly gives
(Watch out: when computing the bottom-right entry r22=q2Ta2=(32)(2)+(−32)(−5)+(−31)(−4), watch the negative signs so you don't subtract and get −310. Diagonal entries of R are leftover lengths, so they are always positive.)
Geometrically, the bottom-left entry r21=q2Ta1 is 0 because q2 was built to be perpendicular to a1, so the projection of a1 onto q2 is 0. In the second column of R,r12=−3 is the signed projection length of a2 along q1, and r22=6 is the length of the leftover part of a2 perpendicular to q1 along q2, giving R=[30−36].
3
A 3×2 matrix A has QR factorization A=QR, where the first column of Q is q1=313232, the second column of A is a2=75−4, and R=[6039]. Find the missing first column a1 of A and the missing second column q2 of Q.
Write out what each column of R says about how a1 and a2 are built from q1 and q2:a1=r11q1+0q2 and a2=r12q1+r22q2.
From the first column of R,a1 is built as
a1=6q1+0q2=6313232=244
From the second column of R,a2=3q1+9q2, so subtracting 3q1 gives 9q2:
(Watch out: don't stop at 63−6. That is the unscaled leftover vector 9q2 of length 9, so you still need to divide by r22=9 to make q2 a unit vector.)
Dividing by 9 gives
a1=244,q2=9163−6=3231−32
4
Using the QR factorization A=QR with Q=32313232−32−31 and R=[30−36], find the least squares solution x^ to Ax=b for b=1112.
Watch out: because r12=−3 is negative, add 3 to 9 to get 3x^1=12; subtracting 3 by mistake gives 3x^1=6 and the wrong answer [21].
Project b onto the columns of Q by computing QTb, then solve the upper-triangular system Rx^=QTb starting from the bottom row.
First compute QTb by dotting each column of Q with b:
The bottom row gives 6x^2=6, so x^2=1. Substituting x^2=1 into the top row gives
3x^1−3(1)=9⟹3x^1=12⟹x^1=4
(Watch out: because r12=−3 is negative, add 3 to 9 to get 3x^1=12; subtracting 3 by mistake gives 3x^1=6 and the wrong answer [21].)
Thus,
x^=[41]
5
For a tall 3×2 matrix A=QR, a student writes: "Start with QRx^=b, and multiply on the left by Q−1=QT to get Rx^=QTb." Identify the two flaws in this argument, then show how Rx^=QTb is properly derived from the Normal Equations ATAx^=ATb.
Check whether Ax=b has an exact solution when A is tall, and whether a non-square 3×2 matrix Q can have an inverse Q−1; then substitute A=QR into ATAx^=ATb and apply (QR)T=RTQT.
First, when A is tall, b usually does not lie in the column space of A, so Ax=b has no exact solution and QRx^ does not equal b. Second, Q is 3×2 (not square), so even though QTQ=I,Q has no inverse Q−1.
To derive the equation properly, substitute A=QR into the Normal Equations ATAx^=ATb:
(QR)T(QR)x^=(QR)Tb
(Watch out: remember to reverse the order when taking the transpose of a product so (QR)T becomes RTQT; writing QTRT(QR)x^ puts RTQ in the middle instead of QTQ.)
Expanding the transposes gives
RT(QTQ)Rx^=RTQTb
Since QTQ=I, this simplifies to RTRx^=RTQTb, and canceling the invertible square matrix RT from both sides gives