Least Squares Minimization

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:

not Colinear

Least Squares

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.

Note

If $\large A\vec{x}=\vec{b}$ is inconsistent, the solution of the least squares problem gives us the "closest thing" to a solution of $\large A\vec{x}=\vec{b}$. We say "least squares" because the norm we minimize is a square root of the sum of the squares of the differences of the components. So...there's a lot of squares in that thing we minimize!

Least Squares Solutions

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:

Summary

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.

Note

$\large A^T$ is an $\large n\times m$ matrix, so $\large A^TA$ is $\large n\times n$ and $\large A^T\vec{b}$ is $\large n\times 1$.

Back to the Example

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:

LS Line

Least Squares Best Fits

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.

Note

We can find the best fit of any linear form in this way.

Least Squares in Other Settings

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.