MAT 102 Linear Algebra · DSE · Intake 2/1 · Dr. Ronobir Chandra Sarker
Orthogonality — Part 3: Least squares and orthonormal bases
Lecture notes on sections 4.3 and 4.4 of Strang, Introduction to Linear Algebra. Read with pen and paper beside you, work each example yourself before reading its solution, and do every exercise before opening the answer.
Fitting data. Measurements never lie exactly on a straight line. Least squares chooses the line that fits best. It is the projection of Part 2 applied to data, it is the basis of linear regression, and it is one of the most used calculations in all of science.
A convenient basis. When the basis vectors are perpendicular to each other and have length \(1\) (an orthonormal basis), the coefficient of each basis vector is a single dot product, so no system of equations has to be solved. The Gram–Schmidt process produces such a basis from any basis, and it leads to the factorization \(A = QR\) that computers use for least squares.
What you need
From Part 2: the normal equations \(A\T A\hat{\vb x} = A\T\vb b\), the projection \(\vb p = A\hat{\vb x}\), the error \(\vb e = \vb b - \vb p\) with \(A\T\vb e = \vb 0\), and projection onto a line, \(\hat x = \vb a\T\vb b / \vb a\T\vb a\).
From Part 1: orthogonal vectors (dot product zero), lengths, and the column space.
From Chapter 2: elimination and back substitution for two equations in two unknowns; the inverse of a matrix.
Notation
Symbol
Meaning
\((t_i, b_i)\), \(m\)
the data points (time, measurement) and how many there are
\(C\), \(D\)
the intercept and slope of the line \(b = C + Dt\)
\(\sum t_i\)
\(t_1 + t_2 + \cdots + t_m\)
\(p_i\), \(e_i\), \(E\)
height of the line at \(t_i\); error \(b_i - p_i\); total squared error \(\sum e_i^2\)
\(\vb q_1, \vb q_2, \dots\); \(Q\)
orthonormal vectors; the matrix with them as columns
\(\vb A, \vb B, \vb C\); \(R\)
the orthogonal (not yet unit) vectors in Gram–Schmidt; the triangular factor in \(A = QR\)
1Least squares (4.3)
Suppose we measure a quantity \(b\) at several times \(t\) and we believe that \(b\) grows along a straight line \(b = C + Dt\). Because of measurement noise no line passes through all the points. Which line is best? This is the least-squares problem, and we will see that it is a projection in disguise.
Historical note. In 1801 the newly discovered asteroid Ceres was lost behind the Sun after only forty days of observations. The 24-year-old Gauss used least squares on those noisy observations to predict where it would reappear, and it reappeared exactly there. Today the same method is called linear regression; it is the first method taught in statistics and machine learning, and a GPS receiver solves a least-squares problem every second.
Why there is no exact solution
With \(m\) data points \((t_i, b_i)\) the line \(b = C + Dt\) must satisfy \(m\) equations in only two unknowns:
\[ C + Dt_1 = b_1,\quad C + Dt_2 = b_2,\quad \dots,\quad C + Dt_m = b_m, \]
that is \(A\vb x = \vb b\) with
\[ A = \begin{bmatrix} 1 & t_1 \\ 1 & t_2 \\ \vdots & \vdots \\ 1 & t_m \end{bmatrix}, \qquad \vb x = \begin{bmatrix} C \\ D \end{bmatrix}. \]
The first column is all ones because it multiplies \(C\); the second column holds the times because they multiply \(D\). The matrix is tall and thin, its two columns span only a plane inside \(\R^m\), and a noisy \(\vb b\) lies outside that plane. So \(A\vb x = \vb b\) has no solution. We cannot make the error \(\vb e = \vb b - A\vb x\) zero, but we can make it as short as possible.
Definition 1.1. The least-squares solution \(\hat{\vb x}\) of \(A\vb x = \vb b\) is the vector that makes the squared length of the error as small as possible:
\[ E = \nrm{A\vb x - \vb b}^2 = e_1^2 + e_2^2 + \cdots + e_m^2 \quad\text{is minimised at } \vb x = \hat{\vb x}. \]
For a line fit, \(e_i = b_i - (C + Dt_i)\) is the vertical distance from the \(i\)-th point to the line, and \(E\) is the sum of their squares.
Theorem 1.2. The least-squares solution satisfies the normal equations
\[ A\T A\,\hat{\vb x} = A\T\vb b. \]
Proof. As \(\vb x\) varies, \(A\vb x\) runs through every point of the column space \(\mathbf C(A)\). Minimising \(\nrm{A\vb x - \vb b}\) therefore means finding the point of \(\mathbf C(A)\) closest to \(\vb b\). By Part 2 (projection onto a subspace) that point is the projection \(\vb p = A\hat{\vb x}\), and the error \(\vb e = \vb b - A\hat{\vb x}\) is perpendicular to every column of \(A\): \(A\T(\vb b - A\hat{\vb x}) = \vb 0\), which is \(A\T A\hat{\vb x} = A\T\vb b\). ∎
Remark. Calculus gives the same equations: setting the partial derivatives \(\partial E/\partial C\) and \(\partial E/\partial D\) equal to zero produces exactly the two normal equations. The book shows both arguments.
Fitting a straight line
The normal equations for \(b = C + Dt\).
\[ A\T A = \begin{bmatrix} m & \sum t_i \\ \sum t_i & \sum t_i^2 \end{bmatrix}, \qquad A\T\vb b = \begin{bmatrix} \sum b_i \\ \sum t_i b_i \end{bmatrix}, \qquad \begin{bmatrix} m & \sum t_i \\ \sum t_i & \sum t_i^2 \end{bmatrix}\begin{bmatrix} C \\ D \end{bmatrix} = \begin{bmatrix} \sum b_i \\ \sum t_i b_i \end{bmatrix}. \]
Only five numbers are needed: \(m\), \(\sum t_i\), \(\sum t_i^2\), \(\sum b_i\), \(\sum t_i b_i\).
Method 1.1.
Write the \(m\) equations \(C + Dt_i = b_i\), and so \(A\) and \(\vb b\).
Compute the five sums and write \(A\T A\) and \(A\T\vb b\).
Solve the normal equations by elimination: this gives \(C\) and \(D\), hence the best line.
Compute the heights on the line \(p_i = C + Dt_i\), the errors \(e_i = b_i - p_i\), and the minimum \(E = \sum e_i^2\).
Check: \(\sum e_i = 0\) and \(\sum t_i e_i = 0\) (the error is perpendicular to both columns of \(A\)).
Example 1.1 (book). Find the closest line to the points \((0, 6)\), \((1, 0)\), \((2, 0)\).
The equations \(C + 0D = 6\), \(C + 1D = 0\), \(C + 2D = 0\) give
\[ A = \begin{bmatrix} 1 & 0 \\ 1 & 1 \\ 1 & 2 \end{bmatrix}, \qquad \vb b = \begin{bmatrix} 6 \\ 0 \\ 0 \end{bmatrix}. \]
No line passes through all three points, so we look for the least-squares solution.
Figure 1.1 — the least-squares line of Example 1.1. Black dots: the data \(b_i\). Teal dots: the heights \(p_i = 5 - 3t_i\) on the best line. Red: the vertical errors \(e_i = b_i - p_i\). No line passes through all three data points; this line makes \(E = e_1^2 + e_2^2 + e_3^2 = 6\) as small as possible.
Example 1.2 (book, Problem Set 4.3). Fit \(b = C + Dt\) to \(b = 0, 8, 8, 20\) at \(t = 0, 1, 3, 4\).
Example 1.3 (a horizontal line). Fit \(b = C\) (no slope) to measurements \(b_1, \dots, b_m\).
Now \(A\) is a single column of ones, so \(A\T A = m\) and \(A\T\vb b = \sum b_i\). The normal equation \(mC = \sum b_i\) gives
\[ C = \frac{b_1 + b_2 + \cdots + b_m}{m}, \]
the average of the measurements. The mean is a least-squares fit, and therefore also a projection.
Exercise 1. Find the least-squares line through \((1, 2)\), \((2, 0)\), \((3, 4)\). Give \(C\) and \(D\), the heights, the errors, \(E\), and the checks.
The coordinate axes \((1,0,0)\), \((0,1,0)\), \((0,0,1)\) are perpendicular to each other and have length \(1\). That is why coordinates are so easy to read off: the component of \(\vb b\) along an axis is a single dot product. This section shows that every subspace has a basis of this kind, how to construct it, and why it makes least squares easy.
Definition 2.1. Vectors \(\vb q_1, \dots, \vb q_n\) are orthonormal when they are perpendicular to each other and each has length \(1\):
\[ \vb q_i\T\vb q_j = \begin{cases} 0 & i \ne j \quad\text{(orthogonal)} \\ 1 & i = j \quad\text{(unit length)} \end{cases} \]
If \(Q\) is the matrix with the \(\vb q\)'s as columns, these \(n^2\) conditions are the single matrix equation
\[ Q\T Q = I, \]
because the \((i, j)\) entry of \(Q\T Q\) is exactly \(\vb q_i\T\vb q_j\).
Definition 2.2. A square matrix with orthonormal columns is called an orthogonal matrix. For such a matrix \(Q\T Q = I\) says that \(Q\T\) is the inverse:
\[ Q^{-1} = Q\T. \]
Example 2.1. Three orthogonal matrices.
Rotation by \(\theta\): \(Q = \begin{bmatrix} \cos\theta & -\sin\theta \\ \sin\theta & \cos\theta \end{bmatrix}\). The columns have dot product \(-\cos\theta\sin\theta + \sin\theta\cos\theta = 0\) and each has squared length \(\cos^2\theta + \sin^2\theta = 1\).
Permutation: \(Q = \begin{bmatrix} 0 & 1 \\ 1 & 0 \end{bmatrix}\) swaps the two entries of a vector. Its columns are the coordinate axes in a different order.
A \(3 \times 3\) example: \(Q = \dfrac13\begin{bmatrix} 1 & 2 & 2 \\ 2 & 1 & -2 \\ 2 & -2 & 1 \end{bmatrix}\). The integer columns \((1,2,2)\), \((2,1,-2)\), \((2,-2,1)\) have dot products \(2 + 2 - 4 = 0\), \(2 - 4 + 2 = 0\), \(4 - 2 - 2 = 0\), and each has squared length \(9\). Dividing by \(3\) makes them unit vectors.
Example 2.2 (book, 4.4 #1). Classify each pair as independent only, orthogonal, or orthonormal: \((1,0)\) and \((-1,1)\); \((.6,.8)\) and \((.4,-.3)\); \((\cos\theta, \sin\theta)\) and \((-\sin\theta, \cos\theta)\).
\((1,0)\cdot(-1,1) = -1 \ne 0\): independent, not orthogonal.
\((.6,.8)\cdot(.4,-.3) = .24 - .24 = 0\): orthogonal. Lengths: \(\sqrt{.36 + .64} = 1\) but \(\sqrt{.16 + .09} = .5\). So orthogonal, not orthonormal.
Rotations and reflections are orthogonal matrices; this theorem is why computer graphics is full of them.
Caution. \(Q\T Q = I\) holds for every matrix with orthonormal columns, but \(QQ\T = I\) only when \(Q\) is square. For example \(Q = \begin{bmatrix} 1 & 0 \\ 0 & 1 \\ 0 & 0 \end{bmatrix}\) has \(Q\T Q = I_2\) but \(QQ\T \ne I_3\).
Least squares with orthonormal columns
If the columns of \(A = Q\) are orthonormal, the normal equations \(Q\T Q\hat{\vb x} = Q\T\vb b\) collapse because \(Q\T Q = I\):
Projection with orthonormal columns.
\[ \begin{aligned} \hat{\vb x} &= Q\T\vb b && (\hat x_i = \vb q_i\T\vb b) \\ \vb p &= QQ\T\vb b = (\vb q_1\T\vb b)\,\vb q_1 + (\vb q_2\T\vb b)\,\vb q_2 + \cdots \end{aligned} \]
There is nothing to solve: every coefficient is a single dot product.
Example 2.3. Project \(\vb b = (3, 0, 3)\) onto the plane spanned by \(\vb q_1 = \tfrac13(1,2,2)\) and \(\vb q_2 = \tfrac13(2,1,-2)\).
Start with independent vectors \(\vb a, \vb b, \vb c\). We want orthonormal vectors \(\vb q_1, \vb q_2, \vb q_3\) that span the same space. The idea is one projection at a time: keep \(\vb a\); from \(\vb b\) subtract its projection onto \(\vb a\), because what is left over is an error vector and error vectors are perpendicular; from \(\vb c\) subtract its projections onto the first two; finally divide each vector by its length.
Figure 2.1 — one Gram–Schmidt step is one projection. Project \(\vb b\) onto the line through \(\vb A = \vb a\) to get \(\vb p\). What is left, \(\vb B = \vb b - \vb p\), is the error of that projection, so it is automatically orthogonal to \(\vb A\). Dividing \(\vb A\) and \(\vb B\) by their lengths gives \(\vb q_1\) and \(\vb q_2\).
Method 2.1 (Gram–Schmidt).
\(\vb A = \vb a\).
\(\vb B = \vb b - \dfrac{\vb A\T\vb b}{\vb A\T\vb A}\,\vb A\). Check \(\vb A\T\vb B = 0\).
\(\vb C = \vb c - \dfrac{\vb A\T\vb c}{\vb A\T\vb A}\,\vb A - \dfrac{\vb B\T\vb c}{\vb B\T\vb B}\,\vb B\). Check \(\vb A\T\vb C = 0\) and \(\vb B\T\vb C = 0\).
The original vectors are combinations of the \(\vb q\)'s, and each one uses only the earlier \(\vb q\)'s: \(\vb a\) is a multiple of \(\vb q_1\); \(\vb b\) is a combination of \(\vb q_1, \vb q_2\); \(\vb c\) uses all three. So the matrix connecting them is upper triangular.
\(A = QR\). With \(A = [\,\vb a\ \ \vb b\ \ \vb c\,]\) and \(Q = [\,\vb q_1\ \ \vb q_2\ \ \vb q_3\,]\),
\[ A = QR, \qquad R = Q\T A = \begin{bmatrix} \vb q_1\T\vb a & \vb q_1\T\vb b & \vb q_1\T\vb c \\ 0 & \vb q_2\T\vb b & \vb q_2\T\vb c \\ 0 & 0 & \vb q_3\T\vb c \end{bmatrix}. \]
The diagonal of \(R\) holds the lengths \(\nrm{\vb A}, \nrm{\vb B}, \nrm{\vb C}\).
Example 2.6. Write \(A = QR\) for the vectors of Example 2.4.
Remark (why computers use \(QR\)). With \(A = QR\) the normal equations become \(R\T R\hat{\vb x} = R\T Q\T\vb b\), that is \(R\hat{\vb x} = Q\T\vb b\): a triangular system solved by back substitution, with much smaller rounding errors than forming \(A\T A\). Every serious least-squares program works this way.
Exercise 2.
Is \(\dfrac{1}{\sqrt2}\begin{bmatrix} 1 & -1 \\ 1 & 1 \end{bmatrix}\) an orthogonal matrix? If so, write its inverse.
Apply Gram–Schmidt to \(\vb a = (1, 1, 0)\), \(\vb b = (2, 0, 2)\), and write \(R\).
Show answer
Answer
The columns are \(\frac{1}{\sqrt2}(1, 1)\) and \(\frac{1}{\sqrt2}(-1, 1)\). Dot product \(\frac12(-1 + 1) = 0\); squared lengths \(\frac12(1 + 1) = 1\) each. Orthonormal columns in a square matrix, so yes, it is an orthogonal matrix and \(Q^{-1} = Q\T = \dfrac{1}{\sqrt2}\begin{bmatrix} 1 & 1 \\ -1 & 1 \end{bmatrix}\).
\(\vb A = (1,1,0)\), \(\vb A\T\vb A = 2\), \(\vb A\T\vb b = 2 + 0 + 0 = 2\), so \(\vb B = \vb b - \frac22\vb A = (2,0,2) - (1,1,0) = (1, -1, 2)\); check \(\vb A\T\vb B = 1 - 1 + 0 = 0\). \(\checkmark\) Lengths \(\nrm{\vb A} = \sqrt2\), \(\nrm{\vb B} = \sqrt{1 + 1 + 4} = \sqrt6\), so \(\vb q_1 = \frac{1}{\sqrt2}(1,1,0)\) and \(\vb q_2 = \frac{1}{\sqrt6}(1,-1,2)\). Then \(R = \begin{bmatrix} \vb q_1\T\vb a & \vb q_1\T\vb b \\ 0 & \vb q_2\T\vb b \end{bmatrix} = \begin{bmatrix} \sqrt2 & 2/\sqrt2 \\ 0 & 6/\sqrt6 \end{bmatrix} = \begin{bmatrix} \sqrt2 & \sqrt2 \\ 0 & \sqrt6 \end{bmatrix}\).
3Question types and model answers
Almost every question on this part is one of the four types below. Each model answer is written out the way I expect to see it on paper: the formula first, then the numbers, the arithmetic, the check, and a one-line conclusion.
Type 1 — Least-squares line
Question. Find the least-squares line \(b = C + Dt\) through \((0, 6), (1, 0), (2, 0)\). Give the heights, the errors and \(E\).
Question. Project \(\vb b = (3, 0, 3)\) onto the plane spanned by the orthonormal vectors \(\vb q_1 = \tfrac13(1,2,2)\) and \(\vb q_2 = \tfrac13(2,1,-2)\).
Q4. Project \(\vb b = (1, 1, 1)\) onto the plane spanned by the orthonormal vectors \(\vb q_1 = \tfrac13(1, 2, 2)\) and \(\vb q_2 = \tfrac13(2, -2, 1)\). Give \(\vb p\), \(\vb e\) and the checks.
Show answer
Answer \(\hat x_1 = \vb q_1\T\vb b = \frac13(1 + 2 + 2) = \frac53\), \(\hat x_2 = \vb q_2\T\vb b = \frac13(2 - 2 + 1) = \frac13\). \(\vb p = \frac53\vb q_1 + \frac13\vb q_2 = \frac59(1,2,2) + \frac19(2,-2,1) = \left(\frac79, \frac89, \frac{11}{9}\right)\). \(\vb e = \vb b - \vb p = \left(\frac29, \frac19, -\frac29\right)\). Checks: \(\vb q_1\T\vb e = \frac{1}{27}(2 + 2 - 4) = 0\) and \(\vb q_2\T\vb e = \frac{1}{27}(4 - 2 - 2) = 0\). \(\checkmark\)
Q5. Apply Gram–Schmidt to \(\vb a = (1, 1, 0)\), \(\vb b = (2, 0, 2)\): find \(\vb q_1\), \(\vb q_2\) and \(R\).
Show answer
Answer \(\vb A = \vb a = (1,1,0)\), \(\vb A\T\vb A = 2\). \(\vb A\T\vb b = 2 + 0 + 0 = 2\), so \(\vb B = \vb b - \frac22\vb A = (2,0,2) - (1,1,0) = (1, -1, 2)\); check \(\vb A\T\vb B = 1 - 1 + 0 = 0\). \(\checkmark\) Lengths \(\nrm{\vb A} = \sqrt2\), \(\nrm{\vb B} = \sqrt{1 + 1 + 4} = \sqrt6\), so \(\vb q_1 = \frac{1}{\sqrt2}(1,1,0)\), \(\vb q_2 = \frac{1}{\sqrt6}(1,-1,2)\). \(R = \begin{bmatrix} \vb q_1\T\vb a & \vb q_1\T\vb b \\ 0 & \vb q_2\T\vb b \end{bmatrix} = \begin{bmatrix} \sqrt2 & 2/\sqrt2 \\ 0 & 6/\sqrt6 \end{bmatrix} = \begin{bmatrix} \sqrt2 & \sqrt2 \\ 0 & \sqrt6 \end{bmatrix}\).
Q6 (theory). (a) Explain why the least-squares solution satisfies \(A\T A\hat{\vb x} = A\T\vb b\). (b) Prove that \(\nrm{Q\vb x} = \nrm{\vb x}\) when \(Q\) has orthonormal columns. (c) Why do the normal equations become \(\hat{\vb x} = Q\T\vb b\) when \(A = Q\)?
Show answer
Answer (a) As \(\vb x\) varies, \(A\vb x\) runs through the column space, so minimising \(\nrm{A\vb x - \vb b}\) means finding the point of \(\mathbf C(A)\) closest to \(\vb b\). That point is the projection \(\vb p = A\hat{\vb x}\), whose error \(\vb b - A\hat{\vb x}\) is perpendicular to every column: \(A\T(\vb b - A\hat{\vb x}) = \vb 0\), i.e. \(A\T A\hat{\vb x} = A\T\vb b\). (b) \(\nrm{Q\vb x}^2 = (Q\vb x)\T(Q\vb x) = \vb x\T Q\T Q\vb x = \vb x\T I\vb x = \nrm{\vb x}^2\). \(\blacksquare\) (c) With \(A = Q\) the normal equations read \(Q\T Q\hat{\vb x} = Q\T\vb b\), and \(Q\T Q = I\) because the columns are orthonormal, so \(\hat{\vb x} = Q\T\vb b\): each coefficient is one dot product \(\vb q_i\T\vb b\).
5Formula sheet
Topic
Formulas
Least squares
\(\hat{\vb x}\) minimises \(E = \nrm{A\vb x - \vb b}^2 = e_1^2 + \cdots + e_m^2\) solve the normal equations \(A\T A\hat{\vb x} = A\T\vb b\)