Consider the following simple question: are the points $\large (1,2), (2,4), \text{ and } (3,5)$ colinear? How can we tell? If $\large (1,2)$ is on the line $\large y=mx+b$, then the equation $\large b+m(1)=2$ holds.

If $\large y=mx+b$ is a line containing all three points, then we'll be able to solve the three following equations for $\large m$ and $\large b$:

$$\large \begin{split} b+m &= 2\\ b+2m &= 4\\ b+3m &= 5\\ \end{split} $$

Can we solve this system of 3 linear equations? It is overdetermined, so it's likely there is no solution. Let's take a look at the augmented matrix:

$$\large \begin{bmatrix} 1 & 1 & : & 2\\ 1 & 2 & : & 4\\ 1 & 3 & : & 5\\ \end{bmatrix}\sim\begin{bmatrix} 1 & 0 & : & 0\\ 0 & 1 & : & 0\\ 0 & 0 & : & 1\\ \end{bmatrix} $$

There is no solution, so these three points are not colinear. We can verify this with a plot of the three points:

The example above shows one scenario where we end up with an inconsistent system. It's a fairly common predicament. We want a solution, but there isn't one!

Here's what we do. There is no $\large \vec{x}$ such that $\large A\vec{x}=\vec{b}$, but...is there an $\large \vec{x}$ that gets close? Maybe close is good enough. Of all the possible vectors $\large \vec{x}$, is there one that minimizes the distance between $\large A\vec{x}$ and $\large \vec{b}$?

Definition: The $\vec{x}$ that minimizes the distance $\large \lVert A\vec{x}-\vec{b} \rVert$ is called the Least Squares solution to $\large A\vec{x}=\vec{b}$. The problem of minimizing this distance is called a Least Squares Problem.

Our goal is to minimize $\large \lVert A\vec{x}-\vec{b} \rVert$ when $\large A\vec{x}=\vec{b}$ is inconsistent. Since the system is inconsistent, we know $\large \vec{b}$ is not in $\large \text{Col}(A)$.

What we want is the vector in $\large \text{Col}(A)$ that is closest to $\large \vec{b}$. We have a name for this! What we want is the projection of $\large \vec{b}$ onto $\large \text{Col}(A)$. We want to solve this system instead:

$$\large A\vec{x}=\hat{b}=\text{proj}_{\text{Col}(A)}\vec{b}$$

This system is guaranteed to be consistent, because $\large \hat{b}$ is in the column space of $\large A$. Wooo! We have a consistent system! But how do we solve it? There is a slick way to do it without calculating $\large \hat{b}$ or worrying about $\large \text{Col}(A)$. We need the Four Subspace Theorem we learned in our lecture on orthogonality. The video shows this slick approach:

Let's summarize what we derived in the video with a theorem:

Theorem: Let $\large A$ be an $\large m\times n$ matrix, and let $\large \vec{b}$ be $\large m\times 1$. Then the least squares solution of $\large A\vec{x}=\vec{b}$ is found by solving the normal equations:

$$\large A^TA\vec{x}=A^T\vec{b}$$

As long as the columns of $\large A$ are linearly independent, the normal equations are consistent.

In the example to start this lesson, we had an inconsistent system $\large A\vec{x}=\vec{b}$:

$$\large A= \begin{bmatrix} 1 & 1 \\ 1 & 2 \\ 1 & 3 \\ \end{bmatrix}, \vec{b}= \begin{bmatrix} 2 \\ 4 \\ 5 \\ \end{bmatrix} $$

We can now find a least squares solution to this system, which we do in the video:

We see that the least squares solution gives us $\large b=\frac{2}{3}$ and $\large m=\frac{3}{2}$. The plot of the least squares line is here:

In the example we just concluded, the three points are not colinear. We can't find a line that passes through each point. Instead, we found a least squares solution, and that gave us the "best fitting" line to the three points. This is a very common application of least squares.

Suppose we have data $\large (x_1,y_1),(x_2,y_2),\dots,(x_m,y_m)$, and we'd like to find the equation of the parabola that is a best fit to this data. A parabola in general looks like $\large f(x) = a_0+a_1x+a_2x^2$. If we plug our points into this equation, we get a system of equations that is overdetermined and likely to be inconsistent:

$$\large \begin{split} a_0+a_1x_1+a_2x_1^2&=y_1\\ a_0+a_1x_2+a_2x_2^2&=y_2\\ \quad \vdots \quad\quad \vdots \quad &\vdots \\ a_0+a_1x_m+a_2x_m^2&=y_m\\ \end{split} $$

If we write this in matrix notation, we have:

$$\large A=\begin{bmatrix} 1 & x_1 & x_1^2\\ 1 & x_2 & x_2^2\\ \vdots & \vdots & \vdots \\ 1 & x_m & x_m^2\\ \end{bmatrix}, \vec{b}=\begin{bmatrix} y_1\\ y_2\\ \vdots\\ y_m\\ \end{bmatrix} $$

We can now just solve the normal equations $\large A^TA\vec{x}=A^T\vec{b}$ and get $\large a_0, a_1, a_2$, the coefficients for the best fitting parabola to our data.

We've seen examples of using least squares minimization to find curves of best fit. This is a massive application in most STEM fields. Notably, this forms the backbone of statistics and data science. Least squares solutions are at the heart of the field of machine learning.

But we can use least squares in any setting where we have an inconsistent system. In the absence of a solution, we can find the closest thing. It's a powerful idea that relies heavily on the ideas of subspaces (the column and null spaces in particular) and orthogonal projections of vectors. This is why we develop theory in linear algebra...there's a payoff.

I can:

• Set up the normal equations for an inconsistent system.
• Set up and/or solve the normal equations to find a best fitting curve for a given dataset.