Least squares and the normal equations

Skill positionModule 4 of 4 · Topic 1 of 4

4.1 Least squares and the normal equations

—Lab score— / 100Total XP—Streak—

More equations than unknowns

A regression has many observations and few coefficients: $A\mathbf{x}=\mathbf{b}$ with $A$ tall ( $n$ rows, $p$ columns, $n>p$ ) has no exact solution, because $\mathbf{b}$ is almost never in the column space. Least squares picks the $\hat{\mathbf{x}}$ that makes the error as small as possible, $\min_{\mathbf{x}}\|A\mathbf{x}-\mathbf{b}\|^2$ . Geometrically, $A\hat{\mathbf{x}}$ is the projection of $\mathbf{b}$ onto the column space, so the residual $\mathbf{b}-A\hat{\mathbf{x}}$ is orthogonal to every column of $A$ .

A^{T}A\,\hat{\mathbf{x}}=A^{T}\mathbf{b},\qquad \hat{\mathbf{x}}=(A^{T}A)^{-1}A^{T}\mathbf{b},\qquad \hat{\mathbf{b}}=A\hat{\mathbf{x}}

(1)

Orthogonality of the residual, $A^{T}(\mathbf{b}-A\hat{\mathbf{x}})=\mathbf{0}$ , rearranges into the normal equations above. They always have a solution, and it is unique when the columns of $A$ are independent (then $A^{T}A$ is invertible). In regression notation $A=X$ holds the regressors, with a first column of ones for the intercept, $\mathbf{b}=\mathbf{y}$ is the response and $\hat{\boldsymbol\beta}=(X^{T}X)^{-1}X^{T}\mathbf{y}$ are the OLS coefficients. In code you still solve the system rather than invert $X^{T}X$ .

Fitting a line to three pointsFit

y=c_0+c_1t

to the points

(0,1)

(1,2)

(2,2)

. Then

A=\begin{pmatrix}1&0\\1&1\\1&2\end{pmatrix}

and

\mathbf{b}=(1,2,2)

, so

A^{T}A=\begin{pmatrix}3&3\\3&5\end{pmatrix}

and

A^{T}\mathbf{b}=(5,6)

. The normal equations

3c_0+3c_1=5

3c_0+5c_1=6

give

c_1=0.5

and

c_0=7/6\approx1.167

. The fitted values are

1.167,\ 1.667,\ 2.167

and the residuals

-0.167,\ 0.333,\ -0.167

: they sum to zero and are orthogonal to

t

Normal equations: $A^{T}A\hat{\mathbf{x}}=A^{T}\mathbf{b}$ ; solve them, do not invert.
Residual: $\mathbf{b}-A\hat{\mathbf{x}}$ , orthogonal to every column of $A$ ; with an intercept column it sums to zero.
Independent columns are needed for a unique answer; collinear regressors make $A^{T}A$ singular.

Squaring the condition numberForming

A^{T}A

squares the condition number:

\kappa(A^{T}A)=\kappa(A)^2

. If

\kappa(A)=10^{5}

, the normal equations have

\kappa=10^{10}

and lose ten of your sixteen digits. The next topic shows how QR solves the same problem without ever forming

A^{T}A

Lab · what's graded

The normal matrix15 pts
The slope15 pts
The intercept15 pts
The size of the error10 pts
What the residual is orthogonal to15 pts
The steps of a least squares fit15 pts
Why residuals sum to zero15 pts

0/ 7 answered

1Matrix · vector15 ptsNot answered

Fit $y=c_0+c_1t$ to the points $(0,1)$ , $(1,2)$ , $(2,2)$ with $A=\begin{pmatrix}1&0\\1&1\\1&2\end{pmatrix}$ and $\mathbf{b}=(1,2,2)$ . Fill in $A^{T}A$ .

A^T A =

2Numeric answer15 ptsNot answered

Fit $y=c_0+c_1t$ to the points $(0,1)$ , $(1,2)$ , $(2,2)$ with $A=\begin{pmatrix}1&0\\1&1\\1&2\end{pmatrix}$ and $\mathbf{b}=(1,2,2)$ . Solve $A^{T}A\mathbf{c}=A^{T}\mathbf{b}$ , where $A^{T}\mathbf{b}=(5,6)$ . What is the slope $c_1$ ?

c_1 =

accepted: ± 0.001

3Numeric answer15 ptsNot answered

Fit $y=c_0+c_1t$ to the points $(0,1)$ , $(1,2)$ , $(2,2)$ with $A=\begin{pmatrix}1&0\\1&1\\1&2\end{pmatrix}$ and $\mathbf{b}=(1,2,2)$ . What is the intercept $c_0$ ? Give it to three decimals.

c_0 =

accepted: ± 0.001

4Numeric answer10 ptsNot answered

Fit $y=c_0+c_1t$ to the points $(0,1)$ , $(1,2)$ , $(2,2)$ with $A=\begin{pmatrix}1&0\\1&1\\1&2\end{pmatrix}$ and $\mathbf{b}=(1,2,2)$ . The residuals are $(-1/6,\ 1/3,\ -1/6)$ . What is the sum of squared residuals? Give it to three decimals.

SSR =

accepted: ± 0.001

5Choice15 ptsNot answered

The residual $\mathbf{b}-A\hat{\mathbf{x}}$ of a least squares fit is orthogonal to which of these? Select all that apply.

6Order the steps15 ptsNot answered

Put the steps of fitting a regression by the normal equations in order.

Drag to reorder, or focus an item, press Space to lift it, the arrow keys to move it and Space to drop it.

1Form $A^{T}A$ and $A^{T}\mathbf{b}$
2Compute the fitted values $A\hat{\mathbf{x}}$ and the residual
3Build $A$ with a column of ones and the regressors
4Solve $A^{T}A\mathbf{x}=A^{T}\mathbf{b}$ for the coefficients

7Explain in words15 ptsNot answered

In a regression with an intercept the residuals add up to zero. In two sentences, say why, using orthogonality.

Graded on:The intercept is a column of ones among the regressorsThe residual is orthogonal to it, so its dot product with ones, the sum, is zero0 / 400 characters

Math modeKeyboard or LaTeX inputTask 1 of 7 · Ctrl ⏎ to check

Least squares and the normal equations

Skill positionModule 4 of 4 · Topic 1 of 4

4.1 Least squares and the normal equations

—Lab score— / 100Total XP—Streak—

More equations than unknowns

A^{T}A\,\hat{\mathbf{x}}=A^{T}\mathbf{b},\qquad \hat{\mathbf{x}}=(A^{T}A)^{-1}A^{T}\mathbf{b},\qquad \hat{\mathbf{b}}=A\hat{\mathbf{x}}

(1)

Fitting a line to three pointsFit

y=c_0+c_1t

to the points

(0,1)

(1,2)

(2,2)

. Then

A=\begin{pmatrix}1&0\\1&1\\1&2\end{pmatrix}

and

\mathbf{b}=(1,2,2)

, so

A^{T}A=\begin{pmatrix}3&3\\3&5\end{pmatrix}

and

A^{T}\mathbf{b}=(5,6)

. The normal equations

3c_0+3c_1=5

3c_0+5c_1=6

give

c_1=0.5

and

c_0=7/6\approx1.167

. The fitted values are

1.167,\ 1.667,\ 2.167

and the residuals

-0.167,\ 0.333,\ -0.167

: they sum to zero and are orthogonal to

t

Normal equations: $A^{T}A\hat{\mathbf{x}}=A^{T}\mathbf{b}$ ; solve them, do not invert.
Residual: $\mathbf{b}-A\hat{\mathbf{x}}$ , orthogonal to every column of $A$ ; with an intercept column it sums to zero.
Independent columns are needed for a unique answer; collinear regressors make $A^{T}A$ singular.

Squaring the condition numberForming

A^{T}A

squares the condition number:

\kappa(A^{T}A)=\kappa(A)^2

. If

\kappa(A)=10^{5}

, the normal equations have

\kappa=10^{10}

and lose ten of your sixteen digits. The next topic shows how QR solves the same problem without ever forming

A^{T}A

Lab · what's graded

The normal matrix15 pts
The slope15 pts
The intercept15 pts
The size of the error10 pts
What the residual is orthogonal to15 pts
The steps of a least squares fit15 pts
Why residuals sum to zero15 pts

0/ 7 answered

1Matrix · vector15 ptsNot answered

Fit $y=c_0+c_1t$ to the points $(0,1)$ , $(1,2)$ , $(2,2)$ with $A=\begin{pmatrix}1&0\\1&1\\1&2\end{pmatrix}$ and $\mathbf{b}=(1,2,2)$ . Fill in $A^{T}A$ .

A^T A =

2Numeric answer15 ptsNot answered

c_1 =

accepted: ± 0.001

3Numeric answer15 ptsNot answered

Fit $y=c_0+c_1t$ to the points $(0,1)$ , $(1,2)$ , $(2,2)$ with $A=\begin{pmatrix}1&0\\1&1\\1&2\end{pmatrix}$ and $\mathbf{b}=(1,2,2)$ . What is the intercept $c_0$ ? Give it to three decimals.

c_0 =

accepted: ± 0.001

4Numeric answer10 ptsNot answered

SSR =

accepted: ± 0.001

5Choice15 ptsNot answered

The residual $\mathbf{b}-A\hat{\mathbf{x}}$ of a least squares fit is orthogonal to which of these? Select all that apply.

6Order the steps15 ptsNot answered

Put the steps of fitting a regression by the normal equations in order.

Drag to reorder, or focus an item, press Space to lift it, the arrow keys to move it and Space to drop it.

1Form $A^{T}A$ and $A^{T}\mathbf{b}$
2Compute the fitted values $A\hat{\mathbf{x}}$ and the residual
3Build $A$ with a column of ones and the regressors
4Solve $A^{T}A\mathbf{x}=A^{T}\mathbf{b}$ for the coefficients

7Explain in words15 ptsNot answered

In a regression with an intercept the residuals add up to zero. In two sentences, say why, using orthogonality.

Graded on:The intercept is a column of ones among the regressorsThe residual is orthogonal to it, so its dot product with ones, the sum, is zero0 / 400 characters

Math modeKeyboard or LaTeX inputTask 1 of 7 · Ctrl ⏎ to check

Least squares and the normal equations

More equations than unknowns

Lab · what's graded

Log in to run your code.

Least squares and the normal equations

More equations than unknowns

Lab · what's graded

Log in to run your code.