6.5 Least squares · Matrix Theory

A linear system with more equations than unknowns usually has no solution, and that is the normal situation with measured data. Suppose the length of a spring is measured under five different loads. Hooke’s law says that the five data points lie on a line $𝑦 = 𝑐_{0} + 𝑐_{1} 𝑥$ , which gives five linear equations in the two unknowns $𝑐_{0}, 𝑐_{1}$ , and small measurement errors make them inconsistent. When no $𝐱$ satisfies $𝐴 𝐱 = 𝐛$ , the natural substitute is an $𝐱$ for which $𝐴 𝐱$ is as close to $𝐛$ as possible. As $𝐱$ varies, $𝐴 𝐱$ runs over the column space $im 𝐴$ , so this asks for the point of $im 𝐴$ closest to $𝐛$ , and Theorem 6.4.33 says that this point is ${Pr}_{im 𝐴} (𝐛)$ . This section turns the observation into a computation, the normal equations $𝐴^{*} 𝐴 𝐱 = 𝐴^{*} 𝐛$ , which find the best $𝐱$ without an orthonormal basis of $im 𝐴$ , and applies it to fitting lines and curves to data.

Throughout, $𝔽$ is $ℝ$ or $ℂ$ , $𝐴 \in 𝔽^{𝑚 \times 𝑛}$ has columns $𝐚_{1}, \dots, 𝐚_{𝑛}$ , and $𝐛 \in 𝔽^{𝑚}$ . The spaces $𝔽^{𝑚}$ and $𝔽^{𝑛}$ carry the dot product (Definition 6.1.8), so $⟨ 𝐮, 𝐯 ⟩ = 𝐯^{*} 𝐮$ and ${‖ 𝐮 ‖}^{2} = \sum_{𝑖} {| 𝑢_{𝑖} |}^{2}$ . Only Section 6.5.5 and the exercises built on it use other inner products.

6.5.1The least-squares problem

Intuition (Solving as well as possible). As $𝐱$ ranges over $𝔽^{𝑛}$ , the vector $𝐴 𝐱 =$ $𝑥_{1} 𝐚_{1} +$ $\dots +$ $𝑥_{𝑛} 𝐚_{𝑛}$ ranges over the column space $im 𝐴 =$ $span (𝐚_{1}, \dots, 𝐚_{𝑛})$ (Proposition 2.6.18). So $𝐴 𝐱 = 𝐛$ has a solution exactly when $𝐛 \in im 𝐴$ . If $𝐛 \notin im 𝐴$ , every $𝐴 𝐱$ misses $𝐛$ , and the best we can ask for is that the miss $‖ 𝐛 - 𝐴 𝐱 ‖$ be as small as possible. That is, we want the point of the subspace $im 𝐴$ nearest to $𝐛$ .

Picture $𝑚 = 3$ , with $im 𝐴$ a plane through $𝟎$ and $𝐛$ off the plane (Figure 6.5.1). The nearest point of the plane is the foot of the perpendicular from $𝐛$ , which is ${Pr}_{im 𝐴} (𝐛)$ . It lies in $im 𝐴$ , so it equals $𝐴 \hat{𝐱}$ for some $\hat{𝐱}$ , and that $\hat{𝐱}$ is the best we can do. So the problem splits into a geometric step, projecting $𝐛$ onto $im 𝐴$ , and an algebraic one, solving $𝐴 \hat{𝐱} = {Pr}_{im 𝐴} (𝐛)$ , a system that is consistent by construction. The normal equations of Section 6.5.2 merge the two steps.

Figure 6.5.1. The column space

im 𝐴 =

span (𝐚_{1}, 𝐚_{2})

(shaded) and a vector

𝐛 \notin im 𝐴

. The point of

im 𝐴

closest to

𝐛

is the foot

𝐴 \hat{𝐱} = {Pr}_{im 𝐴} (𝐛)

of the perpendicular, and the residual

𝐛 - 𝐴 \hat{𝐱}

is orthogonal to

im 𝐴

. Every other point

𝐴 𝐱

im 𝐴

is farther from

𝐛

(dashed).

Definition 6.5.1 (Least-squares solution). Let $𝐴 \in 𝔽^{𝑚 \times 𝑛}$ and $𝐛 \in 𝔽^{𝑚}$ . A least-squares solution of $𝐴 𝐱 = 𝐛$ is a vector $\hat{𝐱} \in 𝔽^{𝑛}$ such that

‖ 𝐛 - 𝐴 \hat{𝐱} ‖ \leq ‖ 𝐛 - 𝐴 𝐱 ‖ for every 𝐱 \in 𝔽^{𝑛} .

For such an $\hat{𝐱}$ , the vector $𝐛 - 𝐴 \hat{𝐱}$ is the residual, and $‖ 𝐛 - 𝐴 \hat{𝐱} ‖$ is the least-squares error.

The name comes from the quantity being minimized. In coordinates,

{‖ 𝐛 - 𝐴 𝐱 ‖}^{2} = \sum_{𝑖 = 1}^{𝑚} {| 𝑏_{𝑖} - {(𝐴 𝐱)}_{𝑖} |}^{2},

the sum of the squares of the errors in the $𝑚$ equations. If $𝐴 𝐱 = 𝐛$ has a solution, its least-squares solutions are exactly its solutions: the solutions have error $0$ , and by definiteness only they do. The course writes $𝐴 𝐱 \approx 𝐛$ for the problem of finding a least-squares solution.

The intuition above becomes the following proposition, which is Theorem 6.4.33 read for the subspace $im 𝐴$ .

Proposition 6.5.2 (Least squares is projection). Let $𝐴 \in 𝔽^{𝑚 \times 𝑛}$ and $𝐛 \in 𝔽^{𝑚}$ .

(a) $\hat{𝐱} \in 𝔽^{𝑛}$ is a least-squares solution of $𝐴 𝐱 = 𝐛$ if and only if $𝐴 \hat{𝐱} = {Pr}_{im 𝐴} (𝐛)$ .
(b)Least-squares solutions exist. If $\hat{𝐱}$ is one, the set of all of them is $\hat{𝐱} +$ $ker 𝐴 =$ ${\hat{𝐱} + 𝐳 | 𝐳 \in ker 𝐴}$ .
(c)The least-squares solution is unique if and only if the columns of $𝐴$ are linearly independent.
(d)The least-squares error is $dist (𝐛, im 𝐴)$ .

Proof.routine

Uses. Proposition 2.6.18 (The column space is spanned by the columns), Theorem 6.4.20 (Orthonormal bases exist), Theorem 6.4.33 (Best approximation), Corollary 2.6.31 (Fibers are translates of the kernel), Theorem 2.6.11 (Injectivity is decided at $𝟎$ ), Corollary 2.6.24 (The columns decide), Definition 6.4.34 (Distance to a subspace)

Hint 1. Every vector of

im 𝐴

has the form

𝐴 𝐱

. So minimizing

‖ 𝐛 - 𝐴 𝐱 ‖

over

𝐱 \in 𝔽^{𝑛}

is minimizing

‖ 𝐛 - 𝐰 ‖

over

𝐰 \in im 𝐴

Hint 2. For (a), use both halves of Theorem 6.4.33: the inequality and its equality case.

Hint 3. For (b),

{Pr}_{im 𝐴} (𝐛)

lies in

im 𝐴

. And

𝐴 𝐱 = 𝐴 \hat{𝐱}

exactly when

𝐱 - \hat{𝐱} \in ker 𝐴

Sketch. Let

𝐩 = {Pr}_{im 𝐴} (𝐛)

. If

𝐴 \hat{𝐱} = 𝐩

, then

‖ 𝐛 - 𝐩 ‖ \leq ‖ 𝐛 - 𝐴 𝐱 ‖

for all

𝐱

by Theorem 6.4.33, since

𝐴 𝐱 \in im 𝐴

. Conversely, a least-squares solution does at least as well as any

𝐱_{0}

with

𝐴 𝐱_{0} = 𝐩

, so

𝐴 \hat{𝐱}

is a point of

im 𝐴

at least as close to

𝐛

𝐩

, and the equality case forces

𝐴 \hat{𝐱} = 𝐩

. The least-squares solutions are then the solutions of the consistent system

𝐴 𝐱 = 𝐩

, which form

\hat{𝐱} + ker 𝐴

; this is a single point exactly when

ker 𝐴 = {𝟎}

The column space $𝑊 = im 𝐴$ is a subspace of the finite-dimensional space $𝔽^{𝑚}$ , so it has an orthonormal basis and ${Pr}_{𝑊}$ is defined (Theorem 6.4.20). Let $𝐩 = {Pr}_{𝑊} (𝐛)$ . By Proposition 2.6.18, every vector of $𝑊$ has the form $𝐴 𝐱$ .

(a) Suppose $𝐴 \hat{𝐱} = 𝐩$ , and let $𝐱 \in 𝔽^{𝑛}$ . Since $𝐴 𝐱 \in 𝑊$ , Theorem 6.4.33 gives

‖ 𝐛 - 𝐴 \hat{𝐱} ‖ = ‖ 𝐛 - 𝐩 ‖ \leq ‖ 𝐛 - 𝐴 𝐱 ‖ .

Conversely, suppose $\hat{𝐱}$ is a least-squares solution. Since $𝐩 \in 𝑊$ , there is $𝐱_{0}$ with $𝐴 𝐱_{0} = 𝐩$ , and so $‖ 𝐛 -$ $𝐴 \hat{𝐱} ‖ \leq$ $‖ 𝐛 -$ $𝐴 𝐱_{0} ‖ =$ $‖ 𝐛 -$ $𝐩 ‖$ . On the other hand, $𝐴 \hat{𝐱} \in 𝑊$ , so $‖ 𝐛 -$ $𝐩 ‖ \leq$ $‖ 𝐛 -$ $𝐴 \hat{𝐱} ‖$ by Theorem 6.4.33. So equality holds, and by the equality case of Theorem 6.4.33, $𝐴 \hat{𝐱} = 𝐩$ .

(b) Since $𝐩 \in 𝑊$ , there is $\hat{𝐱}$ with $𝐴 \hat{𝐱} = 𝐩$ , and it is a least-squares solution by (a). By (a), the least-squares solutions are exactly the solutions of the consistent system $𝐴 𝐱 = 𝐩$ , and by Corollary 2.6.31 (applied to $𝑇_{𝐴}$ ) these form the set $\hat{𝐱} + ker 𝐴$ .

(c) By (b), the least-squares solution is unique if and only if $ker 𝐴 = {𝟎}$ , that is, if and only if $𝑇_{𝐴}$ is injective (Theorem 2.6.11). By Corollary 2.6.24, this happens if and only if the columns of $𝐴$ are linearly independent.

(d) By (a) and Definition 6.4.34, $‖ 𝐛 -$ $𝐴 \hat{𝐱} ‖ =$ $‖ 𝐛 -$ ${Pr}_{𝑊} (𝐛) ‖ =$ $dist (𝐛, 𝑊)$ . □

By (b), the set of least-squares solutions has the same shape as the solution set of a consistent system (Proposition 3.1.19), and for a good reason: it is the solution set of the consistent system $𝐴 𝐱 = {Pr}_{im 𝐴} (𝐛)$ . Note also that the vector $𝐴 \hat{𝐱}$ is always unique, even when $\hat{𝐱}$ is not.

Example 6.5.3 (Three points and a line). No line passes through the three points $(0, 1)$ , $(1, 1)$ , $(2, 4)$ . Let us find the line $𝑦 = 𝑐_{0} + 𝑐_{1} 𝑥$ that comes closest, in the sense that the sum of the squared vertical gaps between the points and the line is as small as possible. The line passes through all three points exactly when

𝑐_{0} + 0 𝑐_{1} = 1, 𝑐_{0} + 1 𝑐_{1} = 1, 𝑐_{0} + 2 𝑐_{1} = 4,

that is, when $𝐴 𝐜 = 𝐲$ for the unknown $𝐜 = (𝑐_{0}, 𝑐_{1})$ , where

𝐴 = (\begin{matrix} 1 & 0 \\ 1 & 1 \\ 1 & 2 \end{matrix}), 𝐲 = (\begin{matrix} 1 \\ 1 \\ 4 \end{matrix}) .

The first two equations force $𝑐_{1} = 0$ and $𝑐_{0} = 1$ , and then the third says $1 = 4$ , so the system is inconsistent. The $𝑖$ th entry of $𝐲 - 𝐴 𝐜$ is the vertical gap $𝑦_{𝑖} -$ $(𝑐_{0} + 𝑐_{1} 𝑥_{𝑖})$ at the $𝑖$ th point, so the best line comes from the least-squares solution of $𝐴 𝐜 = 𝐲$ .

The column space is the plane in $ℝ^{3}$ spanned by $𝟏 = (1, 1, 1)$ and $𝐱 = (0, 1, 2)$ . These are not orthogonal, so we first run Gram–Schmidt (Algorithm 6.4.14): $𝐱 -$ $(⟨ 𝐱, 𝟏 ⟩ / 3) 𝟏 =$ $(0, 1, 2) -$ $(1, 1, 1) =$ $(- 1, 0, 1)$ . With the orthogonal basis $𝟏, (- 1, 0, 1)$ of $im 𝐴$ , Corollary 6.4.10 gives

{Pr}_{im 𝐴} (𝐲) = \frac{6}{3} (1, 1, 1) + \frac{3}{2} (- 1, 0, 1) = (\frac{1}{2}, 2, \frac{7}{2}) .

Solving $𝐴 𝐜 = (1 / 2, 2, 7 / 2)$ gives $𝑐_{0} = 1 / 2$ and $𝑐_{1} = 3 / 2$ , and the third equation checks: $1 / 2 + 2 \cdot 3 / 2 = 7 / 2$ . The columns of $𝐴$ are independent, so by Proposition 6.5.2 the least-squares line is unique: it is $𝑦 = \frac{1}{2} + \frac{3}{2} 𝑥$ .

The residual is $𝐲 -$ $𝐴 𝐜 =$ $(1 / 2, - 1, 1 / 2)$ . Its entries are the three vertical gaps, the red segments in the plot below, and the sum of their squares is $3 / 2$ . In $ℝ^{3}$ it is a single vector, orthogonal to the plane $im 𝐴$ : indeed $(1 / 2, - 1, 1 / 2) \cdot$ $(1, 1, 1) =$ $0$ and $(1 / 2, - 1, 1 / 2) \cdot$ $(0, 1, 2) =$ $0$ . Minimizing the sum of the squared gaps in the plot is the same as minimizing the length of one vector in $ℝ^{3}$ .

The line of Example 6.5.3 and its residuals (red). In the interactive version, “Column space” shows the same fit in

ℝ^{3}

: the data vector

𝐲

, its projection

𝐴 𝐜

onto the plane spanned by

𝟏

and

𝐱

, and the residual, whose three coordinates are the three red gaps in the plot. Drag the points and watch the residual vector stay perpendicular to the plane.

The computation in Example 6.5.3 took a detour. We wanted the coefficients $𝐜$ , but we first computed an orthogonal basis of $im 𝐴$ and the vector $𝐴 𝐜$ , and only then solved for $𝐜$ . The normal equations go to $𝐜$ directly.

6.5.2The normal equations

Intuition (Why the residual is perpendicular). Here is a direct reason, without Theorem 6.4.33, why the best $𝐴 𝐱$ must be the foot of the perpendicular. Take any candidate $𝐴 𝐱$ and its residual $𝐫 = 𝐛 - 𝐴 𝐱$ . Suppose $𝐫$ is not perpendicular to $im 𝐴$ , so that $⟨ 𝐫, 𝐰 ⟩ \neq 0$ for some $𝐰 \in im 𝐴$ ; replacing $𝐰$ by a scalar multiple, we may take $⟨ 𝐫, 𝐰 ⟩$ real and positive. Slide the candidate a little in the direction $𝐰$ , to $𝐴 𝐱 + 𝑡 𝐰$ with $𝑡 > 0$ , which is still in $im 𝐴$ . Its distance to $𝐛$ satisfies

{‖ 𝐫 - 𝑡 𝐰 ‖}^{2} = {‖ 𝐫 ‖}^{2} - 2 𝑡 ⟨ 𝐫, 𝐰 ⟩ + 𝑡^{2} {‖ 𝐰 ‖}^{2}

by Proposition 6.1.29. For small $𝑡 > 0$ the term $- 2 𝑡 ⟨ 𝐫, 𝐰 ⟩$ beats $𝑡^{2} {‖ 𝐰 ‖}^{2}$ , so the new candidate is strictly closer. A candidate whose residual has any component along $im 𝐴$ can be improved by sliding toward that component. So the best candidate, if there is one, has a residual orthogonal to all of $im 𝐴$ , which is the condition of Theorem 6.4.6.

The condition $𝐫 ⟂ im 𝐴$ is checked one column at a time, since $im 𝐴$ is spanned by the columns. And “ $𝐫 ⟂ 𝐚_{𝑗}$ for every $𝑗$ ” is a single matrix equation: $𝐚_{𝑗}^{*} 𝐫$ is the $𝑗$ th entry of $𝐴^{*} 𝐫$ . With $𝐫 = 𝐛 - 𝐴 𝐱$ , the condition $𝐴^{*} (𝐛 - 𝐴 𝐱) = 𝟎$ is a linear system for $𝐱$ . Here “normal” means perpendicular: the equations say that the residual is normal to the column space.

The column-by-column test deserves to be recorded for any matrix.

Lemma 6.5.4 (The orthogonal complement of a column space). For every

𝑀 \in 𝔽^{𝑚 \times 𝑛}

{(im 𝑀)}^{⟂} = ker 𝑀^{*}

. That is, a vector

𝐲 \in 𝔽^{𝑚}

is orthogonal to every column of

𝑀

if and only if

𝑀^{*} 𝐲 = 𝟎

Proof.routine

Uses. Definition 6.3.26 (Conjugate transpose), Proposition 2.4.8 (Four views of the product), Definition 6.1.8 (Dot product), Proposition 6.3.9 (Properties of $𝐴^{⟂}$ ), Proposition 2.6.18 (The column space is spanned by the columns)

Hint 1. Compute the

𝑗

th entry of

𝑀^{*} 𝐲

. What is row

𝑗

𝑀^{*}

Hint 2. The

𝑗

th entry is

𝐦_{𝑗}^{*} 𝐲 = ⟨ 𝐲, 𝐦_{𝑗} ⟩

, where

𝐦_{𝑗}

is column

𝑗

𝑀

. Then pass from the columns to their span with Proposition 6.3.9(c).

Sketch. Row

𝑗

𝑀^{*}

𝐦_{𝑗}^{*}

, so the

𝑗

th entry of

𝑀^{*} 𝐲

𝐦_{𝑗}^{*} 𝐲 = ⟨ 𝐲, 𝐦_{𝑗} ⟩

. So

𝑀^{*} 𝐲 = 𝟎

if and only if

𝐲

is orthogonal to each column, and by Proposition 6.3.9(c) that means

𝐲 ⟂ span (𝐦_{1}, \dots, 𝐦_{𝑛}) =

im 𝑀

Let $𝐦_{1}, \dots, 𝐦_{𝑛}$ be the columns of $𝑀$ . By Definition 6.3.26, row $𝑗$ of $𝑀^{*}$ is $𝐦_{𝑗}^{*}$ , so by Proposition 2.4.8 and Definition 6.1.8 the $𝑗$ th entry of $𝑀^{*} 𝐲$ is

𝐦_{𝑗}^{*} 𝐲 = 𝐲 \cdot 𝐦_{𝑗} = ⟨ 𝐲, 𝐦_{𝑗} ⟩ .

Hence $𝑀^{*} 𝐲 = 𝟎$ if and only if $𝐲 ⟂ 𝐦_{𝑗}$ for every $𝑗$ . By Proposition 6.3.9(c) and Proposition 2.6.18, that holds if and only if $𝐲 ⟂ span (𝐦_{1}, \dots, 𝐦_{𝑛}) =$ $im 𝑀$ . □

For real $𝑀$ this says ${(im 𝑀)}^{⟂} = ker 𝑀^{𝖳}$ ; applied to $𝑀^{𝖳}$ , it is the statement $ker 𝐴 = 𝑅^{⟂}$ of Example 6.4.23(b), where $𝑅$ is the span of the rows. Theorem 6.6.21 extends the lemma to linear maps between arbitrary inner product spaces.

Theorem 6.5.5 (The normal equations). Let

𝐴 \in 𝔽^{𝑚 \times 𝑛}

𝐛 \in 𝔽^{𝑚}

, and

\hat{𝐱} \in 𝔽^{𝑛}

. The following are equivalent:

(i) $\hat{𝐱}$ is a least-squares solution of $𝐴 𝐱 = 𝐛$ ;
(ii) $𝐛 - 𝐴 \hat{𝐱} ⟂ im 𝐴$ , that is, the residual is orthogonal to every column of $𝐴$ ;
(iii) $𝐴^{*} 𝐴 \hat{𝐱} = 𝐴^{*} 𝐛$ .

In particular, the normal equations

𝐴^{*} 𝐴 𝐱 = 𝐴^{*} 𝐛

always have a solution, and their solutions are exactly the least-squares solutions of

𝐴 𝐱 = 𝐛

Proof (by projection).routine

Uses. Proposition 6.5.2 (Least squares is projection), Theorem 6.4.6 (The projection is characterized by orthogonality), Theorem 6.4.20 (Orthonormal bases exist), Lemma 6.5.4 (The orthogonal complement of a column space)

Techniques. Recognize a projection by its two conditions (Technique 6.4.7)

Hint 1. By Proposition 6.5.2(a), (i) says that

𝐴 \hat{𝐱} = {Pr}_{im 𝐴} (𝐛)

. Which two conditions characterize this projection?

Hint 2.

𝐴 \hat{𝐱}

lies in

im 𝐴

no matter what, so only the second condition of Theorem 6.4.6 is in question.

Hint 3. For (ii)

\Leftrightarrow

(iii), apply Lemma 6.5.4 to the vector

𝐛 - 𝐴 \hat{𝐱}

Sketch. (i) holds iff

𝐴 \hat{𝐱} = {Pr}_{im 𝐴} (𝐛)

(Proposition 6.5.2(a)). Since

𝐴 \hat{𝐱} \in im 𝐴

automatically, Theorem 6.4.6 says this holds iff

𝐛 - 𝐴 \hat{𝐱} ⟂ im 𝐴

, which is (ii). By Lemma 6.5.4, (ii) holds iff

𝐴^{*} (𝐛 - 𝐴 \hat{𝐱}) = 𝟎

, which is (iii). Existence is Proposition 6.5.2(b).

(i) $\Leftrightarrow$ (ii). By Proposition 6.5.2(a), (i) holds if and only if $𝐴 \hat{𝐱} = {Pr}_{im 𝐴} (𝐛)$ . Fix an orthonormal basis of $im 𝐴$ (Theorem 6.4.20). By Theorem 6.4.6, ${Pr}_{im 𝐴} (𝐛)$ is the unique vector $𝐩$ with $𝐩 \in im 𝐴$ and $𝐛 - 𝐩 ⟂ im 𝐴$ . The vector $𝐩 = 𝐴 \hat{𝐱}$ lies in $im 𝐴$ in any case, so $𝐴 \hat{𝐱} = {Pr}_{im 𝐴} (𝐛)$ if and only if $𝐛 - 𝐴 \hat{𝐱} ⟂ im 𝐴$ .

(ii) $\Leftrightarrow$ (iii). By Lemma 6.5.4, $𝐛 - 𝐴 \hat{𝐱} ⟂ im 𝐴$ if and only if $𝐴^{*} (𝐛 - 𝐴 \hat{𝐱}) = 𝟎$ , that is, $𝐴^{*} 𝐴 \hat{𝐱} = 𝐴^{*} 𝐛$ .

Finally, least-squares solutions exist by Proposition 6.5.2(b), and by (i) $\Leftrightarrow$ (iii) they are exactly the solutions of the normal equations. □

The second proof does not use projections at all. It makes the sliding argument of the intuition precise, and the move it uses applies to many minimization problems.

Technique 6.5.6 (Perturb a minimizer). Suppose $\hat{𝐱}$ minimizes a real-valued quantity $𝑓 (𝐱)$ over a vector space. Then for every direction $𝐡$ , the function $𝑡 \mapsto 𝑓 (\hat{𝐱} + 𝑡 𝐡)$ of a real variable $𝑡$ has a minimum at $𝑡 = 0$ . When $𝑓$ is the squared norm of a vector that depends linearly (or affinely) on $𝐱$ , this function is a quadratic polynomial $𝛼 + 𝛽 𝑡 + 𝛾 𝑡^{2}$ with $𝛾 \geq 0$ , and a minimum at $𝑡 = 0$ forces the linear coefficient $𝛽$ to vanish: if $𝛽 \neq 0$ , a small $𝑡$ of the opposite sign makes $𝛽 𝑡 + 𝛾 𝑡^{2} < 0$ . Doing this for every $𝐡$ gives an equation that $\hat{𝐱}$ must satisfy. Choosing $𝐡$ cleverly, usually equal to the vector you want to show is zero, turns “ $𝛽 = 0$ ” into a statement ${‖ 𝐬 ‖}^{2} = 0$ (Technique 6.1.36). In the other direction, if the linear coefficient vanishes for every $𝐡$ , the expansion shows that $𝑓 (\hat{𝐱} + 𝐡) \geq$ $𝑓 (\hat{𝐱})$ , so $\hat{𝐱}$ is a minimizer.

This is “the derivative vanishes at a minimum” without derivatives, and with the converse built in. Reach for it when a vector is defined as the minimizer (or maximizer) of something and you need an equation it satisfies. The canonical example is the second proof of Theorem 6.5.5. The same move gives the minimal-norm solution in Section 6.5.7, and in Section 12.3 it shows that a maximizer of $⟨ 𝑇 𝐯, 𝐯 ⟩$ over unit vectors is an eigenvector.

Used in 4 places

Theorem 6.5.5, Exercise 6.5.39, Exercise 6.7.6, Exercise 6.7.13.

Proof of Theorem 6.5.5 (by perturbation).standard

Uses. Proposition 6.1.29 (Expanding a norm), Proposition 6.3.27 (Properties of the conjugate transpose), Definition 6.1.2 (Inner product), Lemma 6.5.4 (The orthogonal complement of a column space), Proposition 6.5.2 (Least squares is projection)

Techniques. Perturb a minimizer (Technique 6.5.6), Show a vector is zero via its norm (Technique 6.1.36)

Hint 1. Let

𝐫 = 𝐛 - 𝐴 \hat{𝐱}

and

𝐬 = 𝐴^{*} 𝐫

. Expand

{‖ 𝐛 - 𝐴 (\hat{𝐱} + 𝐡) ‖}^{2} =

{‖ 𝐫 - 𝐴 𝐡 ‖}^{2}

for an arbitrary

𝐡 \in 𝔽^{𝑛}

Hint 2. Move

𝐴

across the inner product:

⟨ 𝐫, 𝐴 𝐡 ⟩ =

⟨ 𝐴^{*} 𝐫, 𝐡 ⟩ =

⟨ 𝐬, 𝐡 ⟩

. You should get

{‖ 𝐫 ‖}^{2} -

2 Re ⟨ 𝐬, 𝐡 ⟩ +

{‖ 𝐴 𝐡 ‖}^{2}

Hint 3. If

𝐬 = 𝟎

, the middle term is gone. If

\hat{𝐱}

is a minimizer, take

𝐡 = 𝑡 𝐬

with

𝑡 > 0

small.

Sketch. With

𝐫 = 𝐛 - 𝐴 \hat{𝐱}

and

𝐬 = 𝐴^{*} 𝐫

, for every

𝐡

{‖ 𝐛 - 𝐴 (\hat{𝐱} + 𝐡) ‖}^{2} =

{‖ 𝐫 ‖}^{2} -

2 Re ⟨ 𝐬, 𝐡 ⟩ +

{‖ 𝐴 𝐡 ‖}^{2}

. If

𝐬 = 𝟎

, this is at least

{‖ 𝐫 ‖}^{2}

, so

\hat{𝐱}

is a minimizer. If

\hat{𝐱}

is a minimizer, put

𝐡 = 𝑡 𝐬

: then

2 𝑡 {‖ 𝐬 ‖}^{2} \leq

𝑡^{2} {‖ 𝐴 𝐬 ‖}^{2}

for all

𝑡 > 0

, so

{‖ 𝐬 ‖}^{2} \leq

(𝑡 / 2) {‖ 𝐴 𝐬 ‖}^{2}

for all

𝑡 > 0

, which forces

𝐬 = 𝟎

. So (i)

\Leftrightarrow

(iii); and (ii)

\Leftrightarrow

(iii) is Lemma 6.5.4.

Let $𝐫 = 𝐛 - 𝐴 \hat{𝐱}$ and $𝐬 =$ $𝐴^{*} 𝐫 =$ $𝐴^{*} 𝐛 -$ $𝐴^{*} 𝐴 \hat{𝐱}$ , so that (iii) says $𝐬 = 𝟎$ . Every $𝐱 \in 𝔽^{𝑛}$ has the form $\hat{𝐱} + 𝐡$ , and $𝐛 -$ $𝐴 (\hat{𝐱} + 𝐡) =$ $𝐫 -$ $𝐴 𝐡$ . By Proposition 6.3.27(d) and conjugate symmetry,

⟨ 𝐫, 𝐴 𝐡 ⟩ = ⟨ 𝐴 𝐡, 𝐫 ⟩ = ⟨ 𝐡, 𝐴^{*} 𝐫 ⟩ = ⟨ 𝐬, 𝐡 ⟩,

so Proposition 6.1.29 gives, for every $𝐡 \in 𝔽^{𝑛}$ ,

{‖ 𝐛 - 𝐴 (\hat{𝐱} + 𝐡) ‖}^{2} = {‖ 𝐫 ‖}^{2} - 2 Re ⟨ 𝐬, 𝐡 ⟩ + {‖ 𝐴 𝐡 ‖}^{2} .

(6.5.1)

(iii) $\Rightarrow$ (i). If $𝐬 = 𝟎$ , then (6.5.1) reads ${‖ 𝐛 - 𝐴 (\hat{𝐱} + 𝐡) ‖}^{2} =$ ${‖ 𝐫 ‖}^{2} +$ ${‖ 𝐴 𝐡 ‖}^{2} \geq$ ${‖ 𝐫 ‖}^{2}$ for every $𝐡$ . So $\hat{𝐱}$ is a least-squares solution.

(i) $\Rightarrow$ (iii). Suppose $\hat{𝐱}$ is a least-squares solution, and take $𝐡 = 𝑡 𝐬$ with $𝑡$ real and positive. Then $⟨ 𝐬, 𝐡 ⟩ = 𝑡 {‖ 𝐬 ‖}^{2}$ , and (6.5.1) together with minimality gives

{‖ 𝐫 ‖}^{2} \leq {‖ 𝐫 ‖}^{2} - 2 𝑡 {‖ 𝐬 ‖}^{2} + 𝑡^{2} {‖ 𝐴 𝐬 ‖}^{2}, that is, 2 {‖ 𝐬 ‖}^{2} \leq 𝑡 {‖ 𝐴 𝐬 ‖}^{2}

after dividing by $𝑡 > 0$ . If $𝐬 \neq 𝟎$ , choose $𝑡 > 0$ so small that $𝑡 {‖ 𝐴 𝐬 ‖}^{2} <$ $2 {‖ 𝐬 ‖}^{2}$ (any $𝑡 > 0$ works if $𝐴 𝐬 = 𝟎$ ); this contradicts the inequality. So $𝐬 = 𝟎$ .

(ii) $\Leftrightarrow$ (iii) is Lemma 6.5.4 applied to $𝐫$ , as in the first proof. The perturbation argument characterizes the least-squares solutions but does not produce one, so existence still comes from Proposition 6.5.2(b); Exercise 6.5.45 gives an algebraic existence proof instead. □

The first proof is the picture of Figure 6.5.1: least squares is projection, and projections are recognized by orthogonality. The second is the calculus approach of “set the gradient to zero”, done without derivatives: $𝐬 = 𝐴^{*} (𝐛 - 𝐴 \hat{𝐱})$ is, up to a factor $- 2$ , the gradient of ${‖ 𝐛 - 𝐴 𝐱 ‖}^{2}$ . It does not use Theorem 6.4.33, and it gives a sharper statement. If $\hat{𝐱}$ solves the normal equations, then by (6.5.1) with $𝐡 = 𝐱 - \hat{𝐱}$ ,

\begin{aligned} {‖ 𝐛 - 𝐴 𝐱 ‖}^{2} & = {‖ 𝐛 - 𝐴 \hat{𝐱} ‖}^{2} \\ + {‖ 𝐴 (𝐱 - \hat{𝐱}) ‖}^{2} \end{aligned}

(6.5.2)

for every $𝐱 \in 𝔽^{𝑛}$ . This is Pythagoras for the right triangle of Figure 6.5.1 with vertices $𝐛$ , $𝐴 \hat{𝐱}$ , $𝐴 𝐱$ , and it says exactly how fast the error grows as $𝐱$ moves away from $\hat{𝐱}$ .

Example 6.5.7 (Three points, by the normal equations). Return to Example 6.5.3, with $𝐴 = (\begin{matrix} 1 & 0 \\ 1 & 1 \\ 1 & 2 \end{matrix})$ and $𝐲 = (1, 1, 4)$ . The entries of $𝐴^{𝖳} 𝐴$ are the dot products of the columns $𝟏 = (1, 1, 1)$ and $𝐱 = (0, 1, 2)$ (Theorem 6.3.29), and $𝐴^{𝖳} 𝐲$ lists their dot products with $𝐲$ :

\begin{aligned} 𝐴^{𝖳} 𝐴 & = (\begin{matrix} 𝟏 \cdot 𝟏 & 𝐱 \cdot 𝟏 \\ 𝟏 \cdot 𝐱 & 𝐱 \cdot 𝐱 \end{matrix}) = (\begin{matrix} 3 & 3 \\ 3 & 5 \end{matrix}), \\ 𝐴^{𝖳} 𝐲 & = (\begin{matrix} 𝐲 \cdot 𝟏 \\ 𝐲 \cdot 𝐱 \end{matrix}) = (\begin{matrix} 6 \\ 9 \end{matrix}) . \end{aligned}

The normal equations $3 𝑐_{0} + 3 𝑐_{1} = 6$ , $3 𝑐_{0} + 5 𝑐_{1} = 9$ give $2 𝑐_{1} = 3$ , so $𝑐_{1} = 3 / 2$ and $𝑐_{0} = 1 / 2$ , as before. This time no orthogonal basis was needed: only the inner products of the columns with each other and with $𝐲$ .

Exercise 6.5.8.routine In $ℂ^{3}$ , let $𝐚 = (1, 𝑖, 1)$ and $𝐛 = (1, 1, 0)$ , and let $𝐴$ be the $3 \times 1$ matrix with column $𝐚$ .

(a)Find the least-squares solution $\hat{𝑧} \in ℂ$ of $𝐴 𝑧 = 𝐛$ , that is, of $𝑧 𝐚 = 𝐛$ , and check that the residual is orthogonal to $𝐚$ .
(b)A student solves $𝐴^{𝖳} 𝐴 𝑧 = 𝐴^{𝖳} 𝐛$ instead. Show that the resulting $𝑧$ is not a least-squares solution.

Solution.

Uses. Theorem 6.5.5 (The normal equations), Definition 6.1.8 (Dot product), Definition 6.3.26 (Conjugate transpose)

Hint 1. Here

𝐴^{*} 𝐴 = 𝐚^{*} 𝐚 = {‖ 𝐚 ‖}^{2}

and

𝐴^{*} 𝐛 =

𝐚^{*} 𝐛 =

⟨ 𝐛, 𝐚 ⟩

, with the entries of

𝐚

conjugated.

Hint 2. You should get

\hat{𝑧} = (1 - 𝑖) / 3

. For (b),

𝐚^{𝖳} 𝐚 = 1 + 𝑖^{2} + 1 = 1

Sketch. (a)

𝐚^{*} 𝐚 = 3

and

𝐚^{*} 𝐛 = 1 - 𝑖

, so

\hat{𝑧} = (1 - 𝑖) / 3

, and the residual

((2 + 𝑖) / 3, (2 - 𝑖) / 3, (- 1 + 𝑖) / 3)

has inner product

0

with

𝐚

. (b)

𝐚^{𝖳} 𝐚 = 1

and

𝐚^{𝖳} 𝐛 = 1 + 𝑖

, so

𝑧 = 1 + 𝑖

, whose residual

(- 𝑖, 2 - 𝑖, - 1 - 𝑖)

has inner product

- 2 - 4 𝑖 \neq 0

with

𝐚

; by Theorem 6.5.5 it is not a least-squares solution.

(a) With one column, the normal equations read $(𝐚^{*} 𝐚) 𝑧 = 𝐚^{*} 𝐛$ . Here $𝐚^{*} = (1, - 𝑖, 1)$ , so

𝐚^{*} 𝐚 = 1 + (- 𝑖) (𝑖) + 1 = 3, 𝐚^{*} 𝐛 = 1 + (- 𝑖) \cdot 1 + 0 = 1 - 𝑖,

and $\hat{𝑧} = (1 - 𝑖) / 3$ by Theorem 6.5.5. The residual is

\begin{aligned} 𝐛 - \hat{𝑧} 𝐚 & = (1 - \frac{1 - 𝑖}{3}, 1 - \frac{𝑖 + 1}{3}, - \frac{1 - 𝑖}{3}) \\ = (\frac{2 + 𝑖}{3}, \frac{2 - 𝑖}{3}, \frac{- 1 + 𝑖}{3}), \end{aligned}

using $𝑖 (1 - 𝑖) = 𝑖 + 1$ . Its inner product with $𝐚$ is

\begin{aligned} \frac{1}{3} ((2 + 𝑖) \cdot 1 + (2 - 𝑖) \cdot 𝑖 + (- 1 + 𝑖) \cdot 1) \\ = \frac{1}{3} ((2 + 𝑖) + (- 1 - 2 𝑖) + (- 1 + 𝑖)) = 0 . \end{aligned}

(b) $𝐚^{𝖳} 𝐚 = 1 + 𝑖^{2} + 1 = 1$ and $𝐚^{𝖳} 𝐛 = 1 + 𝑖$ , so the student gets $𝑧 = 1 + 𝑖$ . Its residual is $𝐛 -$ $(1 + 𝑖) 𝐚 =$ $(1 - (1 + 𝑖), 1 - (𝑖 - 1), - (1 + 𝑖)) =$ $(- 𝑖, 2 - 𝑖, - 1 - 𝑖)$ , and its inner product with $𝐚$ is $- 𝑖 +$ $(2 - 𝑖) (- 𝑖) +$ $(- 1 - 𝑖) =$ $- 𝑖 -$ $2 𝑖 -$ $1 -$ $1 -$ $𝑖 =$ $- 2 -$ $4 𝑖 \neq$ $0$ . By Theorem 6.5.5, $1 + 𝑖$ is not a least-squares solution. Over $ℂ$ the transpose does not compute inner products; the conjugate transpose does.

When is the solution unique?

Intuition (Same kernel). The coefficient matrix $𝐴^{*} 𝐴$ of the normal equations is the Gram matrix of the columns of $𝐴$ (Theorem 6.3.29). By Proposition 6.5.2(c) and Theorem 6.5.5, the normal equations have exactly one solution precisely when the columns of $𝐴$ are independent. Since $𝐴^{*} 𝐴$ is square, we expect it to be invertible exactly when the columns of $𝐴$ are independent, and the underlying statement is that $𝐴^{*} 𝐴$ and $𝐴$ have the same kernel.

One containment is free: if $𝐴 𝐱 = 𝟎$ , then $𝐴^{*} 𝐴 𝐱 = 𝟎$ . For the other we must get from $𝐴^{*} (𝐴 𝐱) = 𝟎$ back to $𝐴 𝐱 = 𝟎$ , and $𝐴^{*}$ can have a large kernel, so we cannot cancel it. Two things rescue us. Multiplying by $𝐱^{*}$ turns $𝐱^{*} 𝐴^{*} 𝐴 𝐱$ into ${‖ 𝐴 𝐱 ‖}^{2}$ , so the norm vanishes (Technique 6.1.36). Geometrically, $𝐴^{*} (𝐴 𝐱) = 𝟎$ says that $𝐴 𝐱$ is orthogonal to $im 𝐴$ (Lemma 6.5.4), while $𝐴 𝐱$ lies in $im 𝐴$ .

Proposition 6.5.9 ( $rank (𝐴^{*} 𝐴) =$ $rank 𝐴$ ). Let $𝐴 \in 𝔽^{𝑚 \times 𝑛}$ .

(a) $ker (𝐴^{*} 𝐴) = ker 𝐴$ .
(b) $rank (𝐴^{*} 𝐴) =$ $rank 𝐴$ .
(c) $𝐴^{*} 𝐴$ is invertible if and only if the columns of $𝐴$ are linearly independent, that is, if and only if $rank 𝐴 = 𝑛$ .

Proof (by the norm).standard

Uses. Proposition 6.3.27 (Properties of the conjugate transpose), Definition 6.1.8 (Dot product), Definition 6.1.2 (Inner product), Theorem 4.2.11 (Rank–nullity), Corollary 3.5.25 (The invertible matrix theorem), Corollary 2.6.24 (The columns decide), Theorem 3.5.12 (First Fundamental Theorem, completed)

Techniques. Show a vector is zero via its norm (Technique 6.1.36), Double containment (Technique 1.3.14)

Hint 1. For (a), the containment

ker 𝐴 \subseteq ker (𝐴^{*} 𝐴)

is immediate. For the other, suppose

𝐴^{*} 𝐴 𝐱 = 𝟎

and multiply on the left by

𝐱^{*}

Hint 2.

𝐱^{*} 𝐴^{*} 𝐴 𝐱 =

{(𝐴 𝐱)}^{*} (𝐴 𝐱) =

{‖ 𝐴 𝐱 ‖}^{2}

Hint 3. For (b), both matrices have

𝑛

columns; apply rank–nullity to each. For (c), a square matrix is invertible exactly when its kernel is

{𝟎}

Sketch. If

𝐴^{*} 𝐴 𝐱 = 𝟎

, then

{‖ 𝐴 𝐱 ‖}^{2} =

𝐱^{*} 𝐴^{*} 𝐴 𝐱 =

0

, so

𝐴 𝐱 = 𝟎

; the reverse containment is clear. Both matrices have

𝑛

columns, so rank–nullity turns equal kernels into equal ranks. The square matrix

𝐴^{*} 𝐴

is invertible iff its kernel, which is

ker 𝐴

, is

{𝟎}

, iff the columns of

𝐴

are independent.

(a) If $𝐴 𝐱 = 𝟎$ , then $𝐴^{*} 𝐴 𝐱 = 𝐴^{*} 𝟎 = 𝟎$ . Conversely, suppose $𝐴^{*} 𝐴 𝐱 = 𝟎$ . By Proposition 6.3.27(b) and (a), $𝐱^{*} 𝐴^{*} = {(𝐴 𝐱)}^{*}$ , so, identifying $1 \times 1$ matrices with scalars (Definition 6.1.8),

{‖ 𝐴 𝐱 ‖}^{2} = {(𝐴 𝐱)}^{*} (𝐴 𝐱) = 𝐱^{*} (𝐴^{*} 𝐴 𝐱) = 𝐱^{*} 𝟎 = 0 .

By definiteness, $𝐴 𝐱 = 𝟎$ . So $ker (𝐴^{*} 𝐴) = ker 𝐴$ .

(b) Both $𝐴^{*} 𝐴 \in 𝔽^{𝑛 \times 𝑛}$ and $𝐴$ have $𝑛$ columns, so by Theorem 4.2.11 and (a),

\begin{aligned} rank (𝐴^{*} 𝐴) & = 𝑛 - dim ker (𝐴^{*} 𝐴) \\ = 𝑛 - dim ker 𝐴 = rank 𝐴 . \end{aligned}

(c) The matrix $𝐴^{*} 𝐴$ is square, so it is invertible if and only if $ker (𝐴^{*} 𝐴) = {𝟎}$ (Corollary 3.5.25). By (a), that is $ker 𝐴 = {𝟎}$ , which holds if and only if the columns of $𝐴$ are linearly independent (Corollary 2.6.24), and if and only if $rank 𝐴 = 𝑛$ (Theorem 3.5.12). □

Proof (by orthogonality).routine

Uses. Lemma 6.5.4 (The orthogonal complement of a column space), Proposition 6.3.9 (Properties of $𝐴^{⟂}$ ), Theorem 4.2.11 (Rank–nullity), Corollary 3.5.25 (The invertible matrix theorem), Corollary 2.6.24 (The columns decide)

Techniques. Double containment (Technique 1.3.14)

Hint 1. Suppose

𝐴^{*} (𝐴 𝐱) = 𝟎

. What does Lemma 6.5.4 say about the vector

𝐴 𝐱

Hint 2.

𝐴 𝐱

lies in

im 𝐴

and in

{(im 𝐴)}^{⟂}

Sketch. If

𝐴^{*} (𝐴 𝐱) = 𝟎

, then

𝐴 𝐱 \in

ker 𝐴^{*} =

{(im 𝐴)}^{⟂}

by Lemma 6.5.4, and also

𝐴 𝐱 \in im 𝐴

. So

𝐴 𝐱 \in

im 𝐴 \cap

{(im 𝐴)}^{⟂} =

{𝟎}

. Parts (b) and (c) follow from (a) as in the first proof.

As before,

ker 𝐴 \subseteq ker (𝐴^{*} 𝐴)

. Conversely, let

𝐴^{*} 𝐴 𝐱 = 𝟎

, and put

𝐲 = 𝐴 𝐱

. Then

𝐴^{*} 𝐲 = 𝟎

, so

𝐲 \in {(im 𝐴)}^{⟂}

by Lemma 6.5.4. But also

𝐲 \in im 𝐴

. Hence

𝐲 \in

im 𝐴 \cap

{(im 𝐴)}^{⟂} =

{𝟎}

(Proposition 6.3.9(d)), that is,

𝐴 𝐱 = 𝟎

. This proves (a), and (b) and (c) follow from (a) exactly as in the first proof. □

The first proof is the one that generalizes to operators: the same computation shows $ker (𝑇^{*} 𝑇) = ker 𝑇$ for a linear map $𝑇$ between inner product spaces (Section 6.6). It is also Proposition 6.3.30(b) for the columns of $𝐴$ , whose Gram matrix is $𝐴^{*} 𝐴$ . The second proof is Theorem 6.5.5 with $𝐛 = 𝟎$ : the least-squares solutions of $𝐴 𝐱 = 𝟎$ are the solutions of $𝐴 𝐱 =$ ${Pr}_{im 𝐴} (𝟎) =$ $𝟎$ .

Remark 6.5.10 (The conjugate is essential). Both proofs used that

𝐯^{*} 𝐯 = {‖ 𝐯 ‖}^{2}

vanishes only for

𝐯 = 𝟎

. Without the conjugate the proposition fails. For

𝐴 = (\begin{matrix} 1 \\ 𝑖 \end{matrix})

over

ℂ

rank 𝐴 = 1

but

𝐴^{𝖳} 𝐴 = 1 + 𝑖^{2} = 0

. Over

𝔽_{2}

, where there is no inner product at all (Section 6.1),

𝐴 = (\begin{matrix} 1 \\ 1 \end{matrix})

has

𝐴^{𝖳} 𝐴 = 1 + 1 = 0

. Over

ℝ

𝐴^{*} = 𝐴^{𝖳}

, and the proposition says

rank (𝐴^{𝖳} 𝐴) =

rank 𝐴

Corollary 6.5.11 (The least-squares solution for independent columns). If the columns of $𝐴 \in 𝔽^{𝑚 \times 𝑛}$ are linearly independent, then for every $𝐛 \in 𝔽^{𝑚}$ the system $𝐴 𝐱 = 𝐛$ has exactly one least-squares solution,

\hat{𝐱} = {(𝐴^{*} 𝐴)}^{- 1} 𝐴^{*} 𝐛 .

If moreover $𝑚 = 𝑛$ , then $𝐴$ is invertible and $\hat{𝐱} = 𝐴^{- 1} 𝐛$ .

Proof.routine

Uses. Proposition 6.5.9 ( $rank (𝐴^{*} 𝐴) =$ $rank 𝐴$ ), Theorem 6.5.5 (The normal equations), Corollary 3.5.25 (The invertible matrix theorem), Proposition 6.3.27 (Properties of the conjugate transpose), Proposition 2.5.17 (Algebra of inverses)

Hint 1. By Proposition 6.5.9(c),

𝐴^{*} 𝐴

is invertible. What does that say about the normal equations?

Hint 2. For

𝑚 = 𝑛

, write

{(𝐴^{*} 𝐴)}^{- 1} =

𝐴^{- 1} {(𝐴^{*})}^{- 1}

Sketch.

𝐴^{*} 𝐴

is invertible (Proposition 6.5.9(c)), so the normal equations have the single solution

{(𝐴^{*} 𝐴)}^{- 1} 𝐴^{*} 𝐛

, and by Theorem 6.5.5 it is the unique least-squares solution. If

𝐴

is square, it is invertible, and

{(𝐴^{*} 𝐴)}^{- 1} 𝐴^{*} =

𝐴^{- 1} {(𝐴^{*})}^{- 1} 𝐴^{*} =

𝐴^{- 1}

By Proposition 6.5.9(c), $𝐴^{*} 𝐴$ is invertible, so the normal equations $𝐴^{*} 𝐴 𝐱 = 𝐴^{*} 𝐛$ have exactly one solution, ${(𝐴^{*} 𝐴)}^{- 1} 𝐴^{*} 𝐛$ . By Theorem 6.5.5, the least-squares solutions are exactly the solutions of the normal equations.

If $𝑚 = 𝑛$ , then $𝐴$ is a square matrix with independent columns, so it is invertible (Corollary 2.6.24, Corollary 3.5.25), and so is $𝐴^{*}$ (Proposition 6.3.27(c)). By Proposition 2.5.17, ${(𝐴^{*} 𝐴)}^{- 1} =$ $𝐴^{- 1} {(𝐴^{*})}^{- 1}$ , so $\hat{𝐱} =$ $𝐴^{- 1} {(𝐴^{*})}^{- 1} 𝐴^{*} 𝐛 =$ $𝐴^{- 1} 𝐛$ , which is no surprise: $𝐴 𝐱 = 𝐛$ then has an exact solution. □

The formula is good for theory, but to compute $\hat{𝐱}$ by hand one solves the normal equations by row reduction rather than inverting $𝐴^{*} 𝐴$ , as in Example 6.5.7.

Example 6.5.12 (Dependent columns). Let

𝐴 = (\begin{matrix} 1 & 2 \\ 1 & 2 \\ 2 & 4 \end{matrix}), 𝐛 = (\begin{matrix} 1 \\ 2 \\ 0 \end{matrix}) .

The second column is twice the first, so $rank 𝐴 = 1$ and the least-squares solution is not unique. The normal equations are

𝐴^{𝖳} 𝐴 = (\begin{matrix} 6 & 12 \\ 12 & 24 \end{matrix}), 𝐴^{𝖳} 𝐛 = (\begin{matrix} 3 \\ 6 \end{matrix}),

so they reduce to $6 𝑥_{1} + 12 𝑥_{2} = 3$ (the second equation is twice the first). Their solutions are $\hat{𝐱} =$ $(1 / 2, 0) +$ $𝑡 (- 2, 1)$ for $𝑡 \in ℝ$ , a line in $ℝ^{2}$ parallel to $ker 𝐴 =$ $span ((- 2, 1))$ , as Proposition 6.5.2(b) predicts. Each of them gives the same vector $𝐴 \hat{𝐱} =$ $(1 / 2) (1, 1, 2)$ , which is the projection of $𝐛$ onto the line $im 𝐴 =$ $span ((1, 1, 2))$ , namely $(3 / 6) (1, 1, 2)$ . Section 6.5.7 singles out one of these solutions.

6.5.3Projection onto a column space

Theorem 6.4.31 computes the matrix of ${Pr}_{𝑊}$ from an orthonormal basis of $𝑊$ . The normal equations give a formula from any basis, with no Gram–Schmidt step.

Proposition 6.5.13 (Projection onto a column space). Let $𝐴 \in 𝔽^{𝑚 \times 𝑛}$ have linearly independent columns. Then

{Pr}_{im 𝐴} (𝐛) = 𝐴 {(𝐴^{*} 𝐴)}^{- 1} 𝐴^{*} 𝐛 for every 𝐛 \in 𝔽^{𝑚} .

That is, the matrix of ${Pr}_{im 𝐴}$ is $𝑃 = 𝐴 {(𝐴^{*} 𝐴)}^{- 1} 𝐴^{*}$ .

Proof (by the two conditions).routine

Uses. Proposition 6.5.9 ( $rank (𝐴^{*} 𝐴) =$ $rank 𝐴$ ), Theorem 6.4.6 (The projection is characterized by orthogonality), Lemma 6.5.4 (The orthogonal complement of a column space), Theorem 6.4.20 (Orthonormal bases exist)

Techniques. Recognize a projection by its two conditions (Technique 6.4.7)

Hint 1.

𝐴^{*} 𝐴

is invertible by Proposition 6.5.9(c). Let

𝐩 =

𝐴 {(𝐴^{*} 𝐴)}^{- 1} 𝐴^{*} 𝐛

. Check the two conditions of Theorem 6.4.6.

Hint 2.

𝐩 = 𝐴 𝐜

for

𝐜 = {(𝐴^{*} 𝐴)}^{- 1} 𝐴^{*} 𝐛

, so

𝐩 \in im 𝐴

. For the other condition, compute

𝐴^{*} (𝐛 - 𝐩)

and use Lemma 6.5.4.

Sketch. With

𝐜 = {(𝐴^{*} 𝐴)}^{- 1} 𝐴^{*} 𝐛

, the vector

𝐩 = 𝐴 𝐜

lies in

im 𝐴

, and

𝐴^{*} (𝐛 - 𝐩) =

𝐴^{*} 𝐛 -

(𝐴^{*} 𝐴) {(𝐴^{*} 𝐴)}^{- 1} 𝐴^{*} 𝐛 =

𝟎

, so

𝐛 - 𝐩 ⟂ im 𝐴

(Lemma 6.5.4). By Theorem 6.4.6,

𝐩 = {Pr}_{im 𝐴} (𝐛)

By Proposition 6.5.9(c), $𝐴^{*} 𝐴$ is invertible, so $𝑃$ is defined. Let $𝐛 \in 𝔽^{𝑚}$ and $𝐩 = 𝑃 𝐛 = 𝐴 𝐜$ , where $𝐜 = {(𝐴^{*} 𝐴)}^{- 1} 𝐴^{*} 𝐛$ . Then $𝐩 \in im 𝐴$ , and

\begin{aligned} 𝐴^{*} (𝐛 - 𝐩) & = 𝐴^{*} 𝐛 - (𝐴^{*} 𝐴) {(𝐴^{*} 𝐴)}^{- 1} 𝐴^{*} 𝐛 \\ = 𝐴^{*} 𝐛 - 𝐴^{*} 𝐛 = 𝟎, \end{aligned}

so $𝐛 - 𝐩 \in {(im 𝐴)}^{⟂}$ by Lemma 6.5.4. These are the two conditions of Theorem 6.4.6 (for an orthonormal basis of $im 𝐴$ , which exists by Theorem 6.4.20), so $𝐩 = {Pr}_{im 𝐴} (𝐛)$ . □

Proof (by reduction to an orthonormal basis).standard

Uses. Theorem 6.4.31 (The matrix of an orthogonal projection), Theorem 6.4.20 (Orthonormal bases exist), Proposition 6.4.29 (The orthogonal projection as a linear map), Theorem 6.3.29 (Orthonormal columns), Proposition 6.3.27 (Properties of the conjugate transpose), Proposition 2.5.17 (Algebra of inverses), Corollary 3.5.25 (The invertible matrix theorem), Corollary 2.6.24 (The columns decide)

Techniques. Test injectivity at $𝟎$ (Technique 2.6.12)

Hint 1. Let

𝑄

have orthonormal columns forming a basis of

im 𝐴

, so that

{Pr}_{im 𝐴} = 𝑄 𝑄^{*}

. How many columns does

𝑄

have?

Hint 2. Each column of

𝐴

is fixed by

𝑄 𝑄^{*}

, so

𝐴 = 𝑄 𝑆

with

𝑆 = 𝑄^{*} 𝐴 \in 𝔽^{𝑛 \times 𝑛}

. Show that

𝑆

is invertible, and substitute

𝐴 = 𝑄 𝑆

into

𝐴 {(𝐴^{*} 𝐴)}^{- 1} 𝐴^{*}

Sketch. The columns of

𝐴

are a basis of

im 𝐴

, so an orthonormal basis of

im 𝐴

has

𝑛

vectors; let

𝑄 \in 𝔽^{𝑚 \times 𝑛}

have them as columns, so

{Pr}_{im 𝐴} = 𝑄 𝑄^{*}

and

𝑄^{*} 𝑄 = 𝐼_{𝑛}

. Since

𝑄 𝑄^{*}

fixes

im 𝐴

𝐴 = 𝑄 𝑄^{*} 𝐴 = 𝑄 𝑆

with

𝑆 = 𝑄^{*} 𝐴

, which is invertible because

𝑆 𝐱 = 𝟎

gives

𝐴 𝐱 = 𝟎

. Then

𝐴^{*} 𝐴 = 𝑆^{*} 𝑆

and

𝐴 {(𝐴^{*} 𝐴)}^{- 1} 𝐴^{*} =

𝑄 𝑆 𝑆^{- 1} {(𝑆^{*})}^{- 1} 𝑆^{*} 𝑄^{*} =

𝑄 𝑄^{*}

The columns of $𝐴$ are a basis of $im 𝐴$ , so $dim im 𝐴 = 𝑛$ . By Theorem 6.4.20, $im 𝐴$ has an orthonormal basis, which therefore has $𝑛$ vectors $𝐮_{1}, \dots, 𝐮_{𝑛}$ . Let $𝑄 \in 𝔽^{𝑚 \times 𝑛}$ have these columns. By Theorem 6.4.31, ${Pr}_{im 𝐴} = 𝑄 𝑄^{*}$ , and $𝑄^{*} 𝑄 = 𝐼_{𝑛}$ by Theorem 6.3.29. Since ${Pr}_{im 𝐴}$ fixes every vector of $im 𝐴$ (Proposition 6.4.29(b)), it fixes each column of $𝐴$ , so

𝐴 = 𝑄 𝑄^{*} 𝐴 = 𝑄 𝑆 with 𝑆 = 𝑄^{*} 𝐴 \in 𝔽^{𝑛 \times 𝑛} .

The square matrix $𝑆$ is invertible: if $𝑆 𝐱 = 𝟎$ , then $𝐴 𝐱 = 𝑄 𝑆 𝐱 = 𝟎$ , so $𝐱 = 𝟎$ because the columns of $𝐴$ are independent (Corollary 2.6.24), and Corollary 3.5.25 applies. So $𝑆^{*}$ is invertible too (Proposition 6.3.27(c)). Now $𝐴^{*} 𝐴 =$ $𝑆^{*} 𝑄^{*} 𝑄 𝑆 =$ $𝑆^{*} 𝑆$ , so ${(𝐴^{*} 𝐴)}^{- 1} =$ $𝑆^{- 1} {(𝑆^{*})}^{- 1}$ by Proposition 2.5.17, and

𝐴 {(𝐴^{*} 𝐴)}^{- 1} 𝐴^{*} = 𝑄 𝑆 𝑆^{- 1} {(𝑆^{*})}^{- 1} 𝑆^{*} 𝑄^{*} = 𝑄 𝑄^{*} = {Pr}_{im 𝐴},

as desired. □

The first proof is Technique 6.4.7, the method Section 6.4 promised for this formula. The second shows how the formula relates to $𝑄 𝑄^{*}$ : an arbitrary basis of $im 𝐴$ is $𝐴 = 𝑄 𝑆$ for an invertible change-of-basis matrix $𝑆$ , and the factor ${(𝐴^{*} 𝐴)}^{- 1} =$ $𝑆^{- 1} {(𝑆^{*})}^{- 1}$ undoes it. When the columns of $𝐴$ are already orthonormal, $𝐴^{*} 𝐴 = 𝐼_{𝑛}$ and the formula is $𝐴 𝐴^{*}$ , which is Theorem 6.4.31. For a single nonzero column $𝐚$ it is $𝐚 {(𝐚^{*} 𝐚)}^{- 1} 𝐚^{*} =$ $𝐚 𝐚^{*} / (𝐚^{*} 𝐚)$ , the projection onto a line from Section 6.4.

Some consequences can be read off directly. The matrix $𝑃$ satisfies $𝑃^{2} =$ $𝐴 {(𝐴^{*} 𝐴)}^{- 1} (𝐴^{*} 𝐴) {(𝐴^{*} 𝐴)}^{- 1} 𝐴^{*} =$ $𝑃$ and $𝑃^{*} = 𝑃$ , since $𝐴^{*} 𝐴$ is Hermitian, as Proposition 6.4.30 requires. The matrix $𝐼_{𝑚} - 𝑃$ is the projection onto ${(im 𝐴)}^{⟂} = ker 𝐴^{*}$ (Proposition 6.4.29(d), Lemma 6.5.4); it sends $𝐛$ to the residual. The formula needs independent columns, since otherwise $𝐴^{*} 𝐴$ is not invertible. For a matrix with dependent columns, apply it to the matrix of pivot columns of $𝐴$ , which are a basis of $im 𝐴$ (Corollary 3.3.19). In statistics, $𝑃$ is called the hat matrix, because it turns the data $𝐲$ into the fitted values $\hat{𝐲} = 𝑃 𝐲$ .

Example 6.5.14 (A projection matrix from a non-orthogonal basis). The plane $𝑊 =$ ${𝐱 \in ℝ^{3} | 𝑥_{1} + 𝑥_{2} + 𝑥_{3} = 0}$ of Example 6.4.32 has the basis $(1, - 1, 0)$ , $(0, 1, - 1)$ , which is not orthogonal. With these as the columns of $𝐴$ ,

𝐴^{𝖳} 𝐴 = (\begin{matrix} 2 & - 1 \\ - 1 & 2 \end{matrix}), {(𝐴^{𝖳} 𝐴)}^{- 1} = \frac{1}{3} (\begin{matrix} 2 & 1 \\ 1 & 2 \end{matrix}),

and

\begin{aligned} 𝐴 {(𝐴^{𝖳} 𝐴)}^{- 1} 𝐴^{𝖳} & = \frac{1}{3} (\begin{matrix} 1 & 0 \\ - 1 & 1 \\ 0 & - 1 \end{matrix}) (\begin{matrix} 2 & 1 \\ 1 & 2 \end{matrix}) (\begin{matrix} 1 & - 1 & 0 \\ 0 & 1 & - 1 \end{matrix}) \\ = \frac{1}{3} (\begin{matrix} 2 & 1 \\ - 1 & 1 \\ - 1 & - 2 \end{matrix}) (\begin{matrix} 1 & - 1 & 0 \\ 0 & 1 & - 1 \end{matrix}) \\ = \frac{1}{3} (\begin{matrix} 2 & - 1 & - 1 \\ - 1 & 2 & - 1 \\ - 1 & - 1 & 2 \end{matrix}), \end{aligned}

the matrix found in Example 6.4.32 from the normal vector $(1, 1, 1)$ .

Exercise 6.5.15.routine Let

𝐚 = (1, 2, 2)

and

𝐛 = (3, 0, 3)

. Find the matrix

𝑃

of the projection onto

span (𝐚)

with Proposition 6.5.13, the least-squares solution of

𝑥 𝐚 = 𝐛

, and the least-squares error.

Solution.

Uses. Proposition 6.5.13 (Projection onto a column space), Corollary 6.5.11 (The least-squares solution for independent columns), Proposition 6.5.2 (Least squares is projection)

Hint 1. With one column,

𝐴^{𝖳} 𝐴 = 𝐚^{𝖳} 𝐚 = 9

Hint 2.

𝑃 = 𝐚 𝐚^{𝖳} / 9

, and

\hat{𝑥} = 𝐚^{𝖳} 𝐛 / 9

Sketch.

𝑃 =

(1 / 9) (\begin{matrix} 1 & 2 & 2 \\ 2 & 4 & 4 \\ 2 & 4 & 4 \end{matrix})

\hat{𝑥} = 9 / 9 = 1

𝑃 𝐛 = (1, 2, 2)

, and the residual

(2, - 2, 1)

has length

3

Here $𝐴 = 𝐚$ is a single nonzero column, so $𝐴^{𝖳} 𝐴 = 𝐚 \cdot 𝐚 = 9$ and, by Proposition 6.5.13,

𝑃 = \frac{1}{9} 𝐚 𝐚^{𝖳} = \frac{1}{9} (\begin{matrix} 1 & 2 & 2 \\ 2 & 4 & 4 \\ 2 & 4 & 4 \end{matrix}) .

By Corollary 6.5.11, $\hat{𝑥} =$ ${(𝐚^{𝖳} 𝐚)}^{- 1} 𝐚^{𝖳} 𝐛 =$ $(3 + 0 + 6) / 9 =$ $1$ , and indeed $𝑃 𝐛 =$ $\hat{𝑥} 𝐚 =$ $(1, 2, 2)$ . The residual is $𝐛 - 𝐚 = (2, - 2, 1)$ , which is orthogonal to $𝐚$ , and the least-squares error is $‖ (2, - 2, 1) ‖ = 3$ .

6.5.4Linear regression

The most common source of inconsistent systems is data. Suppose we have measured two real quantities $𝑚$ times, with results $(𝑥_{1}, 𝑦_{1}),$ $\dots,$ $(𝑥_{𝑚}, 𝑦_{𝑚})$ , and have reason to expect $𝑦$ to be a linear function of $𝑥$ .

Definition 6.5.16 (Least-squares line). Let $(𝑥_{1}, 𝑦_{1}),$ $\dots,$ $(𝑥_{𝑚}, 𝑦_{𝑚}) \in$ $ℝ^{2}$ be data points. A least-squares line, or regression line, for the data is a line $𝑦 = 𝑐_{0} + 𝑐_{1} 𝑥$ for which

\sum_{𝑖 = 1}^{𝑚} {(𝑦_{𝑖} - 𝑐_{0} - 𝑐_{1} 𝑥_{𝑖})}^{2}

is as small as possible. The numbers $𝑦_{𝑖} -$ $(𝑐_{0} + 𝑐_{1} 𝑥_{𝑖})$ are the residuals of the line.

To turn this into a least-squares problem, let $𝟏 = (1, \dots, 1)$ , $𝐱 = (𝑥_{1}, \dots, 𝑥_{𝑚})$ , and $𝐲 = (𝑦_{1}, \dots, 𝑦_{𝑚})$ in $ℝ^{𝑚}$ , and let $𝐴 \in ℝ^{𝑚 \times 2}$ be the matrix with columns $𝟏$ and $𝐱$ . For $𝐜 = (𝑐_{0}, 𝑐_{1})$ , the $𝑖$ th entry of $𝐴 𝐜$ is $𝑐_{0} + 𝑐_{1} 𝑥_{𝑖}$ , so the sum in Definition 6.5.16 is ${‖ 𝐲 - 𝐴 𝐜 ‖}^{2}$ . Hence $𝑦 = 𝑐_{0} + 𝑐_{1} 𝑥$ is a least-squares line if and only if $𝐜$ is a least-squares solution of $𝐴 𝐜 = 𝐲$ , and the residuals of the line are the entries of the residual vector $𝐲 - 𝐴 𝐜$ . (The lecture writes the line as $𝑦 = 𝑎 + 𝑏 𝑥$ , so $𝑎 = 𝑐_{0}$ and $𝑏 = 𝑐_{1}$ . We keep the letter $𝐛$ for right-hand sides, and the indices match the interactive figures.)

As in Example 6.2.19, the answer is best expressed through the means $𝑚_{𝑥} =$ $(𝑥_{1} + \dots + 𝑥_{𝑚}) / 𝑚$ and $𝑚_{𝑦} =$ $(𝑦_{1} + \dots + 𝑦_{𝑚}) / 𝑚$ and the centered data

\begin{aligned} \tilde{𝐱} & = 𝐱 - 𝑚_{𝑥} 𝟏 = (𝑥_{1} - 𝑚_{𝑥}, \dots, 𝑥_{𝑚} - 𝑚_{𝑥}), \\ \tilde{𝐲} & = 𝐲 - 𝑚_{𝑦} 𝟏 = (𝑦_{1} - 𝑚_{𝑦}, \dots, 𝑦_{𝑚} - 𝑚_{𝑦}) . \end{aligned}

Proposition 6.5.17 (The least-squares line). Let $(𝑥_{1}, 𝑦_{1}),$ $\dots,$ $(𝑥_{𝑚}, 𝑦_{𝑚}) \in$ $ℝ^{2}$ be data points whose $𝑥_{𝑖}$ are not all equal. Then there is exactly one least-squares line $𝑦 = 𝑐_{0} + 𝑐_{1} 𝑥$ , given by

\begin{aligned} 𝑐_{1} & = \frac{\sum_{𝑖 = 1}^{𝑚} (𝑥_{𝑖} - 𝑚_{𝑥}) (𝑦_{𝑖} - 𝑚_{𝑦})}{\sum_{𝑖 = 1}^{𝑚} {(𝑥_{𝑖} - 𝑚_{𝑥})}^{2}} = \frac{\tilde{𝐱} \cdot \tilde{𝐲}}{\tilde{𝐱} \cdot \tilde{𝐱}}, \\ 𝑐_{0} & = 𝑚_{𝑦} - 𝑐_{1} 𝑚_{𝑥} . \end{aligned}

In particular, the line passes through the point $(𝑚_{𝑥}, 𝑚_{𝑦})$ , and its residuals add up to $0$ . If all $𝑥_{𝑖}$ are equal, there are infinitely many least-squares lines.

Proof (by solving the normal equations).routine

Uses. Theorem 6.5.5 (The normal equations), Theorem 6.3.29 (Orthonormal columns), Technique 6.1.9 (A sum of nonnegative terms), Proposition 6.5.2 (Least squares is projection), Corollary 2.6.24 (The columns decide)

Hint 1. Write out

𝐴^{𝖳} 𝐴

and

𝐴^{𝖳} 𝐲

with sums: the entries are

𝟏 \cdot 𝟏 = 𝑚

𝟏 \cdot 𝐱 = \sum_{𝑖} 𝑥_{𝑖}

, and so on.

Hint 2. Divide the first normal equation by

𝑚

to get

𝑐_{0} = 𝑚_{𝑦} - 𝑐_{1} 𝑚_{𝑥}

, and substitute it into the second.

Hint 3. You will need

\sum_{𝑖} {(𝑥_{𝑖} - 𝑚_{𝑥})}^{2} =

\sum_{𝑖} 𝑥_{𝑖}^{2} -

𝑚 𝑚_{𝑥}^{2}

and

\sum_{𝑖} (𝑥_{𝑖} - 𝑚_{𝑥}) (𝑦_{𝑖} - 𝑚_{𝑦}) =

\sum_{𝑖} 𝑥_{𝑖} 𝑦_{𝑖} -

𝑚 𝑚_{𝑥} 𝑚_{𝑦}

Sketch. The normal equations are

𝑚 𝑐_{0} +

(\sum 𝑥_{𝑖}) 𝑐_{1} =

\sum 𝑦_{𝑖}

and

(\sum 𝑥_{𝑖}) 𝑐_{0} +

(\sum 𝑥_{𝑖}^{2}) 𝑐_{1} =

\sum 𝑥_{𝑖} 𝑦_{𝑖}

. The first is

𝑐_{0} + 𝑐_{1} 𝑚_{𝑥} = 𝑚_{𝑦}

; substituting into the second gives

𝑐_{1} (\sum 𝑥_{𝑖}^{2} - 𝑚 𝑚_{𝑥}^{2}) =

\sum 𝑥_{𝑖} 𝑦_{𝑖} -

𝑚 𝑚_{𝑥} 𝑚_{𝑦}

, that is,

𝑐_{1} {‖ \tilde{𝐱} ‖}^{2} = \tilde{𝐱} \cdot \tilde{𝐲}

, and

{‖ \tilde{𝐱} ‖}^{2} > 0

. The first equation also says that

(𝑚_{𝑥}, 𝑚_{𝑦})

lies on the line, and that

𝟏 \cdot (𝐲 - 𝐴 𝐜) = 0

By Theorem 6.3.29, the entries of $𝐴^{𝖳} 𝐴$ and $𝐴^{𝖳} 𝐲$ are dot products:

𝐴^{𝖳} 𝐴 = (\begin{matrix} 𝑚 & \sum_{𝑖} 𝑥_{𝑖} \\ \sum_{𝑖} 𝑥_{𝑖} & \sum_{𝑖} 𝑥_{𝑖}^{2} \end{matrix}), 𝐴^{𝖳} 𝐲 = (\begin{matrix} \sum_{𝑖} 𝑦_{𝑖} \\ \sum_{𝑖} 𝑥_{𝑖} 𝑦_{𝑖} \end{matrix}) .

So the normal equations are

\begin{aligned} 𝑚 𝑐_{0} + (\sum_{𝑖} 𝑥_{𝑖}) 𝑐_{1} & = \sum_{𝑖} 𝑦_{𝑖}, \\ (\sum_{𝑖} 𝑥_{𝑖}) 𝑐_{0} + (\sum_{𝑖} 𝑥_{𝑖}^{2}) 𝑐_{1} & = \sum_{𝑖} 𝑥_{𝑖} 𝑦_{𝑖} . \end{aligned}

Dividing the first by $𝑚$ gives $𝑐_{0} + 𝑐_{1} 𝑚_{𝑥} = 𝑚_{𝑦}$ , that is, $𝑐_{0} = 𝑚_{𝑦} - 𝑐_{1} 𝑚_{𝑥}$ . Substituting this into the second, and using $\sum_{𝑖} 𝑥_{𝑖} = 𝑚 𝑚_{𝑥}$ , gives

𝑐_{1} (\sum_{𝑖} 𝑥_{𝑖}^{2} - 𝑚 𝑚_{𝑥}^{2}) = \sum_{𝑖} 𝑥_{𝑖} 𝑦_{𝑖} - 𝑚 𝑚_{𝑥} 𝑚_{𝑦} .

Expanding the squares and products,

\begin{aligned} \sum_{𝑖} {(𝑥_{𝑖} - 𝑚_{𝑥})}^{2} \\ = \sum_{𝑖} 𝑥_{𝑖}^{2} - 2 𝑚_{𝑥} \sum_{𝑖} 𝑥_{𝑖} + 𝑚 𝑚_{𝑥}^{2} \\ = \sum_{𝑖} 𝑥_{𝑖}^{2} - 𝑚 𝑚_{𝑥}^{2} \end{aligned}

and

\begin{aligned} \sum_{𝑖} (𝑥_{𝑖} - 𝑚_{𝑥}) (𝑦_{𝑖} - 𝑚_{𝑦}) \\ = \sum_{𝑖} 𝑥_{𝑖} 𝑦_{𝑖} - 𝑚_{𝑥} \sum_{𝑖} 𝑦_{𝑖} - 𝑚_{𝑦} \sum_{𝑖} 𝑥_{𝑖} + 𝑚 𝑚_{𝑥} 𝑚_{𝑦} \\ = \sum_{𝑖} 𝑥_{𝑖} 𝑦_{𝑖} - 𝑚 𝑚_{𝑥} 𝑚_{𝑦}, \end{aligned}

so the second equation reads $𝑐_{1} {‖ \tilde{𝐱} ‖}^{2} = \tilde{𝐱} \cdot \tilde{𝐲}$ . Since the $𝑥_{𝑖}$ are not all equal, $\tilde{𝐱} \neq 𝟎$ , and ${‖ \tilde{𝐱} ‖}^{2} > 0$ (Technique 6.1.9). So the normal equations have exactly one solution, the one in the statement, and by Theorem 6.5.5 it is the unique least-squares solution. The first normal equation, $𝑚_{𝑦} = 𝑐_{0} + 𝑐_{1} 𝑚_{𝑥}$ , says that $(𝑚_{𝑥}, 𝑚_{𝑦})$ lies on the line. It is also the equation $𝟏 \cdot (𝐲 - 𝐴 𝐜) = 0$ , so the residuals add up to $0$ .

If all $𝑥_{𝑖}$ are equal, then $𝐱$ is a multiple of $𝟏$ , the columns of $𝐴$ are dependent, and by Proposition 6.5.2 the least-squares solutions form a translate of the line $ker 𝐴$ . Different vectors $𝐜$ give different lines, so there are infinitely many least-squares lines. □

Proof (by centering, which orthogonalizes the columns).standard

Uses. Corollary 6.4.10 (Projecting with an orthogonal list), Proposition 6.3.13 (Orthogonal lists are independent), Proposition 6.5.2 (Least squares is projection), Theorem 6.5.5 (The normal equations)

Techniques. Recognize a projection by its two conditions (Technique 6.4.7)

Hint 1. Compute

𝟏 \cdot \tilde{𝐱}

. What does Gram–Schmidt do to the list

𝟏, 𝐱

Hint 2.

𝟏

and

\tilde{𝐱}

are an orthogonal basis of

im 𝐴

. Project

𝐲

onto

im 𝐴

with Corollary 6.4.10, and rewrite the result in terms of

𝟏

and

𝐱

Sketch.

𝟏 \cdot

\tilde{𝐱} =

\sum_{𝑖} (𝑥_{𝑖} - 𝑚_{𝑥}) =

0

, and

\tilde{𝐱} = 𝐱 - 𝑚_{𝑥} 𝟏

is the second vector Gram–Schmidt produces from

𝟏, 𝐱

. So

𝟏, \tilde{𝐱}

is an orthogonal basis of

im 𝐴

, and

{Pr}_{im 𝐴} (𝐲) =

𝑚_{𝑦} 𝟏 +

𝑐_{1} \tilde{𝐱} =

(𝑚_{𝑦} - 𝑐_{1} 𝑚_{𝑥}) 𝟏 +

𝑐_{1} 𝐱

with

𝑐_{1} =

(𝐲 \cdot \tilde{𝐱}) / {‖ \tilde{𝐱} ‖}^{2} =

(\tilde{𝐲} \cdot \tilde{𝐱}) / {‖ \tilde{𝐱} ‖}^{2}

. This is

𝐴 𝐜

, so

𝐜

is the least-squares solution, unique since the columns are independent.

First, $𝟏 \cdot$ $\tilde{𝐱} =$ $\sum_{𝑖} (𝑥_{𝑖} - 𝑚_{𝑥}) =$ $𝑚 𝑚_{𝑥} -$ $𝑚 𝑚_{𝑥} =$ $0$ , so $\tilde{𝐱} ⟂ 𝟏$ . In fact $\tilde{𝐱} =$ $𝐱 -$ $(⟨ 𝐱, 𝟏 ⟩ / {‖ 𝟏 ‖}^{2}) 𝟏$ is what Gram–Schmidt produces from $𝟏, 𝐱$ . Since the $𝑥_{𝑖}$ are not all equal, $\tilde{𝐱} \neq 𝟎$ ; so $𝟏, \tilde{𝐱}$ is an orthogonal list of nonzero vectors, hence independent (Proposition 6.3.13). It spans $im 𝐴 = span (𝟏, 𝐱)$ , because $\tilde{𝐱} \in span (𝟏, 𝐱)$ and $𝐱 = \tilde{𝐱} + 𝑚_{𝑥} 𝟏$ . So $𝟏, 𝐱$ is independent too.

By Corollary 6.4.10, with $𝐲 \cdot 𝟏 = 𝑚 𝑚_{𝑦}$ and $𝐲 \cdot$ $\tilde{𝐱} =$ $(\tilde{𝐲} + 𝑚_{𝑦} 𝟏) \cdot$ $\tilde{𝐱} =$ $\tilde{𝐲} \cdot$ $\tilde{𝐱}$ ,

\begin{aligned} {Pr}_{im 𝐴} (𝐲) & = \frac{𝐲 \cdot 𝟏}{𝑚} 𝟏 + \frac{𝐲 \cdot \tilde{𝐱}}{{‖ \tilde{𝐱} ‖}^{2}} \tilde{𝐱} = 𝑚_{𝑦} 𝟏 + 𝑐_{1} (𝐱 - 𝑚_{𝑥} 𝟏) \\ = (𝑚_{𝑦} - 𝑐_{1} 𝑚_{𝑥}) 𝟏 + 𝑐_{1} 𝐱 = 𝐴 𝐜, \end{aligned}

with $𝑐_{1} =$ $(\tilde{𝐱} \cdot \tilde{𝐲}) / {‖ \tilde{𝐱} ‖}^{2}$ and $𝑐_{0} = 𝑚_{𝑦} - 𝑐_{1} 𝑚_{𝑥}$ . By Proposition 6.5.2, $𝐜$ is a least-squares solution, and the only one, since the columns of $𝐴$ are independent. The residual $𝐲 - {Pr}_{im 𝐴} (𝐲)$ is orthogonal to $𝟏$ (Theorem 6.5.5), so its entries add up to $0$ , and $𝑐_{0} + 𝑐_{1} 𝑚_{𝑥} = 𝑚_{𝑦}$ says that $(𝑚_{𝑥}, 𝑚_{𝑦})$ is on the line. The case of equal $𝑥_{𝑖}$ is handled as in the first proof. □

The second proof explains the shape of the formula. Centering the $𝑥$ -data is Gram–Schmidt applied to the columns $𝟏, 𝐱$ , and once the columns are orthogonal, the projection splits into two one-dimensional problems: the best constant fit to the data is the mean $𝑚_{𝑦}$ , and the slope is the coefficient of the shadow of $\tilde{𝐲}$ on $\tilde{𝐱}$ . In the plane of the data, centering moves the origin to $(𝑚_{𝑥}, 𝑚_{𝑦})$ , and $𝑐_{1}$ is then the slope of the best line through the new origin (Exercise 6.5.20). When the $𝑦_{𝑖}$ are not all equal, Example 6.2.19 gives $\tilde{𝐱} \cdot$ $\tilde{𝐲} =$ $𝑟 ‖ \tilde{𝐱} ‖ ‖ \tilde{𝐲} ‖$ , where $𝑟$ is the correlation coefficient, so $𝑐_{1} = 𝑟 ‖ \tilde{𝐲} ‖ / ‖ \tilde{𝐱} ‖$ : the slope is the correlation scaled by the ratio of the spreads. Exercise 6.5.40 shows that the squared least-squares error is $(1 - 𝑟^{2}) {‖ \tilde{𝐲} ‖}^{2}$ .

Example 6.5.18 (A spring). A spring hangs from a hook, and its length $𝑦$ (in cm) is measured under loads $𝑥 = 0, 1, 2, 3, 4$ (in newtons):

(0, 10.1), (1, 10.9), (2, 12.2), (3, 12.8), (4, 14.0) .

Hooke’s law predicts $𝑦 = 𝑐_{0} + 𝑐_{1} 𝑥$ , where $𝑐_{0}$ is the natural length and $1 / 𝑐_{1}$ is the stiffness. Here $𝑚_{𝑥} = 2$ and $𝑚_{𝑦} = 60 / 5 = 12$ , so

\tilde{𝐱} = (- 2, - 1, 0, 1, 2), \tilde{𝐲} = (- 1.9, - 1.1, 0.2, 0.8, 2.0) .

Then $\tilde{𝐱} \cdot$ $\tilde{𝐲} =$ $3.8 +$ $1.1 +$ $0 +$ $0.8 +$ $4.0 =$ $9.7$ and $\tilde{𝐱} \cdot \tilde{𝐱} = 10$ , so by Proposition 6.5.17

𝑐_{1} = 0.97, 𝑐_{0} = 12 - 0.97 \cdot 2 = 10.06,

and the least-squares line is $𝑦 = 10.06 + 0.97 𝑥$ : a natural length of about $10.06$ cm and a stiffness of about $1 / 0.97 \approx 1.03$ N/cm. In matrix form, the normal equations were

𝐴^{𝖳} 𝐴 𝐜 = (\begin{matrix} 5 & 10 \\ 10 & 30 \end{matrix}) (\begin{matrix} 𝑐_{0} \\ 𝑐_{1} \end{matrix}) = (\begin{matrix} 60 \\ 129.7 \end{matrix}) = 𝐴^{𝖳} 𝐲 .

The residuals are $0.04$ , $- 0.13$ , $0.20$ , $- 0.17$ , $0.06$ . They add up to $0$ , as Proposition 6.5.17 says, and the least-squares error is $\sqrt{0.091} \approx 0.30$ cm.

The spring data of Example 6.5.18 and the least-squares line

𝑦 = 10.06 + 0.97 𝑥

; the residuals (red) are short. In the interactive version, drag a point to see the normal equations, the coefficients

𝐜

, and the sum of squared residuals change; add or remove points; and switch to a parabola or a cubic (Other models).

Remark 6.5.19 (The calculus derivation). Statistics courses usually find the least-squares line with calculus. The function $𝑆 (𝑐_{0}, 𝑐_{1}) =$ $\sum_{𝑖} {(𝑦_{𝑖} - 𝑐_{0} - 𝑐_{1} 𝑥_{𝑖})}^{2}$ has partial derivatives

\begin{aligned} \frac{𝜕 𝑆}{𝜕 𝑐_{0}} & = - 2 \sum_{𝑖} (𝑦_{𝑖} - 𝑐_{0} - 𝑐_{1} 𝑥_{𝑖}), \\ \frac{𝜕 𝑆}{𝜕 𝑐_{1}} & = - 2 \sum_{𝑖} 𝑥_{𝑖} (𝑦_{𝑖} - 𝑐_{0} - 𝑐_{1} 𝑥_{𝑖}), \end{aligned}

and setting both to $0$ gives $𝟏 \cdot (𝐲 - 𝐴 𝐜) = 0$ and $𝐱 \cdot (𝐲 - 𝐴 𝐜) = 0$ . These are the normal equations, in form (ii) of Theorem 6.5.5. The second proof of Theorem 6.5.5 is this computation without derivatives, and it shows at the same time that the critical point is a minimum, which the calculus argument has to check separately.

Exercise 6.5.20.routine

(a)Show that the line through the origin $𝑦 = 𝑐 𝑥$ that best fits data $(𝑥_{1}, 𝑦_{1}),$ $\dots,$ $(𝑥_{𝑚}, 𝑦_{𝑚})$ , with the $𝑥_{𝑖}$ not all $0$ , in the least-squares sense has $𝑐 =$ $(\sum_{𝑖} 𝑥_{𝑖} 𝑦_{𝑖}) / (\sum_{𝑖} 𝑥_{𝑖}^{2})$ .
(b)Currents $𝐼 =$ $0.5,$ $1.0,$ $1.5,$ $2.0$ (in amperes) through a resistor produce voltages $𝑉 =$ $1.0,$ $2.1,$ $2.9,$ $4.1$ (in volts). Ohm’s law says $𝑉 = 𝑅 𝐼$ . Estimate $𝑅$ .

Solution.

Uses. Corollary 6.5.11 (The least-squares solution for independent columns), Definition 6.5.1 (Least-squares solution)

Hint 1. The design matrix has the single column

𝐱

. What are

𝐱^{𝖳} 𝐱

and

𝐱^{𝖳} 𝐲

Hint 2. For (b),

\sum_{𝑖} 𝐼_{𝑖}^{2} = 7.5

Sketch. (a)

𝐴 = 𝐱

has an independent column since

𝐱 \neq 𝟎

, so

\hat{𝑐} =

{(𝐱^{𝖳} 𝐱)}^{- 1} 𝐱^{𝖳} 𝐲 =

(\sum 𝑥_{𝑖} 𝑦_{𝑖}) / (\sum 𝑥_{𝑖}^{2})

. (b)

\sum 𝐼_{𝑖} 𝑉_{𝑖} =

0.5 +

2.1 +

4.35 +

8.2 =

15.15

and

\sum 𝐼_{𝑖}^{2} = 7.5

, so

𝑅 \approx 2.02

ohms.

(a) The sum $\sum_{𝑖} {(𝑦_{𝑖} - 𝑐 𝑥_{𝑖})}^{2}$ is ${‖ 𝐲 - 𝑐 𝐱 ‖}^{2}$ , so we want the least-squares solution of $𝐴 𝑐 = 𝐲$ for the $𝑚 \times 1$ matrix $𝐴$ with column $𝐱$ . Since $𝐱 \neq 𝟎$ , this column is independent, and by Corollary 6.5.11

\hat{𝑐} = {(𝐱^{𝖳} 𝐱)}^{- 1} 𝐱^{𝖳} 𝐲 = \frac{\sum_{𝑖} 𝑥_{𝑖} 𝑦_{𝑖}}{\sum_{𝑖} 𝑥_{𝑖}^{2}} .

(b) Here $\sum_{𝑖} 𝐼_{𝑖} 𝑉_{𝑖} =$ $0.5 \cdot$ $1.0 +$ $1.0 \cdot$ $2.1 +$ $1.5 \cdot$ $2.9 +$ $2.0 \cdot$ $4.1 =$ $0.5 +$ $2.1 +$ $4.35 +$ $8.2 =$ $15.15$ and $\sum_{𝑖} 𝐼_{𝑖}^{2} =$ $0.25 +$ $1 +$ $2.25 +$ $4 =$ $7.5$ . So $𝑅 \approx 15.15 / 7.5 = 2.02$ ohms. The model has no intercept, because a resistor carries no voltage at zero current; fitting $𝑉 = 𝑐_{0} + 𝑐_{1} 𝐼$ instead would let the data choose a nonzero intercept that the physics rules out.

Other models

Nothing in the line-fitting problem was special to lines. What made it a least-squares problem is that the unknown coefficients enter linearly. A model

𝑦 \approx 𝑐_{0} 𝑓_{0} (𝑥) + 𝑐_{1} 𝑓_{1} (𝑥) + \dots + 𝑐_{𝑛} 𝑓_{𝑛} (𝑥),

with fixed functions $𝑓_{0}, \dots, 𝑓_{𝑛}$ and unknown coefficients $𝑐_{𝑗}$ , leads to the system $𝐴 𝐜 \approx 𝐲$ with entries $𝑎_{𝑖 𝑗} = 𝑓_{𝑗} (𝑥_{𝑖})$ , however nonlinear the $𝑓_{𝑗}$ are. The most important case is fitting a polynomial of degree at most $𝑑$ , where $𝑓_{𝑗} (𝑥) = 𝑥^{𝑗}$ and row $𝑖$ of $𝐴$ is $(1, 𝑥_{𝑖}, 𝑥_{𝑖}^{2}, \dots, 𝑥_{𝑖}^{𝑑})$ . For $𝑚 = 𝑑 + 1$ data points this is the square Vandermonde matrix of Definition 3.4.22.

Proposition 6.5.21 (Polynomial fits). Let $(𝑥_{1}, 𝑦_{1}),$ $\dots,$ $(𝑥_{𝑚}, 𝑦_{𝑚}) \in$ $ℝ^{2}$ , let $𝑑 \geq 0$ , and let $𝐴 \in ℝ^{𝑚 \times (𝑑 + 1)}$ have rows $(1, 𝑥_{𝑖}, 𝑥_{𝑖}^{2}, \dots, 𝑥_{𝑖}^{𝑑})$ .

(a)A polynomial $𝑝 =$ $𝑐_{0} +$ $𝑐_{1} 𝑥 +$ $\dots +$ $𝑐_{𝑑} 𝑥^{𝑑}$ of degree at most $𝑑$ minimizes $\sum_{𝑖} {(𝑦_{𝑖} - 𝑝 (𝑥_{𝑖}))}^{2}$ among all such polynomials if and only if $𝐜 = (𝑐_{0}, \dots, 𝑐_{𝑑})$ is a least-squares solution of $𝐴 𝐜 = 𝐲$ .
(b)The minimizing polynomial is unique if and only if at least $𝑑 + 1$ of the numbers $𝑥_{1}, \dots, 𝑥_{𝑚}$ are distinct.
(c)If $𝑥_{1}, \dots, 𝑥_{𝑚}$ are distinct and $𝑚 = 𝑑 + 1$ , the minimizer is the interpolating polynomial of Theorem 3.4.24, and every residual is $0$ .

Proof.standard

Uses. Definition 1.2.17 (Evaluation), Definition 1.2.13 (Polynomials), Proposition 6.5.2 (Least squares is projection), Lemma 3.4.23 (Too many roots), Corollary 3.4.19 (More unknowns than equations), Theorem 3.4.24 (Polynomial interpolation)

Techniques. Test injectivity at $𝟎$ (Technique 2.6.12)

Hint 1. The

𝑖

th entry of

𝐴 𝐜

𝑝 (𝑥_{𝑖})

. By Proposition 6.5.2(c), uniqueness means

ker 𝐴 = {𝟎}

; what does

𝐴 𝐜 = 𝟎

say about

𝑝

Hint 2. If

𝑑 + 1

of the

𝑥_{𝑖}

are distinct, use Lemma 3.4.23. If at most

𝑑

are distinct, the system

𝐴 𝐜 = 𝟎

has repeated equations; how many different ones?

Sketch. (a)

{(𝐴 𝐜)}_{𝑖} = 𝑝 (𝑥_{𝑖})

, so the sum is

{‖ 𝐲 - 𝐴 𝐜 ‖}^{2}

. (b) Uniqueness means

ker 𝐴 = {𝟎}

, and

𝐴 𝐜 = 𝟎

says

𝑝

vanishes at every

𝑥_{𝑖}

. With

𝑑 + 1

distinct

𝑥_{𝑖}

, Lemma 3.4.23 forces

𝑝 = 𝟎

. With

𝑘 \leq 𝑑

distinct values,

𝐴 𝐜 = 𝟎

is equivalent to a system of

𝑘

equations in

𝑑 + 1 > 𝑘

unknowns, which has a nonzero solution. (c) The interpolating polynomial has error

0

, so it is a minimizer, the only one by (b).

(a) By Definition 1.2.17, the $𝑖$ th entry of $𝐴 𝐜$ is $𝑐_{0} +$ $𝑐_{1} 𝑥_{𝑖} +$ $\dots +$ $𝑐_{𝑑} 𝑥_{𝑖}^{𝑑} =$ $𝑝 (𝑥_{𝑖})$ , so $\sum_{𝑖} {(𝑦_{𝑖} - 𝑝 (𝑥_{𝑖}))}^{2} =$ ${‖ 𝐲 - 𝐴 𝐜 ‖}^{2}$ . Polynomials of degree at most $𝑑$ correspond bijectively to their coefficient vectors $𝐜 \in ℝ^{𝑑 + 1}$ (Definition 1.2.13), so minimizing over $𝑝$ is minimizing over $𝐜$ .

(b) By (a) and Proposition 6.5.2(c), the minimizer is unique if and only if $ker 𝐴 = {𝟎}$ . A vector $𝐜$ lies in $ker 𝐴$ exactly when the corresponding $𝑝$ satisfies $𝑝 (𝑥_{𝑖}) = 0$ for every $𝑖$ .

Suppose $𝑑 + 1$ of the $𝑥_{𝑖}$ are distinct. If $𝐜 \in ker 𝐴$ , then $𝑝$ has degree at most $𝑑$ and vanishes at $𝑑 + 1$ distinct points, so $𝑝 = 𝟎$ by Lemma 3.4.23, and $𝐜 = 𝟎$ .

Suppose instead that the $𝑥_{𝑖}$ take only $𝑘 \leq 𝑑$ distinct values $𝑧_{1}, \dots, 𝑧_{𝑘}$ . Rows of $𝐴$ with the same $𝑥_{𝑖}$ are equal, so $𝐴 𝐜 = 𝟎$ has the same solutions as the system of $𝑘$ equations $𝑐_{0} +$ $𝑐_{1} 𝑧_{𝑙} +$ $\dots +$ $𝑐_{𝑑} 𝑧_{𝑙}^{𝑑} =$ $0$ , $𝑙 = 1, \dots, 𝑘$ , in the $𝑑 + 1 > 𝑘$ unknowns $𝑐_{0}, \dots, 𝑐_{𝑑}$ . By Corollary 3.4.19 it has a nonzero solution, so $ker 𝐴 \neq {𝟎}$ .

(c) By Theorem 3.4.24 there is a polynomial $𝑝$ of degree at most $𝑑 = 𝑚 - 1$ with $𝑝 (𝑥_{𝑖}) = 𝑦_{𝑖}$ for every $𝑖$ . Its residuals are all $0$ , so it is a minimizer, and by (b) it is the only one. □

So the polynomial of degree at most $𝑑$ closest to the data is unique as soon as there are $𝑑 + 1$ distinct $𝑥$ -values, and it interpolates the data when there are exactly that many points. With more points it does not interpolate in general, and it is usually the better model: the high-degree interpolating polynomial passes through every measurement error as well.

Example 6.5.22 (A thrown ball). A ball is thrown upward, and its height $ℎ$ (in meters) is read off a video every half second:

𝑡 = 0, 0.5, 1, 1.5, 2, 2.5, ℎ = 1.0, 5.9, 8.1, 7.9, 5.4, 0.4 .

Without air resistance, $ℎ =$ $ℎ_{0} +$ $𝑣_{0} 𝑡 -$ $(𝑔 / 2) 𝑡^{2}$ with initial height $ℎ_{0}$ , initial speed $𝑣_{0}$ , and gravitational acceleration $𝑔$ , so we fit $ℎ \approx$ $𝑐_{0} +$ $𝑐_{1} 𝑡 +$ $𝑐_{2} 𝑡^{2}$ . Row $𝑖$ of $𝐴$ is $(1, 𝑡_{𝑖}, 𝑡_{𝑖}^{2})$ , and the entries of $𝐴^{𝖳} 𝐴$ and $𝐴^{𝖳} 𝐡$ are the sums $\sum_{𝑖} 𝑡_{𝑖}^{𝑘}$ and $\sum_{𝑖} 𝑡_{𝑖}^{𝑘} ℎ_{𝑖}$ :

𝐴^{𝖳} 𝐴 = (\begin{matrix} 6 & 7.5 & 13.75 \\ 7.5 & 13.75 & 28.125 \\ 13.75 & 28.125 & 61.1875 \end{matrix}), 𝐴^{𝖳} 𝐡 = (\begin{matrix} 28.7 \\ 34.7 \\ 51.45 \end{matrix}) .

There are six distinct $𝑡_{𝑖}$ , so by Proposition 6.5.21 the solution is unique; row reduction gives

\begin{matrix} 𝑐_{0} = \frac{59}{56} \approx 1.054, 𝑐_{1} = \frac{16699}{1400} \approx 11.93, \\ 𝑐_{2} = - \frac{683}{140} \approx - 4.879 . \end{matrix}

So the ball left the hand at about $1.05$ m with speed about $11.9$ m/s, and $𝑔 \approx - 2 𝑐_{2} \approx 9.76 {m/s}^{2}$ , close to the true $9.81$ . The residuals are all smaller than $0.11$ m in absolute value (Figure 6.5.2).

Figure 6.5.2. The heights of Example 6.5.22 and the least-squares parabola

ℎ \approx

1.054 +

11.93 𝑡 -

4.879 𝑡^{2}

. The residuals (red) are barely visible.

Two further variations use the same machinery. With several explanatory variables, say $𝑦 \approx$ $𝑐_{0} +$ $𝑐_{1} 𝑢 +$ $𝑐_{2} 𝑣$ with data $(𝑢_{𝑖}, 𝑣_{𝑖}, 𝑦_{𝑖})$ , the matrix $𝐴$ has the columns $𝟏$ , $𝐮$ , $𝐯$ ; this is multiple regression. And some nonlinear models become linear after a change of variables. Exponential growth $𝑦 = 𝐶 𝑒^{𝑘 𝑥}$ is not linear in $𝐶$ and $𝑘$ , but $ln 𝑦 = ln 𝐶 + 𝑘 𝑥$ is linear in $ln 𝐶$ and $𝑘$ , so one fits a line to the points $(𝑥_{𝑖}, ln 𝑦_{𝑖})$ . This minimizes the squared errors of $ln 𝑦$ , not of $𝑦$ , which roughly means relative rather than absolute errors; it is a different problem with a slightly different answer. How to choose the functions $𝑓_{𝑗}$ , and how to keep a fit with many of them from following the noise, is taken up in Section 16.1.

6.5.5Normal equations in an inner product space

The only place where the proof of Theorem 6.5.5 used $𝔽^{𝑚}$ was in writing the inner products of the columns as the entries of $𝐴^{*} 𝐴$ . In a general inner product space, the Gram matrix (Definition 6.3.28) takes the place of $𝐴^{*} 𝐴$ .

Proposition 6.5.23 (Normal equations for a spanning list). Let $𝑉$ be an inner product space, let $𝐯_{1}, \dots, 𝐯_{𝑛} \in 𝑉$ have Gram matrix $𝐺$ , let $𝑊 =$ $span (𝐯_{1}, \dots, 𝐯_{𝑛})$ , and let $𝐯 \in 𝑉$ . For $𝐜 =$ $(𝑐_{1}, \dots, 𝑐_{𝑛}) \in$ $𝔽^{𝑛}$ ,

𝑐_{1} 𝐯_{1} + \dots + 𝑐_{𝑛} 𝐯_{𝑛} = {Pr}_{𝑊} (𝐯) if and only if 𝐺 𝐜 = 𝐝,

where $𝐝 =$ $(⟨ 𝐯, 𝐯_{1} ⟩, \dots, ⟨ 𝐯, 𝐯_{𝑛} ⟩)$ . The system $𝐺 𝐜 = 𝐝$ always has a solution, and the solution is unique if and only if $𝐯_{1}, \dots, 𝐯_{𝑛}$ is linearly independent.

Proof.routine

Uses. Theorem 6.4.20 (Orthonormal bases exist), Theorem 6.4.6 (The projection is characterized by orthogonality), Proposition 6.3.9 (Properties of $𝐴^{⟂}$ ), Definition 6.3.28 (Gram matrix), Proposition 6.3.30 (Gram matrices detect independence), Corollary 3.5.25 (The invertible matrix theorem)

Techniques. Recognize a projection by its two conditions (Technique 6.4.7), Gram matrices (Technique 6.3.31)

Hint 1. Let

𝐰 = \sum_{𝑗} 𝑐_{𝑗} 𝐯_{𝑗}

. By Theorem 6.4.6,

𝐰 = {Pr}_{𝑊} (𝐯)

if and only if

𝐯 - 𝐰 ⟂ 𝑊

. It suffices to test against

𝐯_{1}, \dots, 𝐯_{𝑛}

Hint 2. Expand

⟨ 𝐰, 𝐯_{𝑖} ⟩ =

\sum_{𝑗} 𝑐_{𝑗} ⟨ 𝐯_{𝑗}, 𝐯_{𝑖} ⟩

and recognize the

𝑖

th entry of

𝐺 𝐜

Sketch. With

𝐰 = \sum_{𝑗} 𝑐_{𝑗} 𝐯_{𝑗}

𝐰 = {Pr}_{𝑊} (𝐯)

iff

⟨ 𝐯 - 𝐰, 𝐯_{𝑖} ⟩ = 0

for all

𝑖

, iff

⟨ 𝐰, 𝐯_{𝑖} ⟩ =

⟨ 𝐯, 𝐯_{𝑖} ⟩

for all

𝑖

, and

⟨ 𝐰, 𝐯_{𝑖} ⟩ =

\sum_{𝑗} 𝑔_{𝑖 𝑗} 𝑐_{𝑗} =

{(𝐺 𝐜)}_{𝑖}

. A solution exists because

{Pr}_{𝑊} (𝐯) \in 𝑊

is some combination of the

𝐯_{𝑗}

; it is unique iff

𝐺

is invertible, iff the list is independent (Proposition 6.3.30).

The subspace $𝑊$ is finite-dimensional, so ${Pr}_{𝑊}$ is defined (Theorem 6.4.20). Let $𝐰 =$ $𝑐_{1} 𝐯_{1} +$ $\dots +$ $𝑐_{𝑛} 𝐯_{𝑛} \in$ $𝑊$ . By Theorem 6.4.6, $𝐰 = {Pr}_{𝑊} (𝐯)$ if and only if $𝐯 - 𝐰 ⟂ 𝑊$ , and by Proposition 6.3.9(c) it suffices to test this against the spanning list: $⟨ 𝐯 - 𝐰, 𝐯_{𝑖} ⟩ = 0$ , that is, $⟨ 𝐰, 𝐯_{𝑖} ⟩ =$ $⟨ 𝐯, 𝐯_{𝑖} ⟩$ , for $𝑖 = 1, \dots, 𝑛$ . By linearity in the first slot and Definition 6.3.28,

⟨ 𝐰, 𝐯_{𝑖} ⟩ = \sum_{𝑗 = 1}^{𝑛} 𝑐_{𝑗} ⟨ 𝐯_{𝑗}, 𝐯_{𝑖} ⟩ = \sum_{𝑗 = 1}^{𝑛} 𝑔_{𝑖 𝑗} 𝑐_{𝑗} = {(𝐺 𝐜)}_{𝑖} .

So $𝐰 = {Pr}_{𝑊} (𝐯)$ if and only if $𝐺 𝐜 = 𝐝$ .

Since ${Pr}_{𝑊} (𝐯) \in 𝑊$ , it equals $\sum_{𝑗} 𝑐_{𝑗} 𝐯_{𝑗}$ for some $𝐜$ , which then solves $𝐺 𝐜 = 𝐝$ . The solution is unique if and only if the square matrix $𝐺$ is invertible (Corollary 3.5.25), that is, by Proposition 6.3.30, if and only if $𝐯_{1}, \dots, 𝐯_{𝑛}$ is linearly independent. □

For $𝑉 = 𝔽^{𝑚}$ with the dot product and $𝐯_{𝑗} = 𝐚_{𝑗}$ , the columns of $𝐴$ , the Gram matrix is $𝐺 = 𝐴^{*} 𝐴$ (Theorem 6.3.29) and $𝑑_{𝑖} =$ $⟨ 𝐛, 𝐚_{𝑖} ⟩ =$ $𝐚_{𝑖}^{*} 𝐛$ is the $𝑖$ th entry of $𝐴^{*} 𝐛$ . So $𝐺 𝐜 = 𝐝$ is the system $𝐴^{*} 𝐴 𝐜 = 𝐴^{*} 𝐛$ , and by Proposition 6.5.2(a) the proposition is Theorem 6.5.5 again. The general version applies when $𝑉$ is a space of functions, where it finds best approximations without orthogonalizing first.

Example 6.5.24 (The line closest to $𝑡^{2}$ ). In $𝐶 [0, 1]$ with $⟨ 𝑓, 𝑔 ⟩ =$ $\int_{0}^{1} 𝑓 (𝑡) 𝑔 (𝑡) d 𝑡$ (Proposition 6.1.13), which line $𝑐_{0} + 𝑐_{1} 𝑡$ minimizes $\int_{0}^{1} {(𝑡^{2} - 𝑐_{0} - 𝑐_{1} 𝑡)}^{2} d 𝑡$ ? Here $𝑊 = span (1, 𝑡)$ , and

\begin{aligned} 𝐺 & = (\begin{matrix} ⟨ 1, 1 ⟩ & ⟨ 𝑡, 1 ⟩ \\ ⟨ 1, 𝑡 ⟩ & ⟨ 𝑡, 𝑡 ⟩ \end{matrix}) = (\begin{matrix} 1 & 1 / 2 \\ 1 / 2 & 1 / 3 \end{matrix}), \\ 𝐝 & = (\begin{matrix} ⟨ 𝑡^{2}, 1 ⟩ \\ ⟨ 𝑡^{2}, 𝑡 ⟩ \end{matrix}) = (\begin{matrix} 1 / 3 \\ 1 / 4 \end{matrix}) . \end{aligned}

The system $𝑐_{0} + 𝑐_{1} / 2 = 1 / 3$ , $𝑐_{0} / 2 + 𝑐_{1} / 3 = 1 / 4$ gives $𝑐_{1} = 1$ and $𝑐_{0} = - 1 / 6$ . So the best line is $𝑡 - 1 / 6$ , and its squared error is

\int_{0}^{1} {(𝑡^{2} - 𝑡 + \frac{1}{6})}^{2} d 𝑡 = \frac{1}{180} .

The chord $𝑡$ through the endpoints of the graph has squared error $\int_{0}^{1} {(𝑡^{2} - 𝑡)}^{2} d 𝑡 =$ $1 / 30$ , six times as large: the best line is the chord lowered by $1 / 6$ .

For polynomials of higher degree the Gram matrix of $1, 𝑡, \dots, 𝑡^{𝑛}$ is the Hilbert matrix of Exercise 6.3.54. It is invertible, but so close to singular that solving $𝐺 𝐜 = 𝐝$ numerically loses most of the accuracy for moderate $𝑛$ . That is why Approximating functions projects onto orthogonal polynomials instead.

Aside (Weighted least squares).Beyond 21-242 Sometimes the equations of an inconsistent system deserve different amounts of trust, for instance measurements made with instruments of different precision. Then one minimizes a weighted sum $\sum_{𝑖} 𝑤_{𝑖} {| 𝑏_{𝑖} - {(𝐴 𝐱)}_{𝑖} |}^{2}$ with weights $𝑤_{𝑖} > 0$ . With $𝐷 =$ $diag (𝑤_{1}, \dots, 𝑤_{𝑚})$ , this sum is ${‖ 𝐛 - 𝐴 𝐱 ‖}_{𝐷}^{2}$ for the weighted dot product ${⟨ 𝐮, 𝐯 ⟩}_{𝐷} = 𝐯^{*} 𝐷 𝐮$ of Example 6.1.21. So the argument of Proposition 6.5.2, run in the inner product space $(𝔽^{𝑚}, {⟨ \cdot, \cdot ⟩}_{𝐷})$ , shows that the minimizers are the $𝐱$ with $𝐴 𝐱 = {Pr}_{im 𝐴} (𝐛)$ , where the projection is now taken with respect to ${⟨ \cdot, \cdot ⟩}_{𝐷}$ . Since ${⟨ 𝐚_{𝑗}, 𝐚_{𝑖} ⟩}_{𝐷} =$ $𝐚_{𝑖}^{*} 𝐷 𝐚_{𝑗}$ and ${⟨ 𝐛, 𝐚_{𝑖} ⟩}_{𝐷} =$ $𝐚_{𝑖}^{*} 𝐷 𝐛$ , Proposition 6.5.23 turns this into the weighted normal equations

𝐴^{*} 𝐷 𝐴 𝐱 = 𝐴^{*} 𝐷 𝐛 .

The same works with $𝐷$ replaced by any positive definite matrix $𝑀$ , since $𝐯^{*} 𝑀 𝐮$ is then an inner product (Proposition 6.1.22). In statistics one takes $𝑤_{𝑖} = 1 / 𝜎_{𝑖}^{2}$ , where $𝜎_{𝑖}$ is the standard deviation of the error in the $𝑖$ th measurement, so that precise measurements count for more. Exercise 6.5.48 gives a second derivation and a computation.

6.5.6Least squares via QR Beyond 21-242

QR factorization is not covered in lecture (Section 6.4.5).

If $𝐴 = 𝑄 𝑅$ is the QR factorization of a matrix with independent columns (Theorem 6.4.38), the normal equations simplify, because $𝑄^{*} 𝑄 = 𝐼_{𝑛}$ .

Proposition 6.5.25 (Least squares via QR). Let $𝐴 \in 𝔽^{𝑚 \times 𝑛}$ have linearly independent columns, and let $𝐴 = 𝑄 𝑅$ be its QR factorization. Then the least-squares solution of $𝐴 𝐱 = 𝐛$ is the unique solution of the upper triangular system

𝑅 \hat{𝐱} = 𝑄^{*} 𝐛 .

Proof.routine

Uses. Theorem 6.4.38 (QR factorization), Theorem 6.3.29 (Orthonormal columns), Proposition 6.3.27 (Properties of the conjugate transpose), Corollary 3.5.25 (The invertible matrix theorem), Theorem 6.5.5 (The normal equations), Corollary 2.6.24 (The columns decide)

Hint 1. Substitute

𝐴 = 𝑄 𝑅

into

𝐴^{*} 𝐴

and

𝐴^{*} 𝐛

, using

𝑄^{*} 𝑄 = 𝐼_{𝑛}

Hint 2. You get

𝑅^{*} 𝑅 𝐱 = 𝑅^{*} 𝑄^{*} 𝐛

. Why may you cancel

𝑅^{*}

Sketch.

𝐴^{*} 𝐴 =

𝑅^{*} 𝑄^{*} 𝑄 𝑅 =

𝑅^{*} 𝑅

and

𝐴^{*} 𝐛 = 𝑅^{*} 𝑄^{*} 𝐛

𝑅

is invertible, since

𝑅 𝐱 = 𝟎

gives

𝐴 𝐱 = 𝟎

, and then so is

𝑅^{*}

. Multiplying by

{(𝑅^{*})}^{- 1}

, the normal equations become

𝑅 𝐱 = 𝑄^{*} 𝐛

By Theorem 6.4.38, $𝑄$ has orthonormal columns, so $𝑄^{*} 𝑄 = 𝐼_{𝑛}$ (Theorem 6.3.29), and by Proposition 6.3.27(b),

𝐴^{*} 𝐴 = 𝑅^{*} 𝑄^{*} 𝑄 𝑅 = 𝑅^{*} 𝑅, 𝐴^{*} 𝐛 = 𝑅^{*} 𝑄^{*} 𝐛 .

The square matrix $𝑅$ is invertible: if $𝑅 𝐱 = 𝟎$ , then $𝐴 𝐱 = 𝑄 𝑅 𝐱 = 𝟎$ , so $𝐱 = 𝟎$ by independence of the columns of $𝐴$ (Corollary 2.6.24, Corollary 3.5.25). Hence $𝑅^{*}$ is invertible (Proposition 6.3.27(c)), and $𝑅^{*} 𝑅 𝐱 = 𝑅^{*} 𝑄^{*} 𝐛$ holds if and only if $𝑅 𝐱 = 𝑄^{*} 𝐛$ . By Theorem 6.5.5, the least-squares solution is the unique solution of $𝑅 𝐱 = 𝑄^{*} 𝐛$ . □

The two sides have a meaning. $𝑄^{*} 𝐛$ is the coordinate vector of ${Pr}_{im 𝐴} (𝐛) =$ $𝑄 𝑄^{*} 𝐛$ with respect to the orthonormal basis formed by the columns of $𝑄$ , and $𝑅$ converts coordinates with respect to the columns of $𝐴$ into coordinates with respect to the columns of $𝑄$ , since $𝐴 𝐱 = 𝑄 (𝑅 𝐱)$ . So $𝑅 \hat{𝐱} = 𝑄^{*} 𝐛$ says that $𝐴 \hat{𝐱}$ and ${Pr}_{im 𝐴} (𝐛)$ have the same coordinates. The system is upper triangular and is solved by back substitution.

Example 6.5.26 (Least squares by QR). For

𝐴 = (\begin{matrix} 1 & 3 \\ 2 & 3 \\ 2 & 0 \end{matrix})

, Exercise 6.4.64 found

𝑄 = \frac{1}{3} (\begin{matrix} 1 & 2 \\ 2 & 1 \\ 2 & - 2 \end{matrix})

and

𝑅 = (\begin{matrix} 3 & 3 \\ 0 & 3 \end{matrix})

. Let

𝐛 = (3, 3, 3)

. Then

𝑄^{𝖳} 𝐛 =

(1 / 3) (3 + 6 + 6, 6 + 3 - 6) =

(5, 1)

, and

𝑅 \hat{𝐱} = (5, 1)

gives

3 {\hat{𝑥}}_{2} = 1

and

3 {\hat{𝑥}}_{1} + 3 {\hat{𝑥}}_{2} = 5

, so

\hat{𝐱} = (4 / 3, 1 / 3)

. The residual

𝐛 -

𝐴 \hat{𝐱} =

(2 / 3, - 2 / 3, 1 / 3)

is orthogonal to both columns of

𝐴

, and the least-squares error is

1

In exact arithmetic there is no reason to prefer QR to the normal equations. In floating-point arithmetic there is: forming $𝐴^{*} 𝐴$ can destroy information that $𝐴$ still contains. Let $𝐴 = (\begin{matrix} 1 & 1 \\ 𝜀 & 0 \\ 0 & 𝜀 \end{matrix})$ with $𝜀 = 10^{- 8}$ . Its columns are independent, and $𝐴^{𝖳} 𝐴 =$ $(\begin{matrix} 1 + 𝜀^{2} & 1 \\ 1 & 1 + 𝜀^{2} \end{matrix})$ . But $𝜀^{2} = 10^{- 16}$ is smaller than half the spacing between double-precision numbers near $1$ (about $2.2 \cdot 10^{- 16}$ ), so the computer stores $1 + 𝜀^{2}$ as $1$ and $𝐴^{𝖳} 𝐴$ as the singular matrix $(\begin{matrix} 1 & 1 \\ 1 & 1 \end{matrix})$ . A QR factorization computed from $𝐴$ itself, with reflections as in Section 9.3, does not square the small entries. Numerical libraries solve least-squares problems this way, or with the singular value decomposition (Section 9.2).

6.5.7The pseudoinverse Beyond 21-242

The pseudoinverse is not covered in lecture; see LADR 6C. Section 9.2 completes the picture with the SVD.

When the columns of $𝐴$ are dependent, the least-squares solutions form a translate $\hat{𝐱} + ker 𝐴$ of the kernel (Example 6.5.12). A natural way to pick one is to take the shortest.

Proposition 6.5.27 (The least-squares solution of minimal norm). Let $𝐴 \in 𝔽^{𝑚 \times 𝑛}$ and $𝐛 \in 𝔽^{𝑚}$ , and let $𝐾 = ker 𝐴$ .

(a)Among the least-squares solutions of $𝐴 𝐱 = 𝐛$ there is exactly one of smallest norm, $𝐱^{+}$ . It is the only least-squares solution in $𝐾^{⟂}$ , and $𝐱^{+} = \hat{𝐱} - {Pr}_{𝐾} (\hat{𝐱})$ for every least-squares solution $\hat{𝐱}$ .
(b)The map $𝔽^{𝑚} \to 𝔽^{𝑛}$ , $𝐛 \mapsto 𝐱^{+}$ , is linear.

Proof.standard

Uses. Proposition 6.5.2 (Least squares is projection), Theorem 6.4.24 (Orthogonal decomposition), Theorem 6.3.3 (Pythagorean theorem), Proposition 6.3.9 (Properties of $𝐴^{⟂}$ ), Theorem 6.5.5 (The normal equations)

Techniques. Orthogonal decomposition (Technique 6.2.4), Uniqueness via two candidates (Technique 1.1.8)

Hint 1. Fix one least-squares solution

\hat{𝐱}

, so that all of them form

\hat{𝐱} + 𝐾

. Split

\hat{𝐱} = {Pr}_{𝐾} (\hat{𝐱}) + 𝐪

with

𝐪 \in 𝐾^{⟂}

(Theorem 6.4.24).

Hint 2. Every least-squares solution is

𝐪 + 𝐳

with

𝐳 \in 𝐾

. Compute

{‖ 𝐪 + 𝐳 ‖}^{2}

with Pythagoras.

Hint 3. For (b),

𝐱^{+}

is the only vector

𝐱

with

𝐱 \in 𝐾^{⟂}

and

𝐴^{*} 𝐴 𝐱 = 𝐴^{*} 𝐛

. Check that

𝑎 𝐱^{+} + 𝐱^{' +}

has both properties for

𝑎 𝐛 + 𝐛^{'}

Sketch. The least-squares solutions are

\hat{𝐱} + 𝐾 = 𝐪 + 𝐾

, where

𝐪 =

\hat{𝐱} -

{Pr}_{𝐾} (\hat{𝐱}) \in

𝐾^{⟂}

. For

𝐳 \in 𝐾

{‖ 𝐪 + 𝐳 ‖}^{2} =

{‖ 𝐪 ‖}^{2} +

{‖ 𝐳 ‖}^{2}

, smallest exactly at

𝐳 = 𝟎

. A least-squares solution in

𝐾^{⟂}

differs from

𝐪

by a vector of

𝐾 \cap 𝐾^{⟂} = {𝟎}

. Linearity:

𝐱^{+}

is characterized by

𝐱^{+} \in 𝐾^{⟂}

and the normal equations, and both conditions are preserved by linear combinations.

(a) Let $\hat{𝐱}$ be a least-squares solution (Proposition 6.5.2(b)). The kernel $𝐾$ is a subspace of the finite-dimensional space $𝔽^{𝑛}$ , so by Theorem 6.4.24 $\hat{𝐱} = {Pr}_{𝐾} (\hat{𝐱}) + 𝐪$ with $𝐪 =$ $\hat{𝐱} -$ ${Pr}_{𝐾} (\hat{𝐱}) \in$ $𝐾^{⟂}$ . By Proposition 6.5.2(b), the least-squares solutions are the vectors $\hat{𝐱} +$ $𝐳 =$ $𝐪 +$ $({Pr}_{𝐾} (\hat{𝐱}) + 𝐳)$ with $𝐳 \in 𝐾$ ; as $𝐳$ runs over $𝐾$ , so does ${Pr}_{𝐾} (\hat{𝐱}) + 𝐳$ . So the least-squares solutions are the vectors $𝐪 + 𝐳^{'}$ with $𝐳^{'} \in 𝐾$ . Since $𝐪 ⟂ 𝐳^{'}$ , Theorem 6.3.3 gives

{‖ 𝐪 + 𝐳^{'} ‖}^{2} = {‖ 𝐪 ‖}^{2} + {‖ 𝐳^{'} ‖}^{2} \geq {‖ 𝐪 ‖}^{2},

with equality if and only if $𝐳^{'} = 𝟎$ . So $𝐱^{+} = 𝐪$ is the unique least-squares solution of smallest norm, and $𝐪 \in 𝐾^{⟂}$ . If $𝐱$ is any least-squares solution in $𝐾^{⟂}$ , then $𝐱 - 𝐪$ lies in $𝐾$ (both are in $𝐪 + 𝐾$ ) and in $𝐾^{⟂}$ (a subspace), so $𝐱 = 𝐪$ by Proposition 6.3.9(d). Since $\hat{𝐱}$ was arbitrary, $𝐱^{+} = \hat{𝐱} - {Pr}_{𝐾} (\hat{𝐱})$ for every least-squares solution $\hat{𝐱}$ .

(b) By (a) and Theorem 6.5.5, $𝐱^{+}$ is the only vector $𝐱$ with $𝐱 \in 𝐾^{⟂}$ and $𝐴^{*} 𝐴 𝐱 = 𝐴^{*} 𝐛$ . Let $𝐛, 𝐛^{'} \in 𝔽^{𝑚}$ have minimal solutions $𝐱^{+}, 𝐱^{' +}$ , and let $𝑎 \in 𝔽$ . Then $𝑎 𝐱^{+} + 𝐱^{' +} \in 𝐾^{⟂}$ , since $𝐾^{⟂}$ is a subspace, and $𝐴^{*} 𝐴 (𝑎 𝐱^{+} + 𝐱^{' +}) =$ $𝑎 𝐴^{*} 𝐛 +$ $𝐴^{*} 𝐛^{'} =$ $𝐴^{*} (𝑎 𝐛 + 𝐛^{'})$ . So $𝑎 𝐱^{+} + 𝐱^{' +}$ is the minimal least-squares solution for $𝑎 𝐛 + 𝐛^{'}$ , which is linearity. □

Definition 6.5.28 (Pseudoinverse). The pseudoinverse of

𝐴 \in 𝔽^{𝑚 \times 𝑛}

is the matrix

𝐴^{+} \in 𝔽^{𝑛 \times 𝑚}

of the linear map

𝐛 \mapsto 𝐱^{+}

of Proposition 6.5.27. That is,

𝐴^{+} 𝐛

is the least-squares solution of

𝐴 𝐱 = 𝐛

of smallest norm.

It is also called the Moore–Penrose inverse. By Proposition 6.5.2(a), $𝐴 𝐴^{+} = {Pr}_{im 𝐴}$ . If the columns of $𝐴$ are independent, the least-squares solution is unique, so $𝐴^{+} = {(𝐴^{*} 𝐴)}^{- 1} 𝐴^{*}$ by Corollary 6.5.11; in particular $𝐴^{+} = 𝐴^{- 1}$ when $𝐴$ is invertible. Exercise 6.5.49 shows $𝐴^{+} 𝐴 = {Pr}_{{(ker 𝐴)}^{⟂}}$ . LADR defines $𝐴^{+}$ differently, as the inverse of the restriction of $𝑇_{𝐴}$ to ${(ker 𝐴)}^{⟂}$ , composed with ${Pr}_{im 𝐴}$ ; by Proposition 6.5.27(a) it is the same matrix.

Example 6.5.29 (A pseudoinverse). Let $𝐴 = (\begin{matrix} 1 & 2 \\ 1 & 2 \\ 2 & 4 \end{matrix})$ as in Example 6.5.12, and $𝐚 = (1, 1, 2)$ , so that $𝐴 𝐱 = (𝑥_{1} + 2 𝑥_{2}) 𝐚$ and $im 𝐴 = span (𝐚)$ . For $𝐛 \in ℝ^{3}$ , ${Pr}_{im 𝐴} (𝐛) =$ $((𝐛 \cdot 𝐚) / 6) 𝐚$ , so the least-squares solutions are the $𝐱$ with $𝑥_{1} +$ $2 𝑥_{2} =$ $(𝐛 \cdot 𝐚) / 6$ . Here $ker 𝐴 =$ $span ((- 2, 1))$ , and ${(ker 𝐴)}^{⟂} =$ $span ((1, 2))$ . The least-squares solution in ${(ker 𝐴)}^{⟂}$ is $𝑠 (1, 2)$ with $5 𝑠 = (𝐛 \cdot 𝐚) / 6$ . So

𝐱^{+} = \frac{𝐛 \cdot 𝐚}{30} (\begin{matrix} 1 \\ 2 \end{matrix}), 𝐴^{+} = \frac{1}{30} (\begin{matrix} 1 & 1 & 2 \\ 2 & 2 & 4 \end{matrix}) .

For $𝐛 = (1, 2, 0)$ , $𝐱^{+} = (1 / 10, 1 / 5)$ , the point of the line of solutions $(1 / 2, 0) + 𝑡 (- 2, 1)$ of Example 6.5.12 closest to $𝟎$ .

Computing $𝐴^{+}$ from the definition means solving a least-squares problem for every $𝐛$ . The singular value decomposition gives $𝐴^{+}$ by a formula, and Section 9.2 finishes the story there.

Exercises

Exercise 6.5.30.routine Find the least-squares solution and the least-squares error of the system

𝑥_{1} + 𝑥_{2} = 2, 𝑥_{1} - 𝑥_{2} = 0, 2 𝑥_{1} + 𝑥_{2} = 5,

and check that the residual is orthogonal to both columns of the coefficient matrix.

Solution.

Uses. Theorem 6.5.5 (The normal equations), Proposition 6.5.9 ( $rank (𝐴^{*} 𝐴) =$ $rank 𝐴$ )

Hint 1. Form

𝐴^{𝖳} 𝐴

and

𝐴^{𝖳} 𝐛

for

𝐴 = (\begin{matrix} 1 & 1 \\ 1 & - 1 \\ 2 & 1 \end{matrix})

and

𝐛 = (2, 0, 5)

Hint 2.

𝐴^{𝖳} 𝐴 = (\begin{matrix} 6 & 2 \\ 2 & 3 \end{matrix})

and

𝐴^{𝖳} 𝐛 = (12, 7)

Sketch. The normal equations

6 𝑥_{1} + 2 𝑥_{2} = 12

2 𝑥_{1} + 3 𝑥_{2} = 7

give

\hat{𝐱} = (11 / 7, 9 / 7)

. The residual is

(- 6, - 2, 4) / 7

, orthogonal to

(1, 1, 2)

and

(1, - 1, 1)

, and the error is

\sqrt{56} / 7 = \sqrt{8 / 7}

Let $𝐴 = (\begin{matrix} 1 & 1 \\ 1 & - 1 \\ 2 & 1 \end{matrix})$ and $𝐛 = (2, 0, 5)$ . Then

\begin{aligned} 𝐴^{𝖳} 𝐴 & = (\begin{matrix} 1 + 1 + 4 & 1 - 1 + 2 \\ 1 - 1 + 2 & 1 + 1 + 1 \end{matrix}) = (\begin{matrix} 6 & 2 \\ 2 & 3 \end{matrix}), \\ 𝐴^{𝖳} 𝐛 & = (\begin{matrix} 2 + 0 + 10 \\ 2 - 0 + 5 \end{matrix}) = (\begin{matrix} 12 \\ 7 \end{matrix}) . \end{aligned}

The columns of $𝐴$ are independent, so by Theorem 6.5.5 and Proposition 6.5.9 the unique least-squares solution solves $6 𝑥_{1} + 2 𝑥_{2} = 12$ , $2 𝑥_{1} + 3 𝑥_{2} = 7$ . Subtracting $3$ times the second equation from the first gives $- 7 𝑥_{2} = - 9$ , so ${\hat{𝑥}}_{2} = 9 / 7$ and ${\hat{𝑥}}_{1} =$ $(7 - 27 / 7) / 2 =$ $11 / 7$ . Then $𝐴 \hat{𝐱} =$ $(20 / 7, 2 / 7, 31 / 7)$ , and the residual is

𝐛 - 𝐴 \hat{𝐱} = \frac{1}{7} (14 - 20, 0 - 2, 35 - 31) = \frac{1}{7} (- 6, - 2, 4) .

Its dot products with the columns are $(- 6 - 2 + 8) / 7 = 0$ and $(- 6 + 2 + 4) / 7 = 0$ . The least-squares error is $‖ 𝐛 -$ $𝐴 \hat{𝐱} ‖ =$ $\sqrt{36 + 4 + 16} / 7 =$ $\sqrt{56} / 7 =$ $\sqrt{8 / 7}$ .

Exercise 6.5.31.routine Find the least-squares solution of $𝐴 𝐱 = 𝐛$ in $ℂ^{3}$ , where

𝐴 = (\begin{matrix} 1 & 𝑖 \\ 1 & - 𝑖 \\ 1 & 1 \end{matrix}), 𝐛 = (\begin{matrix} 2 \\ 0 \\ 1 \end{matrix}),

and the least-squares error.

Solution.

Uses. Theorem 6.5.5 (The normal equations), Definition 6.3.26 (Conjugate transpose), Theorem 6.3.29 (Orthonormal columns)

Hint 1. The entries of

𝐴^{*} 𝐴

are

𝐚_{𝑖}^{*} 𝐚_{𝑗}

; remember to conjugate the entries of

𝐚_{𝑖}

Hint 2.

𝐴^{*} 𝐴 = (\begin{matrix} 3 & 1 \\ 1 & 3 \end{matrix})

and

𝐴^{*} 𝐛 = (3, 1 - 2 𝑖)

Sketch. The normal equations

3 𝑥_{1} + 𝑥_{2} = 3

𝑥_{1} + 3 𝑥_{2} = 1 - 2 𝑖

give

\hat{𝐱} =

(1 + 𝑖 / 4, - 3 𝑖 / 4)

. The residual is

((1 - 𝑖) / 4, (- 1 - 𝑖) / 4, 𝑖 / 2)

, orthogonal to both columns, with squared norm

1 / 2

With $𝐚_{1} = (1, 1, 1)$ and $𝐚_{2} = (𝑖, - 𝑖, 1)$ ,

\begin{matrix} 𝐚_{1}^{*} 𝐚_{1} = 3, 𝐚_{1}^{*} 𝐚_{2} = 𝑖 - 𝑖 + 1 = 1, \\ 𝐚_{2}^{*} 𝐚_{2} = 1 + 1 + 1 = 3, \end{matrix}

and $𝐚_{2}^{*} 𝐚_{1} = 𝐚_{1}^{*} 𝐚_{2} = 1$ . So $𝐴^{*} 𝐴 = (\begin{matrix} 3 & 1 \\ 1 & 3 \end{matrix})$ (Theorem 6.3.29). Also $𝐴^{*} 𝐛 =$ $(2 + 0 + 1, 𝑖 \cdot 2 + - 𝑖 \cdot 0 + 1) =$ $(3, 1 - 2 𝑖)$ . The normal equations are

3 𝑥_{1} + 𝑥_{2} = 3, 𝑥_{1} + 3 𝑥_{2} = 1 - 2 𝑖 .

Subtracting $3$ times the second from the first gives $- 8 𝑥_{2} = 6 𝑖$ , so ${\hat{𝑥}}_{2} = - 3 𝑖 / 4$ , and then ${\hat{𝑥}}_{1} =$ $1 -$ $3 {\hat{𝑥}}_{2} +$ $(- 2 𝑖) =$ $1 +$ $9 𝑖 / 4 -$ $2 𝑖 =$ $1 +$ $𝑖 / 4$ . By Theorem 6.5.5 this is the least-squares solution, and it is unique since $𝐴^{*} 𝐴$ is invertible. Now

\begin{aligned} 𝐴 \hat{𝐱} & = ({\hat{𝑥}}_{1} + 𝑖 {\hat{𝑥}}_{2}, {\hat{𝑥}}_{1} - 𝑖 {\hat{𝑥}}_{2}, {\hat{𝑥}}_{1} + {\hat{𝑥}}_{2}) \\ = (\frac{7}{4} + \frac{𝑖}{4}, \frac{1}{4} + \frac{𝑖}{4}, 1 - \frac{𝑖}{2}), \end{aligned}

so the residual is $𝐛 -$ $𝐴 \hat{𝐱} =$ $((1 - 𝑖) / 4, (- 1 - 𝑖) / 4, 𝑖 / 2)$ . Its inner product with $𝐚_{1}$ is $(1 - 𝑖 - 1 - 𝑖) / 4 +$ $𝑖 / 2 =$ $0$ , and with $𝐚_{2}$ it is $((1 - 𝑖) / 4) 𝑖 +$ $((- 1 - 𝑖) / 4) - 𝑖 +$ $𝑖 / 2 =$ $(- 𝑖 - 1) / 4 +$ $(- 𝑖 + 1) / 4 +$ $𝑖 / 2 =$ $0$ . The squared error is $2 / 16 + 2 / 16 + 1 / 4 = 1 / 2$ .

Exercise 6.5.32.routine A used car of a certain model sells for the following prices $𝑦$ (in thousands of dollars) at ages $𝑥$ (in years):

(1, 21), (2, 19), (3, 16), (4, 15), (5, 12) .

Find the least-squares line and its residuals, and use it to predict the price at age $6$ . What does it predict at age $11$ , and what does that say about extrapolating?

Solution.

Uses. Proposition 6.5.17 (The least-squares line)

Hint 1. Center the data:

𝑚_{𝑥} = 3

and

𝑚_{𝑦} = 16.6

Hint 2.

\tilde{𝐱} = (- 2, - 1, 0, 1, 2)

and

\tilde{𝐲} =

(4.4, 2.4, - 0.6, - 1.6, - 4.6)

Sketch.

\tilde{𝐱} \cdot \tilde{𝐲} = - 22

and

{‖ \tilde{𝐱} ‖}^{2} = 10

, so

𝑐_{1} = - 2.2

and

𝑐_{0} = 16.6 + 6.6 = 23.2

. Residuals

0,

0.2,

- 0.6,

0.6,

- 0.2

. Prediction at

6

10.0

. At

11

- 1.0

, a negative price.

Here $𝑚_{𝑥} = 3$ and $𝑚_{𝑦} = 83 / 5 = 16.6$ , so $\tilde{𝐱} = (- 2, - 1, 0, 1, 2)$ and $\tilde{𝐲} =$ $(4.4, 2.4, - 0.6, - 1.6, - 4.6)$ . Then

\tilde{𝐱} \cdot \tilde{𝐲} = - 8.8 - 2.4 + 0 - 1.6 - 9.2 = - 22, {‖ \tilde{𝐱} ‖}^{2} = 10,

so by Proposition 6.5.17 $𝑐_{1} = - 2.2$ and $𝑐_{0} =$ $16.6 +$ $2.2 \cdot$ $3 =$ $23.2$ . The line is $𝑦 = 23.2 - 2.2 𝑥$ : the car loses about $2.2$ thousand dollars a year. Its values at $𝑥 = 1, \dots, 5$ are $21.0,$ $18.8,$ $16.6,$ $14.4,$ $12.2$ , so the residuals are $0,$ $0.2,$ $- 0.6,$ $0.6,$ $- 0.2$ , which add up to $0$ . At age $6$ it predicts $23.2 - 13.2 = 10.0$ . At age $11$ it predicts $23.2 - 24.2 = - 1.0$ , a negative price. The fit describes the data on the range where it was measured; nothing in least squares says that the linear model stays valid outside that range, and here it clearly does not.

Exercise 6.5.33.standard For the data $(- 1, 2)$ , $(0, 1)$ , $(1, 1)$ , $(2, 4)$ :

(a)find the least-squares line and its squared error;
(b)find the least-squares parabola $𝑦 =$ $𝑐_{0} +$ $𝑐_{1} 𝑥 +$ $𝑐_{2} 𝑥^{2}$ and its squared error;
(c)explain without computing why the error in (b) can be no larger than the one in (a).

Solution.

Uses. Proposition 6.5.17 (The least-squares line), Proposition 6.5.21 (Polynomial fits), Theorem 6.5.5 (The normal equations), Proposition 6.5.2 (Least squares is projection), Theorem 6.4.33 (Best approximation)

Hint 1. For (b),

𝐴^{𝖳} 𝐴

has entries

\sum_{𝑖} 𝑥_{𝑖}^{𝑗 + 𝑘}

; here

𝐴^{𝖳} 𝐴 =

(\begin{matrix} 4 & 2 & 6 \\ 2 & 6 & 8 \\ 6 & 8 & 18 \end{matrix})

and

𝐴^{𝖳} 𝐲 = (8, 7, 19)

Hint 2. For (c), compare the column spaces of the two design matrices.

Sketch. (a)

𝑦 = 1.7 + 0.6 𝑥

with residuals

0.9, - 0.7, - 1.3, 1.1

and squared error

4.2

. (b)

𝑦 = 0.7 - 0.4 𝑥 + 𝑥^{2}

with residuals

- 0.1, 0.3, - 0.3, 0.1

and squared error

0.2

. (c)

span (𝟏, 𝐱) \subseteq

span (𝟏, 𝐱, 𝐱^{2})

, and the distance from

𝐲

to a larger subspace is no larger; equivalently, every line is a parabola with

𝑐_{2} = 0

(a) For the line, $𝐴^{𝖳} 𝐴 = (\begin{matrix} 4 & 2 \\ 2 & 6 \end{matrix})$ and $𝐴^{𝖳} 𝐲 =$ $(2 + 1 + 1 + 4, - 2 + 0 + 1 + 8) =$ $(8, 7)$ . The normal equations $4 𝑐_{0} + 2 𝑐_{1} = 8$ , $2 𝑐_{0} + 6 𝑐_{1} = 7$ give $𝑐_{1} = 3 / 5$ and $𝑐_{0} = 17 / 10$ , so the line is $𝑦 = 1.7 + 0.6 𝑥$ . Its values at $- 1, 0, 1, 2$ are $1.1, 1.7, 2.3, 2.9$ , the residuals are $0.9, - 0.7, - 1.3, 1.1$ , and the squared error is $0.81 +$ $0.49 +$ $1.69 +$ $1.21 =$ $4.2$ .

(b) For the parabola, row $𝑖$ of $𝐴$ is $(1, 𝑥_{𝑖}, 𝑥_{𝑖}^{2})$ , and with $\sum 𝑥_{𝑖} = 2$ , $\sum 𝑥_{𝑖}^{2} = 6$ , $\sum 𝑥_{𝑖}^{3} = 8$ , $\sum 𝑥_{𝑖}^{4} = 18$ , $\sum 𝑦_{𝑖} = 8$ , $\sum 𝑥_{𝑖} 𝑦_{𝑖} = 7$ , $\sum 𝑥_{𝑖}^{2} 𝑦_{𝑖} = 19$ , the normal equations are

\begin{aligned} 4 𝑐_{0} + 2 𝑐_{1} + 6 𝑐_{2} & = 8, \\ 2 𝑐_{0} + 6 𝑐_{1} + 8 𝑐_{2} & = 7, \\ 6 𝑐_{0} + 8 𝑐_{1} + 18 𝑐_{2} & = 19 . \end{aligned}

Row reduction gives $(𝑐_{0}, 𝑐_{1}, 𝑐_{2}) =$ $(7 / 10, - 2 / 5, 1)$ ; check: $2.8 - 0.8 + 6 = 8$ , $1.4 - 2.4 + 8 = 7$ , $4.2 - 3.2 + 18 = 19$ . The four $𝑥_{𝑖}$ are distinct, so this is the unique least-squares parabola (Proposition 6.5.21). Its values are $2.1, 0.7, 1.3, 3.9$ , the residuals are $- 0.1, 0.3, - 0.3, 0.1$ , and the squared error is $0.2$ .

(c) Let $𝐴_{1}$ and $𝐴_{2}$ be the two design matrices. The columns $𝟏, 𝐱$ of $𝐴_{1}$ are also columns of $𝐴_{2}$ , so $im 𝐴_{1} \subseteq im 𝐴_{2}$ . By Proposition 6.5.2(d) the two errors are $dist (𝐲, im 𝐴_{1})$ and $dist (𝐲, im 𝐴_{2})$ , and the distance from $𝐲$ to a larger set is no larger, since Theorem 6.4.33 minimizes over all its points. Concretely, the least-squares line is the parabola with $𝑐_{2} = 0$ , so the best parabola does at least as well. (Exercise 6.5.39 says exactly when the error drops.)

Exercise 6.5.34.standard Let

𝐴 = (\begin{matrix} 1 & 0 \\ 1 & 1 \\ 1 & 2 \end{matrix})

, the matrix of Example 6.5.3. Find all

𝐛 \in ℝ^{3}

for which

(1, 1)

is a least-squares solution of

𝐴 𝐱 = 𝐛

, and describe them geometrically. In terms of data, which data sets

(0, 𝑦_{1}),

(1, 𝑦_{2}),

(2, 𝑦_{3})

have the least-squares line

𝑦 = 1 + 𝑥

Solution.

Uses. Theorem 6.5.5 (The normal equations), Lemma 6.5.4 (The orthogonal complement of a column space)

Hint 1. By Theorem 6.5.5,

(1, 1)

is a least-squares solution exactly when

𝐛 -

𝐴 (1, 1) \in

{(im 𝐴)}^{⟂}

Hint 2.

𝐴 (1, 1) = (1, 2, 3)

, and

{(im 𝐴)}^{⟂} = ker 𝐴^{𝖳}

(Lemma 6.5.4).

Sketch.

{(im 𝐴)}^{⟂} =

ker 𝐴^{𝖳} =

span ((1, - 2, 1))

, so the answer is the line

𝐛 =

(1, 2, 3) +

𝑡 (1, - 2, 1)

𝑡 \in ℝ

, through

𝐴 (1, 1)

perpendicular to the plane

im 𝐴

. The data sets are

(0, 1 + 𝑡),

(1, 2 - 2 𝑡),

(2, 3 + 𝑡)

By Theorem 6.5.5, $(1, 1)$ is a least-squares solution of $𝐴 𝐱 = 𝐛$ if and only if $𝐛 -$ $𝐴 (1, 1) \in$ ${(im 𝐴)}^{⟂}$ . Here $𝐴 (1, 1) = (1, 2, 3)$ , and by Lemma 6.5.4, ${(im 𝐴)}^{⟂} = ker 𝐴^{𝖳}$ , the solutions of $𝑧_{1} + 𝑧_{2} + 𝑧_{3} = 0$ and $𝑧_{2} + 2 𝑧_{3} = 0$ . These give $𝑧_{2} = - 2 𝑧_{3}$ and $𝑧_{1} = 𝑧_{3}$ , so ${(im 𝐴)}^{⟂} =$ $span ((1, - 2, 1))$ . Hence the answer is

{𝐛 \in ℝ^{3} | 𝐛 = (1, 2, 3) + 𝑡 (1, - 2, 1) for some 𝑡 \in ℝ},

the line through the point $𝐴 (1, 1)$ of the plane $im 𝐴$ perpendicular to that plane. The columns of $𝐴$ are independent, so for each such $𝐛$ the vector $(1, 1)$ is the only least-squares solution, and the least-squares error is $| 𝑡 | \sqrt{6}$ , which is $0$ only for $𝐛 = (1, 2, 3)$ . In terms of data, the least-squares line of $(0, 𝑦_{1}),$ $(1, 𝑦_{2}),$ $(2, 𝑦_{3})$ is $𝑦 = 1 + 𝑥$ exactly when $(𝑦_{1}, 𝑦_{2}, 𝑦_{3}) =$ $(1 + 𝑡, 2 - 2 𝑡, 3 + 𝑡)$ for some $𝑡$ : the points are pushed off the line alternately up, down, up, in the pattern $(1, - 2, 1)$ .

Exercise 6.5.35.standard Let $𝐴 \in 𝔽^{𝑚 \times 𝑛}$ and $𝐛, 𝐛^{'} \in 𝔽^{𝑚}$ . Prove or disprove:

(a)If $\hat{𝐱}$ is a least-squares solution of $𝐴 𝐱 = 𝐛$ and ${\hat{𝐱}}^{'}$ is one of $𝐴 𝐱 = 𝐛^{'}$ , then $\hat{𝐱} + {\hat{𝐱}}^{'}$ is a least-squares solution of $𝐴 𝐱 = 𝐛 + 𝐛^{'}$ .
(b)If $𝑈 \in 𝔽^{𝑚 \times 𝑚}$ is unitary, then $𝑈 𝐴 𝐱 = 𝑈 𝐛$ and $𝐴 𝐱 = 𝐛$ have the same least-squares solutions.
(c)If $𝐺 \in 𝔽^{𝑚 \times 𝑚}$ is invertible, then $𝐺 𝐴 𝐱 = 𝐺 𝐛$ and $𝐴 𝐱 = 𝐛$ have the same least-squares solutions.
(d)If $𝑆 \in 𝔽^{𝑛 \times 𝑛}$ is invertible, then $\hat{𝐱}$ is a least-squares solution of $𝐴 𝐱 = 𝐛$ if and only if $𝑆^{- 1} \hat{𝐱}$ is a least-squares solution of $(𝐴 𝑆) 𝐲 = 𝐛$ .

Solution.

Uses. Theorem 6.5.5 (The normal equations), Definition 6.3.33 (Unitary and orthogonal matrices), Proposition 6.3.27 (Properties of the conjugate transpose), Corollary 6.5.11 (The least-squares solution for independent columns)

Techniques. Finding counterexamples and minimal examples (Technique 1.4.18)

Hint 1. For (a), (b), and (d), compare normal equations.

Hint 2. For (c), multiplying one equation by

2

makes its squared error count four times as much. Try a single column

𝐴 = (1, 1)

Sketch. (a) True: the normal equations are linear in

𝐛

. (b) True:

{(𝑈 𝐴)}^{*} (𝑈 𝐴) =

𝐴^{*} 𝐴

and

{(𝑈 𝐴)}^{*} 𝑈 𝐛 = 𝐴^{*} 𝐛

. (c) False:

𝐴 = (1, 1)

𝐛 = (0, 2)

𝐺 = diag (1, 2)

give

\hat{𝑥} = 1

and

\hat{𝑥} = 8 / 5

. (d) True:

𝐲 \mapsto 𝐴 𝑆 𝐲

has the same values as

𝐱 \mapsto 𝐴 𝐱

, reached at

𝐱 = 𝑆 𝐲

(a) True. By Theorem 6.5.5, $𝐴^{*} 𝐴 \hat{𝐱} = 𝐴^{*} 𝐛$ and $𝐴^{*} 𝐴 {\hat{𝐱}}^{'} = 𝐴^{*} 𝐛^{'}$ . Adding, $𝐴^{*} 𝐴 (\hat{𝐱} + {\hat{𝐱}}^{'}) =$ $𝐴^{*} (𝐛 + 𝐛^{'})$ , so $\hat{𝐱} + {\hat{𝐱}}^{'}$ is a least-squares solution of $𝐴 𝐱 = 𝐛 + 𝐛^{'}$ .

(b) True. Since $𝑈^{*} 𝑈 = 𝐼_{𝑚}$ (Definition 6.3.33) and ${(𝑈 𝐴)}^{*} = 𝐴^{*} 𝑈^{*}$ (Proposition 6.3.27(b)),

\begin{aligned} {(𝑈 𝐴)}^{*} (𝑈 𝐴) & = 𝐴^{*} 𝑈^{*} 𝑈 𝐴 = 𝐴^{*} 𝐴, \\ {(𝑈 𝐴)}^{*} (𝑈 𝐛) & = 𝐴^{*} 𝑈^{*} 𝑈 𝐛 = 𝐴^{*} 𝐛 . \end{aligned}

So the two problems have the same normal equations, and by Theorem 6.5.5 the same least-squares solutions. (Geometrically, $𝑈$ preserves lengths, so $‖ 𝑈 𝐛 -$ $𝑈 𝐴 𝐱 ‖ =$ $‖ 𝐛 -$ $𝐴 𝐱 ‖$ .)

(c) False. Let $𝐴 = (\begin{matrix} 1 \\ 1 \end{matrix})$ , $𝐛 = (0, 2)$ , and $𝐺 = diag (1, 2)$ . By Corollary 6.5.11, the least-squares solution of $𝐴 𝑥 = 𝐛$ is $(𝐴^{𝖳} 𝐛) / (𝐴^{𝖳} 𝐴) =$ $2 / 2 =$ $1$ . But $𝐺 𝐴 = (\begin{matrix} 1 \\ 2 \end{matrix})$ and $𝐺 𝐛 = (0, 4)$ , and the least-squares solution of $𝐺 𝐴 𝑥 = 𝐺 𝐛$ is $8 / 5$ . Multiplying an equation by $2$ multiplies its squared error by $4$ , which changes the balance between the equations; this is weighted least squares (Aside (Weighted least squares)).

(d) True. As $𝐲$ runs over $𝔽^{𝑛}$ , so does $𝐱 = 𝑆 𝐲$ , since $𝑆$ is invertible, and $(𝐴 𝑆) 𝐲 = 𝐴 (𝑆 𝐲)$ . So $‖ 𝐛 - 𝐴 𝑆 𝐲 ‖$ takes the same values as $‖ 𝐛 - 𝐴 𝐱 ‖$ , and $𝐲$ minimizes the first if and only if $𝑆 𝐲$ minimizes the second. With $𝐲 = 𝑆^{- 1} \hat{𝐱}$ , this is the claim.

Exercise 6.5.36.routine Let $𝐴 \in 𝔽^{𝑚 \times 𝑛}$ have independent columns. A student computes

𝐴 {(𝐴^{*} 𝐴)}^{- 1} 𝐴^{*} = 𝐴 𝐴^{- 1} {(𝐴^{*})}^{- 1} 𝐴^{*} = 𝐼_{𝑚},

and concludes from Proposition 6.5.13 that ${Pr}_{im 𝐴} = 𝐼_{𝑚}$ , so that every vector of $𝔽^{𝑚}$ lies in $im 𝐴$ and every system $𝐴 𝐱 = 𝐛$ is consistent. Find the error. For which $𝐴$ is the conclusion correct?

Solution.

Uses. Proposition 2.5.17 (Algebra of inverses), Proposition 6.5.13 (Projection onto a column space), Corollary 3.5.25 (The invertible matrix theorem)

Hint 1. The rule

{(𝐵 𝐶)}^{- 1} = 𝐶^{- 1} 𝐵^{- 1}

requires

𝐵

and

𝐶

to be invertible. Are

𝐴

and

𝐴^{*}

Hint 2. Try

𝐴 = (1, 2, 2)

, a single column. When is

im 𝐴 = 𝔽^{𝑚}

Sketch.

{(𝐴^{*} 𝐴)}^{- 1} =

𝐴^{- 1} {(𝐴^{*})}^{- 1}

needs

𝐴

invertible, hence square; for

𝑚 > 𝑛

𝐴

has no inverse. For

𝐴 = (1, 2, 2)

, the projection matrix is

𝐚 𝐚^{𝖳} / 9 \neq 𝐼_{3}

. The conclusion holds exactly when

𝑚 = 𝑛

, that is, when

𝐴

is invertible, and then the computation is valid.

The step ${(𝐴^{*} 𝐴)}^{- 1} =$ $𝐴^{- 1} {(𝐴^{*})}^{- 1}$ applies Proposition 2.5.17 to the factors $𝐴^{*}$ and $𝐴$ , which requires both to be invertible. An invertible matrix is square, so for $𝑚 > 𝑛$ the matrix $𝐴^{- 1}$ does not exist, even though $𝐴^{*} 𝐴$ is invertible. For instance, for the single column $𝐚 = (1, 2, 2)$ the projection matrix is $𝐚 𝐚^{𝖳} / 9$ (Exercise 6.5.15), which has rank $1$ and is not $𝐼_{3}$ . In general ${Pr}_{im 𝐴}$ has rank $dim im 𝐴 = 𝑛$ , so ${Pr}_{im 𝐴} = 𝐼_{𝑚}$ forces $𝑛 = 𝑚$ .

Conversely, if $𝑚 = 𝑛$ , then $𝐴$ is a square matrix with independent columns, hence invertible (Corollary 3.5.25), and so is $𝐴^{*}$ . Then the student’s computation is valid, ${Pr}_{im 𝐴} = 𝐼_{𝑚}$ , and indeed $im 𝐴 = 𝔽^{𝑚}$ .

Exercise 6.5.37.routine

(a)Let $𝐴 \in 𝔽^{𝑚 \times 𝑛}$ , and suppose $𝟏 = (1, \dots, 1) \in im 𝐴$ . Show that the residual of a least-squares solution of $𝐴 𝐱 = 𝐛$ has entries adding up to $0$ , so that the entries of $𝐴 \hat{𝐱}$ have the same mean as those of $𝐛$ .
(b)Part (a) applies to every polynomial fit. Show by an example that the residuals of the least-squares line through the origin, $𝑦 = 𝑐 𝑥$ , need not add up to $0$ .

Solution.

Uses. Theorem 6.5.5 (The normal equations), Exercise 6.5.20

Hint 1. By Theorem 6.5.5(ii), the residual is orthogonal to every vector of

im 𝐴

Hint 2. For (b), two points suffice, for example

(1, 1)

and

(2, 1)

Sketch. (a) The residual

𝐫

is orthogonal to

𝟏 \in im 𝐴

, and

𝐫 \cdot 𝟏 = \sum_{𝑖} 𝑟_{𝑖}

. (b) For

(1, 1), (2, 1)

𝑐 = 3 / 5

and the residuals

2 / 5, - 1 / 5

add up to

1 / 5

(a) Let $𝐫 = 𝐛 - 𝐴 \hat{𝐱}$ . By Theorem 6.5.5, $𝐫 ⟂ im 𝐴$ , and $𝟏 \in im 𝐴$ , so $0 = 𝐫 \cdot 𝟏 = \sum_{𝑖} 𝑟_{𝑖}$ . Hence $\sum_{𝑖} {(𝐴 \hat{𝐱})}_{𝑖} =$ $\sum_{𝑖} 𝑏_{𝑖}$ , and dividing by $𝑚$ , the two vectors have the same mean. For a polynomial fit, $𝟏$ is the first column of the design matrix.

(b) For the data $(1, 1), (2, 1)$ , Exercise 6.5.20 gives $𝑐 =$ $(1 + 2) / (1 + 4) =$ $3 / 5$ . The residuals are $1 - 3 / 5 = 2 / 5$ and $1 - 6 / 5 = - 1 / 5$ , which add up to $1 / 5 \neq 0$ . Here $im 𝐴 = span ((1, 2))$ does not contain $𝟏$ .

Exercise 6.5.38.standard Let $𝐴 \in 𝔽^{𝑚 \times 𝑛}$ have independent columns, and let $𝑃 = 𝐴 {(𝐴^{*} 𝐴)}^{- 1} 𝐴^{*}$ . Without using Proposition 6.5.13, show:

(a) $𝑃^{2} = 𝑃$ and $𝑃^{*} = 𝑃$ ;
(b) $𝑃 𝐴 = 𝐴$ , and $im 𝑃 = im 𝐴$ ;
(c) $tr 𝑃 = 𝑛$ .
(d)Compute $𝑃$ for the regression matrix $𝐴$ with columns $𝟏$ and $𝐱 = (1, 2, 3, 4)$ , and check that $𝑃 𝟏 = 𝟏$ , $𝑃 𝐱 = 𝐱$ , and $tr 𝑃 = 2$ .

Solution.

Uses. Proposition 6.3.27 (Properties of the conjugate transpose), Proposition 2.4.28 (Cyclicity of the trace), Proposition 6.5.9 ( $rank (𝐴^{*} 𝐴) =$ $rank 𝐴$ )

Techniques. Cyclicity of trace (Technique 2.4.29)

Hint 1. For (a), cancel

(𝐴^{*} 𝐴) {(𝐴^{*} 𝐴)}^{- 1}

in the middle of

𝑃^{2}

. For

𝑃^{*}

, note that

𝐴^{*} 𝐴

is Hermitian.

Hint 2. For (b),

im 𝑃 \subseteq im 𝐴

because

𝑃 = 𝐴 (\dots)

; and

𝐴 = 𝑃 𝐴

gives the reverse.

Hint 3. For (c), move the factor

𝐴

from the front to the back with Proposition 2.4.28.

Sketch. (a)

𝑃^{2} =

𝐴 {(𝐴^{*} 𝐴)}^{- 1} (𝐴^{*} 𝐴) {(𝐴^{*} 𝐴)}^{- 1} 𝐴^{*} =

𝑃

, and

𝑃^{*} =

𝐴 {({(𝐴^{*} 𝐴)}^{- 1})}^{*} 𝐴^{*} =

𝑃

since

{(𝐴^{*} 𝐴)}^{*} = 𝐴^{*} 𝐴

. (b)

𝑃 𝐴 = 𝐴

;

im 𝑃 \subseteq

im 𝐴 =

im (𝑃 𝐴) \subseteq

im 𝑃

. (c)

tr (𝐴 {(𝐴^{*} 𝐴)}^{- 1} 𝐴^{*}) =

tr ({(𝐴^{*} 𝐴)}^{- 1} 𝐴^{*} 𝐴) =

tr 𝐼_{𝑛} =

𝑛

. (d)

𝑃 =

(1 / 10) (\begin{matrix} 7 & 4 & 1 & - 2 \\ 4 & 3 & 2 & 1 \\ 1 & 2 & 3 & 4 \\ - 2 & 1 & 4 & 7 \end{matrix})

The matrix $𝐴^{*} 𝐴$ is invertible by Proposition 6.5.9(c), and Hermitian, since ${(𝐴^{*} 𝐴)}^{*} =$ $𝐴^{*} 𝐴^{* *} =$ $𝐴^{*} 𝐴$ by Proposition 6.3.27(a) and (b).

(a) $𝑃^{2} =$ $𝐴 {(𝐴^{*} 𝐴)}^{- 1} (𝐴^{*} 𝐴) {(𝐴^{*} 𝐴)}^{- 1} 𝐴^{*} =$ $𝐴 {(𝐴^{*} 𝐴)}^{- 1} 𝐴^{*} =$ $𝑃$ . By Proposition 6.3.27, $𝑃^{*} =$ ${(𝐴^{*})}^{*} {({(𝐴^{*} 𝐴)}^{- 1})}^{*} 𝐴^{*} =$ $𝐴 {({(𝐴^{*} 𝐴)}^{*})}^{- 1} 𝐴^{*} =$ $𝐴 {(𝐴^{*} 𝐴)}^{- 1} 𝐴^{*} =$ $𝑃$ .

(b) $𝑃 𝐴 =$ $𝐴 {(𝐴^{*} 𝐴)}^{- 1} (𝐴^{*} 𝐴) =$ $𝐴$ . Every $𝑃 𝐲 =$ $𝐴 ({(𝐴^{*} 𝐴)}^{- 1} 𝐴^{*} 𝐲)$ lies in $im 𝐴$ , and every $𝐴 𝐱 = 𝑃 (𝐴 𝐱)$ lies in $im 𝑃$ . So $im 𝑃 = im 𝐴$ .

(c) By Proposition 2.4.28, $tr 𝑃 =$ $tr (𝐴 \cdot {(𝐴^{*} 𝐴)}^{- 1} 𝐴^{*}) =$ $tr ({(𝐴^{*} 𝐴)}^{- 1} 𝐴^{*} \cdot 𝐴) =$ $tr 𝐼_{𝑛} =$ $𝑛$ .

(d) Here $𝐴^{𝖳} 𝐴 = (\begin{matrix} 4 & 10 \\ 10 & 30 \end{matrix})$ , with determinant $20$ , so ${(𝐴^{𝖳} 𝐴)}^{- 1} =$ $(1 / 20) (\begin{matrix} 30 & - 10 \\ - 10 & 4 \end{matrix})$ . Row $𝑖$ of $𝐴$ is $(1, 𝑥_{𝑖})$ , so

𝑝_{𝑖 𝑗} = \frac{1}{20} (30 - 10 (𝑥_{𝑖} + 𝑥_{𝑗}) + 4 𝑥_{𝑖} 𝑥_{𝑗}),

𝑃 = \frac{1}{10} (\begin{matrix} 7 & 4 & 1 & - 2 \\ 4 & 3 & 2 & 1 \\ 1 & 2 & 3 & 4 \\ - 2 & 1 & 4 & 7 \end{matrix}) .

Each row adds up to $10 / 10 = 1$ , so $𝑃 𝟏 = 𝟏$ ; the rows times $(1, 2, 3, 4)$ give $10, 20, 30, 40$ , divided by $10$ , so $𝑃 𝐱 = 𝐱$ ; and $tr 𝑃 =$ $(7 + 3 + 3 + 7) / 10 =$ $2$ . The diagonal entries $𝑝_{𝑖 𝑖}$ are largest at the ends: a data point far from $𝑚_{𝑥}$ pulls harder on the fitted line.

Exercise 6.5.39.standard Let

𝐴 \in 𝔽^{𝑚 \times 𝑛}

𝐚, 𝐛 \in 𝔽^{𝑚}

, and let

𝐴^{'} \in 𝔽^{𝑚 \times (𝑛 + 1)}

𝐴

with

𝐚

appended as a last column. Let

𝐸

and

𝐸^{'}

be the least-squares errors of

𝐴 𝐱 = 𝐛

and

𝐴^{'} 𝐱^{'} = 𝐛

, and let

𝐫

be the residual of a least-squares solution of

𝐴 𝐱 = 𝐛

. Show that

𝐸^{'} \leq 𝐸

, with

𝐸^{'} < 𝐸

if and only if

⟨ 𝐫, 𝐚 ⟩ \neq 0

Solution.

Uses. Theorem 6.5.5 (The normal equations), Proposition 6.5.2 (Least squares is projection), Proposition 6.1.29 (Expanding a norm), Lemma 6.5.4 (The orthogonal complement of a column space)

Techniques. Perturb a minimizer (Technique 6.5.6)

Hint 1. If

\hat{𝐱}

is a least-squares solution for

𝐴

, try

𝐱^{'} = (\hat{𝐱}, 𝑡)

for a scalar

𝑡

. What is its residual?

Hint 2. Its residual is

𝐫 - 𝑡 𝐚

. Expand

{‖ 𝐫 - 𝑡 𝐚 ‖}^{2}

and choose

𝑡 = ⟨ 𝐫, 𝐚 ⟩ / {‖ 𝐚 ‖}^{2}

Hint 3. If

⟨ 𝐫, 𝐚 ⟩ = 0

, check that

(\hat{𝐱}, 0)

satisfies condition (ii) of Theorem 6.5.5 for

𝐴^{'}

Sketch. For

𝐱^{'} = (\hat{𝐱}, 𝑡)

, the residual is

𝐫 - 𝑡 𝐚

, so

𝐸^{' 2} \leq {‖ 𝐫 - 𝑡 𝐚 ‖}^{2}

for every

𝑡

;

𝑡 = 0

gives

𝐸^{'} \leq 𝐸

. If

⟨ 𝐫, 𝐚 ⟩ \neq 0

, then

𝑡 = ⟨ 𝐫, 𝐚 ⟩ / {‖ 𝐚 ‖}^{2}

gives

𝐸^{' 2} \leq

𝐸^{2} -

{| ⟨ 𝐫, 𝐚 ⟩ |}^{2} / {‖ 𝐚 ‖}^{2} <

𝐸^{2}

. If

⟨ 𝐫, 𝐚 ⟩ = 0

, then

𝐫

is orthogonal to every column of

𝐴^{'}

, so

(\hat{𝐱}, 0)

is a least-squares solution for

𝐴^{'}

with residual

𝐫

, and

𝐸^{'} = 𝐸

Let $\hat{𝐱}$ be a least-squares solution of $𝐴 𝐱 = 𝐛$ , so $𝐫 = 𝐛 - 𝐴 \hat{𝐱}$ and $𝐸 = ‖ 𝐫 ‖$ . (By Proposition 6.5.2(a), $𝐫 = 𝐛 - {Pr}_{im 𝐴} (𝐛)$ does not depend on the choice of $\hat{𝐱}$ .) For $𝑡 \in 𝔽$ , the vector $𝐱^{'} = (\hat{𝐱}, 𝑡)$ has $𝐴^{'} 𝐱^{'} = 𝐴 \hat{𝐱} + 𝑡 𝐚$ , so its residual is $𝐫 - 𝑡 𝐚$ , and

𝐸^{' 2} \leq {‖ 𝐫 - 𝑡 𝐚 ‖}^{2} for every 𝑡 \in 𝔽 .

Taking $𝑡 = 0$ gives $𝐸^{'} \leq 𝐸$ .

Suppose $⟨ 𝐫, 𝐚 ⟩ \neq 0$ . Then $𝐚 \neq 𝟎$ ; let $𝑡 = ⟨ 𝐫, 𝐚 ⟩ / {‖ 𝐚 ‖}^{2}$ . By Proposition 6.1.29,

\begin{aligned} {‖ 𝐫 - 𝑡 𝐚 ‖}^{2} & = {‖ 𝐫 ‖}^{2} - 2 Re (𝑡 ⟨ 𝐫, 𝐚 ⟩) + {| 𝑡 |}^{2} {‖ 𝐚 ‖}^{2} \\ = {‖ 𝐫 ‖}^{2} - 2 \frac{{| ⟨ 𝐫, 𝐚 ⟩ |}^{2}}{{‖ 𝐚 ‖}^{2}} + \frac{{| ⟨ 𝐫, 𝐚 ⟩ |}^{2}}{{‖ 𝐚 ‖}^{2}} = 𝐸^{2} - \frac{{| ⟨ 𝐫, 𝐚 ⟩ |}^{2}}{{‖ 𝐚 ‖}^{2}}, \end{aligned}

which is less than $𝐸^{2}$ . So $𝐸^{'} < 𝐸$ .

Suppose $⟨ 𝐫, 𝐚 ⟩ = 0$ . By Theorem 6.5.5(ii), $𝐫$ is orthogonal to the columns of $𝐴$ , and now also to $𝐚$ , so to every column of $𝐴^{'}$ . The vector $(\hat{𝐱}, 0)$ has residual $𝐛 - 𝐴 \hat{𝐱} = 𝐫$ for $𝐴^{'}$ , so by Theorem 6.5.5 it is a least-squares solution of $𝐴^{'} 𝐱^{'} = 𝐛$ , and $𝐸^{'} = ‖ 𝐫 ‖ = 𝐸$ .

In words: adding a column to the design matrix never makes the fit worse, and it makes it strictly better exactly when the new column is correlated with what the old model leaves unexplained. This is also why the error alone cannot decide between models: a model with more columns always wins.

Exercise 6.5.40.standard Let $(𝑥_{1}, 𝑦_{1}),$ $\dots,$ $(𝑥_{𝑚}, 𝑦_{𝑚})$ be data with the $𝑥_{𝑖}$ not all equal and the $𝑦_{𝑖}$ not all equal, let $𝑟$ be their correlation coefficient (Example 6.2.19), and let $𝑦 = 𝑐_{0} + 𝑐_{1} 𝑥$ be their least-squares line.

(a)Show that the residual vector is $\tilde{𝐲} - 𝑐_{1} \tilde{𝐱}$ .
(b)Show that the squared least-squares error is $(1 - 𝑟^{2}) {‖ \tilde{𝐲} ‖}^{2}$ . So the line accounts for the fraction $𝑟^{2}$ of the spread ${‖ \tilde{𝐲} ‖}^{2}$ of the $𝑦$ -values about their mean.
(c)Compute $𝑟^{2}$ for the spring data of Example 6.5.18.

Solution.

Uses. Proposition 6.5.17 (The least-squares line), Proposition 6.1.29 (Expanding a norm), Example 6.2.19 (Correlation is a cosine)

Hint 1. Write

𝐲 = 𝑚_{𝑦} 𝟏 + \tilde{𝐲}

and

𝐴 𝐜 = 𝑐_{0} 𝟏 + 𝑐_{1} 𝐱

, and use

𝑐_{0} = 𝑚_{𝑦} - 𝑐_{1} 𝑚_{𝑥}

Hint 2. Expand

{‖ \tilde{𝐲} - 𝑐_{1} \tilde{𝐱} ‖}^{2}

and substitute

𝑐_{1} =

(\tilde{𝐱} \cdot \tilde{𝐲}) / {‖ \tilde{𝐱} ‖}^{2}

Sketch. (a)

𝐲 -

𝐴 𝐜 =

𝑚_{𝑦} 𝟏 +

\tilde{𝐲} -

(𝑚_{𝑦} - 𝑐_{1} 𝑚_{𝑥}) 𝟏 -

𝑐_{1} 𝐱 =

\tilde{𝐲} -

𝑐_{1} \tilde{𝐱}

. (b)

{‖ \tilde{𝐲} - 𝑐_{1} \tilde{𝐱} ‖}^{2} =

{‖ \tilde{𝐲} ‖}^{2} -

{(\tilde{𝐱} \cdot \tilde{𝐲})}^{2} / {‖ \tilde{𝐱} ‖}^{2} =

{‖ \tilde{𝐲} ‖}^{2} (1 - 𝑟^{2})

. (c)

{‖ \tilde{𝐲} ‖}^{2} = 9.5

and the squared error is

0.091

, so

𝑟^{2} =

1 -

0.091 / 9.5 \approx

0.990

(a) By Proposition 6.5.17, $𝑐_{0} = 𝑚_{𝑦} - 𝑐_{1} 𝑚_{𝑥}$ , so

\begin{aligned} 𝐲 - 𝐴 𝐜 & = (𝑚_{𝑦} 𝟏 + \tilde{𝐲}) - (𝑚_{𝑦} - 𝑐_{1} 𝑚_{𝑥}) 𝟏 - 𝑐_{1} 𝐱 \\ = \tilde{𝐲} - 𝑐_{1} (𝐱 - 𝑚_{𝑥} 𝟏) = \tilde{𝐲} - 𝑐_{1} \tilde{𝐱} . \end{aligned}

(b) By Proposition 6.1.29 (all vectors are real) and $𝑐_{1} =$ $(\tilde{𝐱} \cdot \tilde{𝐲}) / {‖ \tilde{𝐱} ‖}^{2}$ ,

\begin{aligned} {‖ \tilde{𝐲} - 𝑐_{1} \tilde{𝐱} ‖}^{2} & = {‖ \tilde{𝐲} ‖}^{2} - 2 𝑐_{1} (\tilde{𝐱} \cdot \tilde{𝐲}) + 𝑐_{1}^{2} {‖ \tilde{𝐱} ‖}^{2} \\ = {‖ \tilde{𝐲} ‖}^{2} - \frac{{(\tilde{𝐱} \cdot \tilde{𝐲})}^{2}}{{‖ \tilde{𝐱} ‖}^{2}} = {‖ \tilde{𝐲} ‖}^{2} (1 - \frac{{(\tilde{𝐱} \cdot \tilde{𝐲})}^{2}}{{‖ \tilde{𝐱} ‖}^{2} {‖ \tilde{𝐲} ‖}^{2}}), \end{aligned}

and the last fraction is $𝑟^{2}$ . Since the left side is nonnegative, this reproves $𝑟^{2} \leq 1$ , with equality exactly when every residual is $0$ , that is, when the data lie on a line.

(c) For the spring data, ${‖ \tilde{𝐲} ‖}^{2} =$ ${1.9}^{2} +$ ${1.1}^{2} +$ ${0.2}^{2} +$ ${0.8}^{2} +$ ${2.0}^{2} =$ $9.5$ , and the squared error is $0.091$ (Example 6.5.18). So $1 - 𝑟^{2} = 0.091 / 9.5$ , and $𝑟^{2} \approx 0.990$ : the line accounts for $99 %$ of the variation in the lengths.

Exercise 6.5.41.standard Let $(𝑥_{1}, 𝑦_{1}),$ $\dots,$ $(𝑥_{𝑚}, 𝑦_{𝑚})$ be data with the $𝑥_{𝑖}$ not all equal and the $𝑦_{𝑖}$ not all equal, with correlation coefficient $𝑟$ . Let $𝑦 = 𝑐_{0} + 𝑐_{1} 𝑥$ be the least-squares line of $𝑦$ on $𝑥$ , and $𝑥 = 𝑑_{0} + 𝑑_{1} 𝑦$ the least-squares line of $𝑥$ on $𝑦$ (the roles of the coordinates exchanged).

(a)Show that $𝑐_{1} 𝑑_{1} = 𝑟^{2}$ .
(b)Show that both lines pass through $(𝑚_{𝑥}, 𝑚_{𝑦})$ , and that they are the same line if and only if all data points lie on one line.
(c)Find both lines for the data $(0, 0),$ $(1, 2),$ $(2, 1),$ $(3, 3)$ .

Solution.

Uses. Proposition 6.5.17 (The least-squares line), Example 6.2.19 (Correlation is a cosine), Theorem 6.2.1 (Cauchy–Schwarz inequality)

Hint 1. By Proposition 6.5.17 with the roles exchanged,

𝑑_{1} =

(\tilde{𝐱} \cdot \tilde{𝐲}) / {‖ \tilde{𝐲} ‖}^{2}

Hint 2. If

𝑟 \neq 0

, the second line is

𝑦 =

𝑚_{𝑦} +

(1 / 𝑑_{1}) (𝑥 - 𝑚_{𝑥})

. When is

1 / 𝑑_{1} = 𝑐_{1}

Sketch. (a)

𝑐_{1} 𝑑_{1} =

{(\tilde{𝐱} \cdot \tilde{𝐲})}^{2} / ({‖ \tilde{𝐱} ‖}^{2} {‖ \tilde{𝐲} ‖}^{2}) =

𝑟^{2}

. (b) Both lines pass through the means. If

𝑟 = 0

, they are

𝑦 = 𝑚_{𝑦}

and

𝑥 = 𝑚_{𝑥}

. Otherwise they agree iff

𝑐_{1} = 1 / 𝑑_{1}

, iff

𝑟^{2} = 1

, iff the points are collinear (Example 6.2.19). (c)

𝑐_{1} = 𝑑_{1} = 4 / 5

𝑦 = 3 / 10 + (4 / 5) 𝑥

and

𝑦 = - 3 / 8 + (5 / 4) 𝑥

(a) By Proposition 6.5.17, $𝑐_{1} =$ $(\tilde{𝐱} \cdot \tilde{𝐲}) / {‖ \tilde{𝐱} ‖}^{2}$ , and, with the roles of $𝑥$ and $𝑦$ exchanged, $𝑑_{1} =$ $(\tilde{𝐱} \cdot \tilde{𝐲}) / {‖ \tilde{𝐲} ‖}^{2}$ . So

𝑐_{1} 𝑑_{1} = \frac{{(\tilde{𝐱} \cdot \tilde{𝐲})}^{2}}{{‖ \tilde{𝐱} ‖}^{2} {‖ \tilde{𝐲} ‖}^{2}} = 𝑟^{2} .

(b) By Proposition 6.5.17, $𝑚_{𝑦} = 𝑐_{0} + 𝑐_{1} 𝑚_{𝑥}$ and $𝑚_{𝑥} = 𝑑_{0} + 𝑑_{1} 𝑚_{𝑦}$ , so both lines pass through $(𝑚_{𝑥}, 𝑚_{𝑦})$ . If $𝑟 = 0$ , then $𝑐_{1} = 𝑑_{1} = 0$ , and the lines are $𝑦 = 𝑚_{𝑦}$ and $𝑥 = 𝑚_{𝑥}$ , which are different. If $𝑟 \neq 0$ , then $𝑑_{1} \neq 0$ and the second line is $𝑦 =$ $𝑚_{𝑦} +$ $(1 / 𝑑_{1}) (𝑥 - 𝑚_{𝑥})$ . Two lines through the same point coincide exactly when their slopes agree, that is, when $𝑐_{1} = 1 / 𝑑_{1}$ , which by (a) means $𝑟^{2} = 1$ . By Example 6.2.19, $𝑟 = \pm 1$ exactly when all data points lie on one line.

(c) Here $𝑚_{𝑥} = 𝑚_{𝑦} = 3 / 2$ , $\tilde{𝐱} = (- 3, - 1, 1, 3) / 2$ , and $\tilde{𝐲} = (- 3, 1, - 1, 3) / 2$ . So $\tilde{𝐱} \cdot$ $\tilde{𝐲} =$ $(9 - 1 - 1 + 9) / 4 =$ $4$ and ${‖ \tilde{𝐱} ‖}^{2} = {‖ \tilde{𝐲} ‖}^{2} = 5$ . Hence $𝑐_{1} = 𝑑_{1} = 4 / 5$ and $𝑟^{2} = 16 / 25$ . The line of $𝑦$ on $𝑥$ is $𝑦 =$ $3 / 2 +$ $(4 / 5) (𝑥 - 3 / 2) =$ $3 / 10 +$ $(4 / 5) 𝑥$ , and the line of $𝑥$ on $𝑦$ is $𝑦 =$ $3 / 2 +$ $(5 / 4) (𝑥 - 3 / 2) =$ $- 3 / 8 +$ $(5 / 4) 𝑥$ .

Since $𝑟^{2} \leq 1$ , (a) gives $| 𝑐_{1} 𝑑_{1} | \leq 1$ . So when $𝑟 \neq 0$ , $| 𝑐_{1} | \leq 1 / | 𝑑_{1} |$ , and when $𝑟 = 0$ the line of $𝑥$ on $𝑦$ is vertical: either way, the line of $𝑦$ on $𝑥$ is never steeper than the line of $𝑥$ on $𝑦$ . Predictions of $𝑦$ from $𝑥$ are pulled toward the mean $𝑚_{𝑦}$ , which is where the word “regression” comes from.

Exercise 6.5.42.standard Let $𝑦 = 𝑐_{0} + 𝑐_{1} 𝑥$ be the least-squares line for data $(𝑥_{1}, 𝑦_{1}),$ $\dots,$ $(𝑥_{𝑚}, 𝑦_{𝑚})$ with the $𝑥_{𝑖}$ not all equal. Let $𝛼, 𝛾 \neq 0$ and $𝛽, 𝛿 \in ℝ$ , and change units and origins: $𝑥_{𝑖}^{'} = 𝛼 𝑥_{𝑖} + 𝛽$ and $𝑦_{𝑖}^{'} = 𝛾 𝑦_{𝑖} + 𝛿$ . Show that the least-squares line for the new data is the image of the old line under $(𝑥, 𝑦) \mapsto$ $(𝛼 𝑥 + 𝛽, 𝛾 𝑦 + 𝛿)$ , namely

𝑦^{'} = 𝛾 (𝑐_{0} + 𝑐_{1} \frac{𝑥^{'} - 𝛽}{𝛼}) + 𝛿 .

Solution.

Uses. Proposition 6.5.2 (Least squares is projection), Proposition 6.4.29 (The orthogonal projection as a linear map), Proposition 2.6.18 (The column space is spanned by the columns)

Techniques. Recognize a projection by its two conditions (Technique 6.4.7)

Hint 1. Let

𝐴

and

𝐴^{'}

be the design matrices for the old and new data. Compare

im 𝐴

and

im 𝐴^{'}

Hint 2.

im 𝐴 = im 𝐴^{'}

. The fitted values of the new data are

{Pr}_{im 𝐴} (𝛾 𝐲 + 𝛿 𝟏)

; use linearity of the projection and

{Pr}_{im 𝐴} (𝟏) = 𝟏

Sketch.

𝐱^{'} = 𝛼 𝐱 + 𝛽 𝟏

and

𝐱 = (𝐱^{'} - 𝛽 𝟏) / 𝛼

, so

im 𝐴^{'} =

span (𝟏, 𝐱^{'}) =

span (𝟏, 𝐱) =

im 𝐴

. By linearity,

Pr (𝐲^{'}) =

𝛾 Pr (𝐲) +

𝛿 𝟏 =

𝛾 (𝑐_{0} 𝟏 + 𝑐_{1} 𝐱) +

𝛿 𝟏

; substituting

𝐱 = (𝐱^{'} - 𝛽 𝟏) / 𝛼

writes this as

𝐴^{'} 𝐜^{'}

with the coefficients of the claimed line.

Let $𝐴$ and $𝐴^{'}$ have columns $𝟏, 𝐱$ and $𝟏, 𝐱^{'}$ . Since $𝐱^{'} = 𝛼 𝐱 + 𝛽 𝟏$ and $𝐱 = (𝐱^{'} - 𝛽 𝟏) / 𝛼$ , each pair of columns lies in the span of the other, so $𝑊 = im 𝐴 = im 𝐴^{'}$ (Proposition 2.6.18). The $𝑥_{𝑖}^{'}$ are not all equal, so the new least-squares line is unique, and by Proposition 6.5.2(a) its fitted values are ${Pr}_{𝑊} (𝐲^{'})$ . By linearity of ${Pr}_{𝑊}$ (Proposition 6.4.29(a)), ${Pr}_{𝑊} (𝟏) = 𝟏$ , and ${Pr}_{𝑊} (𝐲) =$ $𝑐_{0} 𝟏 +$ $𝑐_{1} 𝐱$ ,

\begin{aligned} {Pr}_{𝑊} (𝐲^{'}) & = 𝛾 {Pr}_{𝑊} (𝐲) + 𝛿 {Pr}_{𝑊} (𝟏) = 𝛾 (𝑐_{0} 𝟏 + 𝑐_{1} 𝐱) + 𝛿 𝟏 \\ = (𝛾 𝑐_{0} + 𝛿 - \frac{𝛾 𝑐_{1} 𝛽}{𝛼}) 𝟏 + \frac{𝛾 𝑐_{1}}{𝛼} 𝐱^{'} . \end{aligned}

So the new line is $𝑦^{'} = 𝑐_{0}^{'} + 𝑐_{1}^{'} 𝑥^{'}$ with $𝑐_{1}^{'} = 𝛾 𝑐_{1} / 𝛼$ and $𝑐_{0}^{'} =$ $𝛾 𝑐_{0} +$ $𝛿 -$ $𝛾 𝑐_{1} 𝛽 / 𝛼$ , which is $𝑦^{'} =$ $𝛾 (𝑐_{0} + 𝑐_{1} (𝑥^{'} - 𝛽) / 𝛼) +$ $𝛿$ , as claimed. Measuring in other units, or from another origin, therefore gives the same fitted line. That fails for a nonlinear change such as $𝑥^{'} = 𝑥^{2}$ , which changes the column space.

Exercise 6.5.43.standard In

𝐶 [0, 1]

with

⟨ 𝑓, 𝑔 ⟩ =

\int_{0}^{1} 𝑓 (𝑡) 𝑔 (𝑡) d 𝑡

, find the polynomial

𝑝

of degree at most

2

closest to

𝑓 (𝑡) = \sqrt{𝑡}

, using Proposition 6.5.23, and compute

{‖ 𝑓 - 𝑝 ‖}^{2}

. Compare with the best line.

Solution.

Uses. Proposition 6.5.23 (Normal equations for a spanning list), Theorem 6.4.33 (Best approximation), Proposition 6.4.4 (Properties of ${Pr}_{𝒪︀}$ )

Techniques. Gram matrices (Technique 6.3.31)

Hint 1. The Gram matrix of

1, 𝑡, 𝑡^{2}

has entries

⟨ 𝑡^{𝑗}, 𝑡^{𝑖} ⟩ =

1 / (𝑖 + 𝑗 + 1)

, and

⟨ \sqrt{𝑡}, 𝑡^{𝑖} ⟩ =

1 / (𝑖 + 3 / 2) =

2 / (2 𝑖 + 3)

Hint 2. Clear denominators: the equations become

6 𝑐_{0} + 3 𝑐_{1} + 2 𝑐_{2} = 4

6 𝑐_{0} +

4 𝑐_{1} +

3 𝑐_{2} =

24 / 5

20 𝑐_{0} +

15 𝑐_{1} +

12 𝑐_{2} =

120 / 7

. For the error,

{‖ 𝑓 - 𝑝 ‖}^{2} =

{‖ 𝑓 ‖}^{2} -

⟨ 𝑝, 𝑓 ⟩

because

𝑓 - 𝑝 ⟂ 𝑝

Sketch.

𝐺 =

(\begin{matrix} 1 & 1 / 2 & 1 / 3 \\ 1 / 2 & 1 / 3 & 1 / 4 \\ 1 / 3 & 1 / 4 & 1 / 5 \end{matrix})

𝐝 = (2 / 3, 2 / 5, 2 / 7)

, solution

𝑝 =

6 / 35 +

(48 / 35) 𝑡 -

(4 / 7) 𝑡^{2}

. Then

{‖ 𝑓 - 𝑝 ‖}^{2} =

1 / 2 -

612 / 1225 =

1 / 2450

. The best line is

4 / 15 + (4 / 5) 𝑡

, with squared error

1 / 450

Let $𝑊$ be the polynomials of degree at most $2$ . By Proposition 6.5.23 with the list $1, 𝑡, 𝑡^{2}$ , the coefficients of $𝑝 =$ ${Pr}_{𝑊} (𝑓) =$ $𝑐_{0} +$ $𝑐_{1} 𝑡 +$ $𝑐_{2} 𝑡^{2}$ solve $𝐺 𝐜 = 𝐝$ , where $𝑔_{𝑖 𝑗} =$ $\int_{0}^{1} 𝑡^{𝑖 + 𝑗} d 𝑡 =$ $1 / (𝑖 + 𝑗 + 1)$ (indices from $0$ ) and $𝑑_{𝑖} =$ $\int_{0}^{1} 𝑡^{𝑖 + 1 / 2} d 𝑡 =$ $2 / (2 𝑖 + 3)$ :

\begin{aligned} 𝑐_{0} + \frac{𝑐_{1}}{2} + \frac{𝑐_{2}}{3} & = \frac{2}{3}, \\ \frac{𝑐_{0}}{2} + \frac{𝑐_{1}}{3} + \frac{𝑐_{2}}{4} & = \frac{2}{5}, \\ \frac{𝑐_{0}}{3} + \frac{𝑐_{1}}{4} + \frac{𝑐_{2}}{5} & = \frac{2}{7} . \end{aligned}

Multiplying by $6$ , $12$ , and $60$ gives $6 𝑐_{0} + 3 𝑐_{1} + 2 𝑐_{2} = 4$ , $6 𝑐_{0} +$ $4 𝑐_{1} +$ $3 𝑐_{2} =$ $24 / 5$ , and $20 𝑐_{0} +$ $15 𝑐_{1} +$ $12 𝑐_{2} =$ $120 / 7$ . The second minus the first is $𝑐_{1} + 𝑐_{2} = 4 / 5$ . The third minus $10 / 3$ times the first is $5 𝑐_{1} +$ $(16 / 3) 𝑐_{2} =$ $120 / 7 -$ $40 / 3 =$ $80 / 21$ , that is, $15 𝑐_{1} + 16 𝑐_{2} = 80 / 7$ . Substituting $𝑐_{1} = 4 / 5 - 𝑐_{2}$ gives $12 + 𝑐_{2} = 80 / 7$ , so $𝑐_{2} = - 4 / 7$ , $𝑐_{1} = 48 / 35$ , and $𝑐_{0} =$ $(4 - 144 / 35 + 8 / 7) / 6 =$ $6 / 35$ . So

𝑝 (𝑡) = \frac{6}{35} + \frac{48}{35} 𝑡 - \frac{4}{7} 𝑡^{2} .

Since $𝑓 - 𝑝 ⟂ 𝑊$ and $𝑝 \in 𝑊$ (Proposition 6.4.4), ${‖ 𝑓 - 𝑝 ‖}^{2} =$ $⟨ 𝑓 - 𝑝, 𝑓 ⟩ =$ ${‖ 𝑓 ‖}^{2} -$ $⟨ 𝑝, 𝑓 ⟩$ , and $⟨ 𝑝, 𝑓 ⟩ =$ $\sum_{𝑖} 𝑐_{𝑖} 𝑑_{𝑖} =$ $(6 / 35) (2 / 3) +$ $(48 / 35) (2 / 5) -$ $(4 / 7) (2 / 7) =$ $612 / 1225$ . With ${‖ 𝑓 ‖}^{2} =$ $\int_{0}^{1} 𝑡 d 𝑡 =$ $1 / 2$ ,

{‖ 𝑓 - 𝑝 ‖}^{2} = \frac{1}{2} - \frac{612}{1225} = \frac{1}{2450} .

For the best line, drop $𝑐_{2}$ and the third equation: $𝑐_{0} + 𝑐_{1} / 2 = 2 / 3$ and $𝑐_{0} / 2 + 𝑐_{1} / 3 = 2 / 5$ give $4 / 15 + (4 / 5) 𝑡$ , with squared error $1 / 2 -$ $(8 / 45 + 8 / 25) =$ $1 / 450$ . Allowing $𝑡^{2}$ reduces the squared error by a factor of $5.4$ , and changes the constant and linear coefficients too, because $1, 𝑡, 𝑡^{2}$ are not orthogonal.

Exercise 6.5.44.standard Over any field $𝐹$ , the equations $𝐴^{𝖳} 𝐴 𝐱 = 𝐴^{𝖳} 𝐛$ make sense for $𝐴 \in 𝐹^{𝑚 \times 𝑛}$ and $𝐛 \in 𝐹^{𝑚}$ , even though there is no inner product. Prove or disprove:

(a)For every $𝐴 \in 𝔽_{2}^{𝑚 \times 𝑛}$ and $𝐛 \in 𝔽_{2}^{𝑚}$ , the system $𝐴^{𝖳} 𝐴 𝐱 = 𝐴^{𝖳} 𝐛$ has a solution.
(b)If $𝐴 \in 𝔽_{2}^{𝑚 \times 𝑛}$ has independent columns, then $𝐴^{𝖳} 𝐴$ is invertible.
(c)Both statements hold over $ℝ$ .

Solution.

Uses. Theorem 6.5.5 (The normal equations), Proposition 6.5.9 ( $rank (𝐴^{*} 𝐴) =$ $rank 𝐴$ ), Remark 6.5.10 (The conjugate is essential)

Techniques. Finding counterexamples and minimal examples (Technique 1.4.18)

Hint 1. Look for a nonzero column

𝐚 \in 𝔽_{2}^{𝑚}

with

𝐚^{𝖳} 𝐚 = 0

Hint 2.

𝐚 = (1, 1)

works. For (a), choose

𝐛

with

𝐚^{𝖳} 𝐛 = 1

Sketch. (a) False:

𝐴 = (\begin{matrix} 1 \\ 1 \end{matrix})

and

𝐛 = (1, 0)

give

0 𝑥 = 1

. (b) False: the same

𝐴

has an independent column and

𝐴^{𝖳} 𝐴 = 0

. (c) True: over

ℝ

𝐴^{𝖳} = 𝐴^{*}

, so these are Theorem 6.5.5 and Proposition 6.5.9(c).

(a) False. Let $𝐴 = (\begin{matrix} 1 \\ 1 \end{matrix}) \in 𝔽_{2}^{2 \times 1}$ and $𝐛 = (1, 0)$ . Then $𝐴^{𝖳} 𝐴 = 1 + 1 = 0$ and $𝐴^{𝖳} 𝐛 = 1$ , so the system reads $0 𝑥 = 1$ , which has no solution.

(b) False. The same $𝐴$ has a single nonzero, hence independent, column, but $𝐴^{𝖳} 𝐴 = 0$ is not invertible.

(c) True. Over $ℝ$ , $𝐴^{𝖳} = 𝐴^{*}$ . The system $𝐴^{𝖳} 𝐴 𝐱 = 𝐴^{𝖳} 𝐛$ is the normal equations, which always have a solution by Theorem 6.5.5, and $𝐴^{𝖳} 𝐴$ is invertible when the columns are independent by Proposition 6.5.9(c). Both proofs used $𝐯^{*} 𝐯 = {‖ 𝐯 ‖}^{2} > 0$ for $𝐯 \neq 𝟎$ , which fails over $𝔽_{2}$ for $𝐯 = (1, 1)$ (Remark 6.5.10).

Exercise 6.5.45.hard Give a second proof that the normal equations

𝐴^{*} 𝐴 𝐱 = 𝐴^{*} 𝐛

always have a solution, by showing that

im (𝐴^{*} 𝐴) = im 𝐴^{*}

Solution (by orthogonal complements).

Uses. Lemma 6.5.4 (The orthogonal complement of a column space), Proposition 6.5.9 ( $rank (𝐴^{*} 𝐴) =$ $rank 𝐴$ ), Proposition 6.3.27 (Properties of the conjugate transpose), Theorem 6.4.26 (The double complement)

Hint 1. Apply Lemma 6.5.4 to

𝑀 = 𝐴^{*} 𝐴

and to

𝑀 = 𝐴^{*}

. What are

{(𝐴^{*} 𝐴)}^{*}

and

{(𝐴^{*})}^{*}

Hint 2. Both complements equal

ker 𝐴

, by Proposition 6.5.9(a). Now take complements again with Theorem 6.4.26.

Sketch.

{(im 𝐴^{*} 𝐴)}^{⟂} =

ker {(𝐴^{*} 𝐴)}^{*} =

ker (𝐴^{*} 𝐴) =

ker 𝐴

and

{(im 𝐴^{*})}^{⟂} =

ker 𝐴^{* *} =

ker 𝐴

. Taking complements,

im (𝐴^{*} 𝐴) =

{(ker 𝐴)}^{⟂} =

im 𝐴^{*}

by Theorem 6.4.26. Then

𝐴^{*} 𝐛 \in

im 𝐴^{*} =

im (𝐴^{*} 𝐴)

By Proposition 6.3.27, ${(𝐴^{*} 𝐴)}^{*} = 𝐴^{*} 𝐴$ and ${(𝐴^{*})}^{*} = 𝐴$ . By Lemma 6.5.4, applied to $𝐴^{*} 𝐴$ and to $𝐴^{*}$ , and by Proposition 6.5.9(a),

\begin{aligned} {(im (𝐴^{*} 𝐴))}^{⟂} & = ker (𝐴^{*} 𝐴) = ker 𝐴, \\ {(im 𝐴^{*})}^{⟂} & = ker 𝐴 . \end{aligned}

Subspaces of $𝔽^{𝑛}$ are finite-dimensional, so Theorem 6.4.26 gives

\begin{aligned} im (𝐴^{*} 𝐴) & = {({(im (𝐴^{*} 𝐴))}^{⟂})}^{⟂} = {(ker 𝐴)}^{⟂} \\ = {({(im 𝐴^{*})}^{⟂})}^{⟂} = im 𝐴^{*} . \end{aligned}

Hence $𝐴^{*} 𝐛 \in$ $im 𝐴^{*} =$ $im (𝐴^{*} 𝐴)$ , that is, $𝐴^{*} 𝐴 𝐱 = 𝐴^{*} 𝐛$ for some $𝐱$ .

Solution (by counting dimensions).

Uses. Proposition 6.5.9 ( $rank (𝐴^{*} 𝐴) =$ $rank 𝐴$ ), Theorem 4.2.7 (The image of $𝑇_{𝐴}$ ), Theorem 4.3.8 (Row rank equals column rank), Proposition 3.5.2 (First properties of rank), Proposition 4.1.21 (Dimensions of subspaces)

Techniques. Dimension counting (Technique 4.2.24)

Hint 1. One containment is clear:

𝐴^{*} 𝐴 𝐱 = 𝐴^{*} (𝐴 𝐱)

. Compare dimensions.

Hint 2.

dim im (𝐴^{*} 𝐴) =

rank 𝐴

by Proposition 6.5.9(b). For

dim im 𝐴^{*} = rank 𝐴^{*}

, write

𝐴^{*} = 𝐴^{𝖳}

: transposing does not change the rank, and neither does conjugating the entries.

Sketch.

im (𝐴^{*} 𝐴) \subseteq im 𝐴^{*}

. Both have dimension

rank 𝐴

: the first by Proposition 6.5.9(b), the second because

rank 𝐴^{*} =

rank 𝐴^{𝖳} =

rank 𝐴 =

rank 𝐴

. Equal dimensions and containment give equality.

Since

𝐴^{*} 𝐴 𝐱 = 𝐴^{*} (𝐴 𝐱)

im (𝐴^{*} 𝐴) \subseteq im 𝐴^{*}

. By Theorem 4.2.7 and Proposition 6.5.9(b),

dim im (𝐴^{*} 𝐴) =

rank (𝐴^{*} 𝐴) =

rank 𝐴

. For

𝐴^{*}

, write

𝐴^{*} = 𝐴^{𝖳}

. By Theorem 4.3.8,

rank 𝐴^{*} = rank 𝐴

. Conjugating the coefficients of a relation shows that

𝐚_{𝑗} \in

span (𝐚_{1}, \dots, 𝐚_{𝑗 - 1})

if and only if

𝐚_{𝑗} \in

span (𝐚_{1}, \dots, 𝐚_{𝑗 - 1})

, so by Proposition 3.5.2(d),

rank 𝐴 = rank 𝐴

. Hence

dim im 𝐴^{*} =

rank 𝐴 =

dim im (𝐴^{*} 𝐴)

, and Proposition 4.1.21 gives

im (𝐴^{*} 𝐴) = im 𝐴^{*}

. As before,

𝐴^{*} 𝐛 \in im (𝐴^{*} 𝐴)

Exercise 6.5.46.hard Let $𝐴 \in 𝔽^{𝑚 \times 𝑛}$ have linearly independent rows, and let $𝐛 \in 𝔽^{𝑚}$ .

(a)Show that $𝐴 𝐴^{*}$ is invertible.
(b)Show that $𝐱_{0} =$ $𝐴^{*} {(𝐴 𝐴^{*})}^{- 1} 𝐛$ solves $𝐴 𝐱 = 𝐛$ and lies in ${(ker 𝐴)}^{⟂}$ .
(c)Show that $𝐱_{0}$ is the unique solution of $𝐴 𝐱 = 𝐛$ of smallest norm.
(d)Find the solution of smallest norm of $𝑥_{1} + 𝑥_{2} + 𝑥_{3} = 3$ , $𝑥_{1} - 𝑥_{3} = 1$ .

Solution.

Uses. Proposition 6.5.9 ( $rank (𝐴^{*} 𝐴) =$ $rank 𝐴$ ), Proposition 6.3.27 (Properties of the conjugate transpose), Proposition 3.1.19 (Solution sets are translates of the kernel), Theorem 6.3.3 (Pythagorean theorem)

Hint 1. The columns of

𝐴^{*}

are the conjugates of the rows of

𝐴

. Apply Proposition 6.5.9(c) to

𝐴^{*}

Hint 2. For

𝐳 \in ker 𝐴

⟨ 𝐴^{*} 𝐲, 𝐳 ⟩ =

⟨ 𝐲, 𝐴 𝐳 ⟩

by Proposition 6.3.27(d).

Hint 3. Every solution is

𝐱_{0} + 𝐳

with

𝐳 \in ker 𝐴

. Use Pythagoras.

Sketch. (a) The columns of

𝐴^{*}

are independent, so

{(𝐴^{*})}^{*} 𝐴^{*} = 𝐴 𝐴^{*}

is invertible. (b)

𝐴 𝐱_{0} =

𝐴 𝐴^{*} {(𝐴 𝐴^{*})}^{- 1} 𝐛 =

𝐛

, and

𝐱_{0} = 𝐴^{*} 𝐲

is orthogonal to

ker 𝐴

since

⟨ 𝐴^{*} 𝐲, 𝐳 ⟩ =

⟨ 𝐲, 𝐴 𝐳 ⟩ =

0

. (c) Solutions are

𝐱_{0} + 𝐳

𝐳 \in ker 𝐴

, with

{‖ 𝐱_{0} + 𝐳 ‖}^{2} =

{‖ 𝐱_{0} ‖}^{2} +

{‖ 𝐳 ‖}^{2}

. (d)

𝐴 𝐴^{𝖳} = diag (3, 2)

, so

𝐱_{0} =

𝐴^{𝖳} (1, 1 / 2) =

(3 / 2, 1, 1 / 2)

(a) Row $𝑖$ of $𝐴$ , read as a vector, has conjugate equal to column $𝑖$ of $𝐴^{*}$ (Definition 6.3.26). A relation $\sum_{𝑖} 𝑐_{𝑖} 𝐫_{𝑖} = 𝟎$ among the conjugated rows gives, after conjugating, the relation $\sum_{𝑖} 𝑐_{𝑖} 𝐫_{𝑖} = 𝟎$ among the rows, so the columns of $𝐴^{*}$ are independent. By Proposition 6.5.9(c) applied to $𝐴^{*} \in 𝔽^{𝑛 \times 𝑚}$ , the matrix ${(𝐴^{*})}^{*} 𝐴^{*} = 𝐴 𝐴^{*}$ is invertible.

(b) $𝐴 𝐱_{0} =$ $(𝐴 𝐴^{*}) {(𝐴 𝐴^{*})}^{- 1} 𝐛 =$ $𝐛$ . Let $𝐲 = {(𝐴 𝐴^{*})}^{- 1} 𝐛$ , so $𝐱_{0} = 𝐴^{*} 𝐲$ . For $𝐳 \in ker 𝐴$ , Proposition 6.3.27(d) and conjugate symmetry give $⟨ 𝐱_{0}, 𝐳 ⟩ =$ $⟨ 𝐴^{*} 𝐲, 𝐳 ⟩ =$ $⟨ 𝐳, 𝐴^{*} 𝐲 ⟩ =$ $⟨ 𝐴 𝐳, 𝐲 ⟩ =$ $0$ . So $𝐱_{0} \in {(ker 𝐴)}^{⟂}$ .

(c) By Proposition 3.1.19, the solutions are the vectors $𝐱_{0} + 𝐳$ with $𝐳 \in ker 𝐴$ . Since $𝐱_{0} ⟂ 𝐳$ , Theorem 6.3.3 gives ${‖ 𝐱_{0} + 𝐳 ‖}^{2} =$ ${‖ 𝐱_{0} ‖}^{2} +$ ${‖ 𝐳 ‖}^{2} \geq$ ${‖ 𝐱_{0} ‖}^{2}$ , with equality if and only if $𝐳 = 𝟎$ .

(d) Here $𝐴 = (\begin{matrix} 1 & 1 & 1 \\ 1 & 0 & - 1 \end{matrix})$ , whose rows are independent, and $𝐴 𝐴^{𝖳} = (\begin{matrix} 3 & 0 \\ 0 & 2 \end{matrix})$ . So ${(𝐴 𝐴^{𝖳})}^{- 1} (3, 1) =$ $(1, 1 / 2)$ , and

𝐱_{0} = 𝐴^{𝖳} (\begin{matrix} 1 \\ 1 / 2 \end{matrix}) = (\begin{matrix} 3 / 2 \\ 1 \\ 1 / 2 \end{matrix}) .

Check: $3 / 2 + 1 + 1 / 2 = 3$ and $3 / 2 - 1 / 2 = 1$ , and $𝐱_{0}$ is orthogonal to $(1, - 2, 1)$ , which spans $ker 𝐴$ . In the language of Section 6.5.7, $𝐱_{0} = 𝐴^{+} 𝐛$ , and $𝐴^{+} = 𝐴^{*} {(𝐴 𝐴^{*})}^{- 1}$ for $𝐴$ with independent rows.

Exercise 6.5.47.hard Let $(𝑥_{1}, 𝑦_{1}),$ $\dots,$ $(𝑥_{𝑚}, 𝑦_{𝑚})$ be data with the $𝑥_{𝑖}$ not all equal. For $𝑖 < 𝑗$ with $𝑥_{𝑖} \neq 𝑥_{𝑗}$ , let $𝑠_{𝑖 𝑗} =$ $(𝑦_{𝑗} - 𝑦_{𝑖}) / (𝑥_{𝑗} - 𝑥_{𝑖})$ be the slope of the line through the $𝑖$ th and $𝑗$ th points. Show that the slope of the least-squares line is a weighted average of these slopes:

𝑐_{1} = \frac{\sum_{𝑖 < 𝑗} {(𝑥_{𝑗} - 𝑥_{𝑖})}^{2} 𝑠_{𝑖 𝑗}}{\sum_{𝑖 < 𝑗} {(𝑥_{𝑗} - 𝑥_{𝑖})}^{2}},

where pairs with $𝑥_{𝑖} = 𝑥_{𝑗}$ are omitted (they would have weight $0$ ). Deduce that $𝑐_{1}$ lies between the smallest and the largest of the $𝑠_{𝑖 𝑗}$ .

Solution.

Uses. Proposition 6.5.17 (The least-squares line)

Hint 1. Show that

\sum_{𝑖 < 𝑗} (𝑢_{𝑗} - 𝑢_{𝑖}) (𝑣_{𝑗} - 𝑣_{𝑖}) =

𝑚 \sum_{𝑘} (𝑢_{𝑘} - 𝑚_{𝑢}) (𝑣_{𝑘} - 𝑚_{𝑣})

for any

𝐮, 𝐯 \in ℝ^{𝑚}

. Sum over all ordered pairs

(𝑖, 𝑗)

first.

Hint 2. Apply this with

(𝐮, 𝐯) = (𝐱, 𝐲)

and

(𝐱, 𝐱)

, and note that

(𝑥_{𝑗} - 𝑥_{𝑖}) (𝑦_{𝑗} - 𝑦_{𝑖}) =

{(𝑥_{𝑗} - 𝑥_{𝑖})}^{2} 𝑠_{𝑖 𝑗}

Sketch. Summing over all ordered pairs,

\sum_{𝑖, 𝑗} (𝑢_{𝑗} - 𝑢_{𝑖}) (𝑣_{𝑗} - 𝑣_{𝑖}) =

2 𝑚 \sum_{𝑘} 𝑢_{𝑘} 𝑣_{𝑘} -

2 (\sum_{𝑘} 𝑢_{𝑘}) (\sum_{𝑘} 𝑣_{𝑘}) =

2 𝑚 \sum_{𝑘} (𝑢_{𝑘} - 𝑚_{𝑢}) (𝑣_{𝑘} - 𝑚_{𝑣})

, and the sum over

𝑖 < 𝑗

is half of it. So the numerator and denominator in the claim are

𝑚 \tilde{𝐱} \cdot \tilde{𝐲}

and

𝑚 {‖ \tilde{𝐱} ‖}^{2}

, whose ratio is

𝑐_{1}

. A weighted average with positive weights lies between the smallest and largest values.

Let $𝐮, 𝐯 \in ℝ^{𝑚}$ with means $𝑚_{𝑢}, 𝑚_{𝑣}$ . Summing over all ordered pairs $(𝑖, 𝑗)$ , including $𝑖 = 𝑗$ , whose terms are $0$ ,

\begin{aligned} \sum_{𝑖, 𝑗} (𝑢_{𝑗} - 𝑢_{𝑖}) (𝑣_{𝑗} - 𝑣_{𝑖}) \\ = \sum_{𝑖, 𝑗} (𝑢_{𝑗} 𝑣_{𝑗} + 𝑢_{𝑖} 𝑣_{𝑖} - 𝑢_{𝑗} 𝑣_{𝑖} - 𝑢_{𝑖} 𝑣_{𝑗}) \\ = 2 𝑚 \sum_{𝑘} 𝑢_{𝑘} 𝑣_{𝑘} - 2 (\sum_{𝑘} 𝑢_{𝑘}) (\sum_{𝑘} 𝑣_{𝑘}) . \end{aligned}

Since $\sum_{𝑘} 𝑢_{𝑘} = 𝑚 𝑚_{𝑢}$ and $\sum_{𝑘} 𝑣_{𝑘} = 𝑚 𝑚_{𝑣}$ , the right side is $2 𝑚 (\sum_{𝑘} 𝑢_{𝑘} 𝑣_{𝑘} - 𝑚 𝑚_{𝑢} 𝑚_{𝑣}) =$ $2 𝑚 \sum_{𝑘} (𝑢_{𝑘} - 𝑚_{𝑢}) (𝑣_{𝑘} - 𝑚_{𝑣})$ , by the identity in the proof of Proposition 6.5.17. The terms for $(𝑖, 𝑗)$ and $(𝑗, 𝑖)$ are equal, so

\sum_{𝑖 < 𝑗} (𝑢_{𝑗} - 𝑢_{𝑖}) (𝑣_{𝑗} - 𝑣_{𝑖}) = 𝑚 \sum_{𝑘} (𝑢_{𝑘} - 𝑚_{𝑢}) (𝑣_{𝑘} - 𝑚_{𝑣}) .

With $(𝐮, 𝐯) = (𝐱, 𝐲)$ and $(𝐱, 𝐱)$ , this gives $\sum_{𝑖 < 𝑗} (𝑥_{𝑗} - 𝑥_{𝑖}) (𝑦_{𝑗} - 𝑦_{𝑖}) =$ $𝑚 \tilde{𝐱} \cdot$ $\tilde{𝐲}$ and $\sum_{𝑖 < 𝑗} {(𝑥_{𝑗} - 𝑥_{𝑖})}^{2} =$ $𝑚 {‖ \tilde{𝐱} ‖}^{2} >$ $0$ . In the first sum, a pair with $𝑥_{𝑖} = 𝑥_{𝑗}$ contributes $0$ , and a pair with $𝑥_{𝑖} \neq 𝑥_{𝑗}$ contributes ${(𝑥_{𝑗} - 𝑥_{𝑖})}^{2} 𝑠_{𝑖 𝑗}$ . Dividing, and using Proposition 6.5.17,

\frac{\sum_{𝑖 < 𝑗} {(𝑥_{𝑗} - 𝑥_{𝑖})}^{2} 𝑠_{𝑖 𝑗}}{\sum_{𝑖 < 𝑗} {(𝑥_{𝑗} - 𝑥_{𝑖})}^{2}} = \frac{\tilde{𝐱} \cdot \tilde{𝐲}}{{‖ \tilde{𝐱} ‖}^{2}} = 𝑐_{1} .

The weights $𝑤_{𝑖 𝑗} =$ ${(𝑥_{𝑗} - 𝑥_{𝑖})}^{2}$ of the remaining pairs are positive. If $𝑠_{min}$ and $𝑠_{max}$ are the smallest and largest $𝑠_{𝑖 𝑗}$ , then $𝑠_{min} \sum 𝑤_{𝑖 𝑗} \leq$ $\sum 𝑤_{𝑖 𝑗} 𝑠_{𝑖 𝑗} \leq$ $𝑠_{max} \sum 𝑤_{𝑖 𝑗}$ , so $𝑠_{min} \leq 𝑐_{1} \leq 𝑠_{max}$ . Pairs of points far apart in $𝑥$ get the most weight, which matches the intuition that they determine a slope most reliably.

Exercise 6.5.48.standardBeyond 21-242

(a)Let $𝑤_{1}, \dots, 𝑤_{𝑚} > 0$ , let $𝑊 =$ $diag (\sqrt{𝑤_{1}}, \dots, \sqrt{𝑤_{𝑚}})$ , and let $𝐷 = 𝑊^{2}$ . Show that $\sum_{𝑖} 𝑤_{𝑖} {| 𝑏_{𝑖} - {(𝐴 𝐱)}_{𝑖} |}^{2} =$ ${‖ 𝑊 𝐛 - 𝑊 𝐴 𝐱 ‖}^{2}$ , and deduce from Theorem 6.5.5 that the minimizers of this sum are the solutions of $𝐴^{*} 𝐷 𝐴 𝐱 = 𝐴^{*} 𝐷 𝐛$ .
(b)Four measurements give $(0, 1),$ $(1, 2),$ $(2, 3),$ $(3, 8)$ , but the last one was made with an instrument whose errors have twice the standard deviation of the others, so it gets weight $1 / 4$ . Find the ordinary and the weighted least-squares lines.

Solution.

Uses. Theorem 6.5.5 (The normal equations), Proposition 6.3.27 (Properties of the conjugate transpose), Aside (Weighted least squares) (Weighted least squares)

Hint 1.

{(𝑊 𝐯)}_{𝑖} = \sqrt{𝑤_{𝑖}} 𝑣_{𝑖}

. So the weighted sum is an ordinary least-squares problem for the matrix

𝑊 𝐴

and the vector

𝑊 𝐛

Hint 2. For (b),

𝐴^{𝖳} 𝐷 𝐴 =

(\begin{matrix} 13 / 4 & 15 / 4 \\ 15 / 4 & 29 / 4 \end{matrix})

and

𝐴^{𝖳} 𝐷 𝐲 = (8, 14)

Sketch. (a)

{‖ 𝑊 (𝐛 - 𝐴 𝐱) ‖}^{2} =

\sum_{𝑖} 𝑤_{𝑖} {| 𝑏_{𝑖} - {(𝐴 𝐱)}_{𝑖} |}^{2}

, so the minimizers are the least-squares solutions of

(𝑊 𝐴) 𝐱 = 𝑊 𝐛

, whose normal equations are

𝐴^{*} 𝑊^{*} 𝑊 𝐴 𝐱 =

𝐴^{*} 𝑊^{*} 𝑊 𝐛

, and

𝑊^{*} 𝑊 = 𝐷

. (b) Ordinary:

𝑦 = 1 / 5 + (11 / 5) 𝑥

. Weighted:

𝑦 =

11 / 19 +

(31 / 19) 𝑥 \approx

0.58 +

1.63 𝑥

(a) The $𝑖$ th entry of $𝑊 (𝐛 - 𝐴 𝐱)$ is $\sqrt{𝑤_{𝑖}} (𝑏_{𝑖} - {(𝐴 𝐱)}_{𝑖})$ , so ${‖ 𝑊 𝐛 - 𝑊 𝐴 𝐱 ‖}^{2} =$ $\sum_{𝑖} 𝑤_{𝑖} {| 𝑏_{𝑖} - {(𝐴 𝐱)}_{𝑖} |}^{2}$ . Hence the minimizers are the least-squares solutions of $(𝑊 𝐴) 𝐱 = 𝑊 𝐛$ , which by Theorem 6.5.5 are the solutions of ${(𝑊 𝐴)}^{*} (𝑊 𝐴) 𝐱 =$ ${(𝑊 𝐴)}^{*} 𝑊 𝐛$ . Since $𝑊$ is real and diagonal, $𝑊^{*} = 𝑊$ and $𝑊^{*} 𝑊 = 𝑊^{2} = 𝐷$ , and by Proposition 6.3.27(b) the equations read $𝐴^{*} 𝐷 𝐴 𝐱 = 𝐴^{*} 𝐷 𝐛$ . This is a second derivation of the weighted normal equations of Aside (Weighted least squares).

(b) Ordinary least squares: $𝐴^{𝖳} 𝐴 = (\begin{matrix} 4 & 6 \\ 6 & 14 \end{matrix})$ and $𝐴^{𝖳} 𝐲 =$ $(14, 0 + 2 + 6 + 24) =$ $(14, 32)$ . The determinant is $20$ , and $𝑐_{0} =$ $(14 \cdot 14 - 6 \cdot 32) / 20 =$ $1 / 5$ , $𝑐_{1} =$ $(4 \cdot 32 - 6 \cdot 14) / 20 =$ $11 / 5$ . So the line is $𝑦 = 0.2 + 2.2 𝑥$ .

Weighted, with $𝐷 =$ $diag (1, 1, 1, 1 / 4)$ :

\begin{aligned} 𝐴^{𝖳} 𝐷 𝐴 & = (\begin{matrix} 3 + 1 / 4 & 3 + 3 / 4 \\ 3 + 3 / 4 & 5 + 9 / 4 \end{matrix}) = \frac{1}{4} (\begin{matrix} 13 & 15 \\ 15 & 29 \end{matrix}), \\ 𝐴^{𝖳} 𝐷 𝐲 & = (\begin{matrix} 6 + 2 \\ 8 + 6 \end{matrix}) = (\begin{matrix} 8 \\ 14 \end{matrix}) . \end{aligned}

Multiplying by $4$ , the system is $13 𝑐_{0} + 15 𝑐_{1} = 32$ , $15 𝑐_{0} + 29 𝑐_{1} = 56$ , with determinant $377 - 225 = 152$ . So $𝑐_{0} =$ $(32 \cdot 29 - 15 \cdot 56) / 152 =$ $88 / 152 =$ $11 / 19$ and $𝑐_{1} =$ $(13 \cdot 56 - 15 \cdot 32) / 152 =$ $248 / 152 =$ $31 / 19$ . The weighted line is $𝑦 \approx 0.58 + 1.63 𝑥$ . The first three points lie on $𝑦 = 1 + 𝑥$ , and giving the unreliable fourth point less weight pulls the slope from $2.2$ toward $1$ .

Exercise 6.5.49.standardBeyond 21-242 Let $𝐴 \in 𝔽^{𝑚 \times 𝑛}$ with pseudoinverse $𝐴^{+}$ (Definition 6.5.28).

(a)Show that $𝐴^{+} 𝐴 = {Pr}_{{(ker 𝐴)}^{⟂}}$ .
(b)Deduce the Penrose equations $𝐴 𝐴^{+} 𝐴 = 𝐴$ , $𝐴^{+} 𝐴 𝐴^{+} = 𝐴^{+}$ , ${(𝐴 𝐴^{+})}^{*} = 𝐴 𝐴^{+}$ , and ${(𝐴^{+} 𝐴)}^{*} = 𝐴^{+} 𝐴$ .
(c)Find $𝐴^{+}$ for $𝐴 = (\begin{matrix} 1 & 1 \\ 1 & 1 \end{matrix})$ and check the four equations.

Solution.

Uses. Proposition 6.5.27 (The least-squares solution of minimal norm), Proposition 6.4.29 (The orthogonal projection as a linear map), Theorem 6.4.31 (The matrix of an orthogonal projection), Proposition 6.5.2 (Least squares is projection)

Hint 1.

𝐴^{+} (𝐴 𝐱)

is the least-squares solution of

𝐴 𝐳 = 𝐴 𝐱

of smallest norm. This system is consistent; what are its solutions?

Hint 2. For (b), use

𝐴 𝐴^{+} = {Pr}_{im 𝐴}

, (a), and the fact that

𝐴^{+} 𝐛 \in {(ker 𝐴)}^{⟂}

. Matrices of orthogonal projections are Hermitian.

Sketch. (a) The solutions of

𝐴 𝐳 = 𝐴 𝐱

are

𝐱 + ker 𝐴

, so

𝐴^{+} 𝐴 𝐱 =

𝐱 -

{Pr}_{ker 𝐴} (𝐱) =

{Pr}_{{(ker 𝐴)}^{⟂}} (𝐱)

by Proposition 6.5.27(a) and Proposition 6.4.29(d). (b)

𝐴 𝐴^{+} 𝐴 =

{Pr}_{im 𝐴} 𝐴 =

𝐴

;

𝐴^{+} 𝐴 𝐴^{+} =

{Pr}_{{(ker 𝐴)}^{⟂}} 𝐴^{+} =

𝐴^{+}

; orthogonal projection matrices are Hermitian. (c)

𝐴^{+} = (1 / 4) (\begin{matrix} 1 & 1 \\ 1 & 1 \end{matrix})

, with

𝐴 𝐴^{+} =

𝐴^{+} 𝐴 =

(1 / 2) (\begin{matrix} 1 & 1 \\ 1 & 1 \end{matrix})

(a) Let $𝐱 \in 𝔽^{𝑛}$ . Then $𝐴^{+} (𝐴 𝐱)$ is the least-squares solution of smallest norm of $𝐴 𝐳 = 𝐴 𝐱$ . This system is consistent, so its least-squares solutions are its solutions, $𝐱 + ker 𝐴$ (Proposition 6.5.2(b)). By Proposition 6.5.27(a) with $\hat{𝐱} = 𝐱$ , $𝐴^{+} 𝐴 𝐱 =$ $𝐱 -$ ${Pr}_{ker 𝐴} (𝐱)$ , and since $𝔽^{𝑛}$ is finite-dimensional this is ${Pr}_{{(ker 𝐴)}^{⟂}} (𝐱)$ by Proposition 6.4.29(d).

(b) By Proposition 6.5.2(a), $𝐴 𝐴^{+} = {Pr}_{im 𝐴}$ , which fixes every column of $𝐴$ ; so $𝐴 𝐴^{+} 𝐴 = 𝐴$ . By Proposition 6.5.27(a), every $𝐴^{+} 𝐛$ lies in ${(ker 𝐴)}^{⟂}$ , which ${Pr}_{{(ker 𝐴)}^{⟂}}$ fixes; with (a), $𝐴^{+} 𝐴 𝐴^{+} = 𝐴^{+}$ . Finally $𝐴 𝐴^{+}$ and $𝐴^{+} 𝐴$ are matrices of orthogonal projections, which are Hermitian by Theorem 6.4.31.

(c) Here $im 𝐴 = span ((1, 1))$ , $ker 𝐴 =$ $span ((1, - 1))$ , and ${(ker 𝐴)}^{⟂} =$ $span ((1, 1))$ . For $𝐛 \in 𝔽^{2}$ , ${Pr}_{im 𝐴} (𝐛) =$ $((𝑏_{1} + 𝑏_{2}) / 2) (1, 1)$ , so the least-squares solutions satisfy $𝑥_{1} +$ $𝑥_{2} =$ $(𝑏_{1} + 𝑏_{2}) / 2$ , and the one in ${(ker 𝐴)}^{⟂}$ is $𝑠 (1, 1)$ with $2 𝑠 = (𝑏_{1} + 𝑏_{2}) / 2$ . So $𝐴^{+} 𝐛 =$ $((𝑏_{1} + 𝑏_{2}) / 4) (1, 1)$ , that is, $𝐴^{+} = (1 / 4) (\begin{matrix} 1 & 1 \\ 1 & 1 \end{matrix})$ . Then $𝐴 𝐴^{+} =$ $𝐴^{+} 𝐴 =$ $(1 / 2) (\begin{matrix} 1 & 1 \\ 1 & 1 \end{matrix})$ , which is Hermitian, $𝐴 𝐴^{+} 𝐴 =$ $(1 / 2) (\begin{matrix} 2 & 2 \\ 2 & 2 \end{matrix}) =$ $𝐴$ , and $𝐴^{+} 𝐴 𝐴^{+} =$ $(1 / 8) (\begin{matrix} 2 & 2 \\ 2 & 2 \end{matrix}) =$ $𝐴^{+}$ .

Exercise 6.5.50.challengeBeyond 21-242 Least squares measures vertical distances to the line. Orthogonal regression measures perpendicular distances instead. Let $𝐩_{1}, \dots, 𝐩_{𝑚} \in ℝ^{2}$ be points, not all equal, with centroid $𝐠$ , and write ${\tilde{𝐩}}_{𝑖} =$ $𝐩_{𝑖} -$ $𝐠 =$ $({\tilde{𝑥}}_{𝑖}, {\tilde{𝑦}}_{𝑖})$ , $𝑆_{𝑥 𝑥} = \sum_{𝑖} {\tilde{𝑥}}_{𝑖}^{2}$ , $𝑆_{𝑦 𝑦} = \sum_{𝑖} {\tilde{𝑦}}_{𝑖}^{2}$ , $𝑆_{𝑥 𝑦} =$ $\sum_{𝑖} {\tilde{𝑥}}_{𝑖} {\tilde{𝑦}}_{𝑖}$ . For a line $ℓ$ and a point $𝐩$ , let $dist (𝐩, ℓ) =$ ${min}_{𝐪 \in ℓ} ‖ 𝐩 -$ $𝐪 ‖$ , and let $𝐷 (ℓ) =$ $\sum_{𝑖} {dist (𝐩_{𝑖}, ℓ)}^{2}$ .

(a)Every line is $ℓ = {𝐩 | ⟨ 𝐩, 𝐧 ⟩ = 𝑐}$ for a unit vector $𝐧$ and some $𝑐 \in ℝ$ . Show that $dist (𝐩, ℓ) =$ $| ⟨ 𝐩, 𝐧 ⟩ -$ $𝑐 |$ , and that for fixed $𝐧$ , $𝐷 (ℓ)$ is smallest when $ℓ$ passes through $𝐠$ .
(b)For a line through $𝐠$ with unit direction $𝐮$ , show that $𝐷 (ℓ) =$ $\sum_{𝑖} {‖ {\tilde{𝐩}}_{𝑖} ‖}^{2} -$ $\sum_{𝑖} {⟨ {\tilde{𝐩}}_{𝑖}, 𝐮 ⟩}^{2}$ .
(c)With $𝐮 = (cos 𝜃, sin 𝜃)$ , show that $\sum_{𝑖} {⟨ {\tilde{𝐩}}_{𝑖}, 𝐮 ⟩}^{2} =$ $(𝑆_{𝑥 𝑥} + 𝑆_{𝑦 𝑦}) / 2 +$ $((𝑆_{𝑥 𝑥} - 𝑆_{𝑦 𝑦}) / 2) cos 2 𝜃 +$ $𝑆_{𝑥 𝑦} sin 2 𝜃$ . Deduce that, if $𝐰 =$ $((𝑆_{𝑥 𝑥} - 𝑆_{𝑦 𝑦}) / 2, 𝑆_{𝑥 𝑦}) \neq$ $𝟎$ , the lines minimizing $𝐷$ are exactly the line through $𝐠$ with $(cos 2 𝜃, sin 2 𝜃) =$ $𝐰 / ‖ 𝐰 ‖$ .
(d)Find the best line in this sense for $(0, 0),$ $(1, 2),$ $(2, 1),$ $(3, 3)$ , and compare it with the two lines of Exercise 6.5.41(c).

Solution.

Uses. Example 6.4.35 (Distance to a hyperplane), Exercise 6.5.20, Theorem 6.3.22 (Parseval’s identity), Theorem 6.2.1 (Cauchy–Schwarz inequality), Exercise 6.5.41

Techniques. Apply Cauchy–Schwarz to a well-chosen inner product (Technique 6.2.21)

Hint 1. For (a),

ℓ = 𝐪 + {𝐧}^{⟂}

for any

𝐪 \in ℓ

; translate Example 6.4.35. Then

\sum_{𝑖} {(⟨ 𝐩_{𝑖}, 𝐧 ⟩ - 𝑐)}^{2}

is a least-squares problem for a constant.

Hint 2. For (b),

𝐮, 𝐧

is an orthonormal basis of

ℝ^{2}

, so

{‖ \tilde{𝐩} ‖}^{2} =

{⟨ \tilde{𝐩}, 𝐮 ⟩}^{2} +

{⟨ \tilde{𝐩}, 𝐧 ⟩}^{2}

Hint 3. For (c), expand

{({\tilde{𝑥}}_{𝑖} cos 𝜃 + {\tilde{𝑦}}_{𝑖} sin 𝜃)}^{2}

with the double-angle formulas, and bound

𝐰 \cdot

(cos 2 𝜃, sin 2 𝜃)

by Cauchy–Schwarz.

Sketch. (a) With

𝐪 \in ℓ

dist (𝐩, ℓ) =

dist (𝐩 - 𝐪, {𝐧}^{⟂}) =

| ⟨ 𝐩 - 𝐪, 𝐧 ⟩ | =

| ⟨ 𝐩, 𝐧 ⟩ -

𝑐 |

; minimizing

\sum_{𝑖} {(⟨ 𝐩_{𝑖}, 𝐧 ⟩ - 𝑐)}^{2}

over

𝑐

gives the mean

𝑐 = ⟨ 𝐠, 𝐧 ⟩

. (b) Parseval in the basis

𝐮, 𝐧

. (c) The double-angle formulas give the expression, and Cauchy–Schwarz bounds

𝐰 \cdot

(cos 2 𝜃, sin 2 𝜃) \leq

‖ 𝐰 ‖

with equality iff

(cos 2 𝜃, sin 2 𝜃) =

𝐰 / ‖ 𝐰 ‖

. (d)

𝐠 = (3 / 2, 3 / 2)

𝐰 = (0, 4)

, so

𝜃 = 𝜋 / 4

and the line is

𝑦 = 𝑥

, whose slope

1

lies between

4 / 5

and

5 / 4

(a) Pick $𝐪 \in ℓ$ , so $⟨ 𝐪, 𝐧 ⟩ = 𝑐$ and $ℓ = 𝐪 + 𝐻$ with $𝐻 = {𝐧}^{⟂}$ . Translating by $- 𝐪$ preserves distances, so by Example 6.4.35, $dist (𝐩, ℓ) =$ $dist (𝐩 - 𝐪, 𝐻) =$ $| ⟨ 𝐩 - 𝐪, 𝐧 ⟩ | =$ $| ⟨ 𝐩, 𝐧 ⟩ -$ $𝑐 |$ . For fixed $𝐧$ , $𝐷 (ℓ) =$ $\sum_{𝑖} {(𝑡_{𝑖} - 𝑐)}^{2}$ with $𝑡_{𝑖} = ⟨ 𝐩_{𝑖}, 𝐧 ⟩$ . This is the least-squares problem $𝑐 𝟏 \approx 𝐭$ , whose solution (Exercise 6.5.20 with all $𝑥_{𝑖} = 1$ ) is the mean $𝑐 =$ $(1 / 𝑚) \sum_{𝑖} 𝑡_{𝑖} =$ $⟨ 𝐠, 𝐧 ⟩$ , and it is unique. So $𝐷$ is smallest when $𝐠 \in ℓ$ .

(b) Let $𝐧$ be a unit vector orthogonal to $𝐮$ , so that $𝐮, 𝐧$ is an orthonormal basis of $ℝ^{2}$ and $ℓ =$ ${𝐩 | ⟨ 𝐩, 𝐧 ⟩ = ⟨ 𝐠, 𝐧 ⟩}$ . By (a), ${dist (𝐩_{𝑖}, ℓ)}^{2} =$ ${⟨ {\tilde{𝐩}}_{𝑖}, 𝐧 ⟩}^{2}$ , and by Parseval (Theorem 6.3.22), ${‖ {\tilde{𝐩}}_{𝑖} ‖}^{2} =$ ${⟨ {\tilde{𝐩}}_{𝑖}, 𝐮 ⟩}^{2} +$ ${⟨ {\tilde{𝐩}}_{𝑖}, 𝐧 ⟩}^{2}$ . Summing over $𝑖$ gives the formula.

(c) We have ${⟨ {\tilde{𝐩}}_{𝑖}, 𝐮 ⟩}^{2} =$ ${\tilde{𝑥}}_{𝑖}^{2} {cos}^{2} 𝜃 +$ $2 {\tilde{𝑥}}_{𝑖} {\tilde{𝑦}}_{𝑖} cos 𝜃 sin 𝜃 +$ ${\tilde{𝑦}}_{𝑖}^{2} {sin}^{2} 𝜃$ . Summing, and using ${cos}^{2} 𝜃 =$ $(1 + cos 2 𝜃) / 2$ , ${sin}^{2} 𝜃 =$ $(1 - cos 2 𝜃) / 2$ , and $2 sin 𝜃 cos 𝜃 =$ $sin 2 𝜃$ ,

\begin{aligned} \sum_{𝑖} {⟨ {\tilde{𝐩}}_{𝑖}, 𝐮 ⟩}^{2} & = \frac{𝑆_{𝑥 𝑥} + 𝑆_{𝑦 𝑦}}{2} + \frac{𝑆_{𝑥 𝑥} - 𝑆_{𝑦 𝑦}}{2} cos 2 𝜃 + 𝑆_{𝑥 𝑦} sin 2 𝜃 \\ = \frac{𝑆_{𝑥 𝑥} + 𝑆_{𝑦 𝑦}}{2} + 𝐰 \cdot (cos 2 𝜃, sin 2 𝜃) . \end{aligned}

By Cauchy–Schwarz (Theorem 6.2.1), $𝐰 \cdot$ $(cos 2 𝜃, sin 2 𝜃) \leq$ $‖ 𝐰 ‖$ , with equality if and only if the unit vector $(cos 2 𝜃, sin 2 𝜃)$ is a positive multiple of $𝐰$ , that is, equals $𝐰 / ‖ 𝐰 ‖$ . By (a), a minimizing line passes through $𝐠$ , and by (b), among those, $𝐷$ is smallest exactly when $\sum_{𝑖} {⟨ {\tilde{𝐩}}_{𝑖}, 𝐮 ⟩}^{2}$ is largest. The condition determines $2 𝜃$ modulo $2 𝜋$ , hence $𝐮$ up to sign, hence the line.

(d) Here $𝐠 = (3 / 2, 3 / 2)$ , $𝑆_{𝑥 𝑥} = 𝑆_{𝑦 𝑦} = 5$ , and $𝑆_{𝑥 𝑦} = 4$ (Exercise 6.5.41(c)), so $𝐰 = (0, 4)$ , $2 𝜃 = 𝜋 / 2$ , and $𝐮 = (1, 1) / \sqrt{2}$ . The best line is $𝑦 = 𝑥$ , with $𝐷 = 10 - (5 + 4) = 1$ . Its slope $1$ lies between the slope $4 / 5$ of the regression of $𝑦$ on $𝑥$ and the slope $5 / 4$ of the regression of $𝑥$ on $𝑦$ , as it treats the two coordinates symmetrically. The direction $𝐮$ maximizing $\sum_{𝑖} {⟨ {\tilde{𝐩}}_{𝑖}, 𝐮 ⟩}^{2}$ is the first principal component of the points (Section 16.2).

More practice

The practice bank has 20 exercises on this section’s topics.