Our destination is the well-known basic linear regression solution for the optimal weights ​${\mathbf{w}}^{\ast }\backslash mathbf\{w\}^*$

where $X\in {\mathbb{R}}^{N\times d}X\; \backslash in\; \backslash mathbb\{R\}^\{N\; \backslash times\; d\}$ is our training data features and $\mathbf{y}\in {\mathbb{R}}^N\backslash mathbf\{y\}\; \backslash in\; \backslash mathbb\{R\}^N$ is a vector of the corresponding training data labels.

The route we’ll use to get there is vector geometry. Our checkpoints will be:

1. We’ll think about finding ${\mathbf{w}}^{\ast }\backslash mathbf\{w\}^*$ by solving the familiar system of linear equations $X{\mathbf{w}}^{\ast }=\mathbf{y}X\backslash mathbf\{w\}^*\; =\; \backslash mathbf\{y\}$ but we will see that this often has no solution.
2. We’ll therefore change paths and solve for ${\mathbf{w}}^{\ast }\backslash mathbf\{w\}^*$ in $X{\mathbf{w}}^{\ast }=\widehat{\mathbf{y}}X\backslash mathbf\{w\}^*\; =\; \backslash hat\{\backslash mathbf\{y\}\}$, where $\widehat{\mathbf{y}}\backslash hat\{\backslash mathbf\{y\}\}$ is the best approximation of $\mathbf{y}\backslash mathbf\{y\}$ for which a solution for ${\mathbf{w}}^{\ast }\backslash mathbf\{w\}^*$ exists.
3. This will lead us to vector geometry, which will define $\widehat{\mathbf{y}}\backslash hat\{\backslash mathbf\{y\}\}$ as the orthogonal projection of $\mathbf{y}\backslash mathbf\{y\}$ onto the span of $XX$.
   1. Here, we’ll see what an orthogonal projection is and prove that it will give the best approximation of $\mathbf{y}\text{}\backslash mathbf\{y\}$
   2. We’ll then see how to get the optimal weights ${\mathbf{w}}^{\ast }\backslash mathbf\{w\}^*$ in $X{\mathbf{w}}^{\ast }=\widehat{\mathbf{y}}\text{}X\backslash mathbf\{w\}^*\; =\; \backslash hat\{\backslash mathbf\{y\}\}$

A System of Linear Equations

The goal of regression is to estimate the function $ff$ of a real-world data-generating phenomenon. The estimation is done using sample data drawn from the phenomenon. This phenomenon could be the pricing of houses in Rwanda and the sampled data could be the price, size, number of rooms, location and seller. If the goal is to predict the house price, then we will estimate a function $ff$ that maps any house’s other features to its price.

Let house $ii$’s price be the scalar $y_{i}y\_i$ and its other features like size and number of rooms be represented as a vector . Therefore, $f:{\mathbf{x}}_i\to y_{i}f:\backslash mathbf\{x\}\_i\; \backslash to\; y\_i$.

Linear regression assumes $ff$ is a linear function,

Since $f({\mathbf{x}}_i)=y_{i}f(\backslash mathbf\{x\}\_i)\; =\; y\_i$, let’s make this

Since we have the $y_{i}y\_i$s and $x_{ij}x\_\{ij\}$s, to find the linear function $ff$, we must find a vector that satisfies the system of linear equations

where $NN$ is the number of houses in our sample data.

We can condense this system of linear equations into the matrix form

where

The problem with this is, with real-world data, the system will often have no solution. That is, there is no $\mathbf{w}\backslash mathbf\{w\}$ that satisfies all the equations in the system, or from a linear algebra view, $\mathbf{y}\backslash mathbf\{y\}$ cannot be expressed as a linear combination of the columns of $XX$.

So, since the perfect $\mathbf{w}\backslash mathbf\{w\}$ does not exist, we instead look for ${\mathbf{w}}^{\ast }\backslash mathbf\{w\}^*$ in $X{\mathbf{w}}^{\ast }=\widehat{\mathbf{y}}X\backslash mathbf\{w\}^*\; =\; \backslash hat\{\backslash mathbf\{y\}\}$, where $\widehat{\mathbf{y}}\backslash hat\{\backslash mathbf\{y\}\}$ is (1) the closest thing to $\mathbf{y}\backslash mathbf\{y\}$ or the best approximation of $\mathbf{y}\backslash mathbf\{y\}$ (2) that can be expressed as a linear combination of $XX$ so that a solution for ${\mathbf{w}}^{\ast }\backslash mathbf\{w\}^*$ in $X{\mathbf{w}}^{\ast }=\widehat{\mathbf{y}}X\backslash mathbf\{w\}^*\; =\; \backslash hat\{\backslash mathbf\{y\}\}$ exists.

The Closest Thing to $\mathbf{y}\backslash mathbf\{y\}$ that can be expressed as a Linear Combination of $XX$

We’ve seen that there is often no solution for $\mathbf{w}\backslash mathbf\{w\}$ in the system $X\mathbf{w}=\mathbf{y}X\backslash mathbf\{w\}\; =\; \backslash mathbf\{y\}$. Since we needed $\mathbf{w}\backslash mathbf\{w\}$ to get $ff$, this means there is often no linear function that perfectly maps all training data features ${\mathbf{x}}_i\backslash mathbf\{x\}\_i$ to their respective labels $y_{i}y\_i$.

Since there is often no linear $ff$, we have to settle for an optimal approximation. Remember the reason we can’t find $ff$ is because $\mathbf{y}\backslash mathbf\{y\}$ cannot be expressed as a linear combination of $XX$. So, instead of $\mathbf{y}\backslash mathbf\{y\}$, we use a vector $\widehat{\mathbf{y}}\backslash hat\{\backslash mathbf\{y\}\}$ that is the closest thing to $\mathbf{y}\backslash mathbf\{y\}$ but also a linear combination of $XX$. Our problem therefore changes to solving for ${\mathbf{w}}^{\ast }\backslash mathbf\{w\}^*$ in $X{\mathbf{w}}^{\ast }=\widehat{\mathbf{y}}X\backslash mathbf\{w\}^*\; =\; \backslash hat\{\backslash mathbf\{y\}\}$. With ${\mathbf{w}}^{\ast }\backslash mathbf\{w\}^*$ we will have all we need to get the optimal linear approximation of $ff$.

But this leads to a new question. How do you determine $\widehat{\mathbf{y}}\backslash hat\{\backslash mathbf\{y\}\}$ - the vector that is closest to $\mathbf{y}\backslash mathbf\{y\}$ but also a linear combination of $XX$? We will use vector geometry and, specifically, the concept of orthogonal projection to answer this question.

Orthogonal Projection

We are looking for $\widehat{\mathbf{y}}\backslash hat\{\backslash mathbf\{y\}\}$, the vector that is closest to $\mathbf{y}\backslash mathbf\{y\}$ but is also a linear combination of $XX$.

For now, let’s assume $\widehat{\mathbf{y}}\backslash hat\{\backslash mathbf\{y\}\}$ and $\mathbf{y}\backslash mathbf\{y\}$ are points and $XX$ is a line on a 2D plane.

Using basic geometry and the Pythagorean theorem, we show that the point $\widehat{\mathbf{y}}\backslash hat\{\backslash mathbf\{y\}\}$ on line $XX$ that is closest to point $\mathbf{y}\backslash mathbf\{y\}$ is the foot of the perpendicular dropped from point $\mathbf{y}\backslash mathbf\{y\}$ to line $XX$. Let $d(x,y)d(x,\; y)$ be the distance from point $xx$ to $yy$. For any point $\mathbf{b}\backslash mathbf\{b\}$ on line $XX$

We get $d(\mathbf{y},\mathbf{b})\ge d(\mathbf{y},\widehat{\mathbf{y}})d(\backslash mathbf\{y\},\; \backslash mathbf\{b\})\; \backslash ge\; d(\backslash mathbf\{y\},\; \backslash hat\{\backslash mathbf\{y\}\})$ by taking square roots.

Think about this proof for two minutes.

And then think about how this geometry problem relates to our linear algebra problem for two minutes.

For the geometry problem, we have found that $\widehat{\mathbf{y}}\backslash hat\{\backslash mathbf\{y\}\}$, the closest point to $\mathbf{y}\backslash mathbf\{y\}$ that is on line $XX$ is the foot of the perpendicular dropped from point $\mathbf{y}\backslash mathbf\{y\}$ onto line $XX$. In the linear algebra problem, similarly, $\widehat{\mathbf{y}}\backslash hat\{\backslash mathbf\{y\}\}$, the closest vector to vector $\mathbf{y}\backslash mathbf\{y\}$ that is in the span of $XX$ is the foot of a perpendicular dropped from $\mathbf{y}\backslash mathbf\{y\}$ onto the span of $XX$. The linear algebra term for $\widehat{\mathbf{y}}\backslash hat\{\backslash mathbf\{y\}\}$ is the orthogonal projection of $\mathbf{y}\backslash mathbf\{y\}$ onto the span of $XX$.

Since the Pythagorean theorem generalizes to vector spaces, we can prove that the vector $\widehat{\mathbf{y}}\backslash hat\{\backslash mathbf\{y\}\}$ closest to $\mathbf{y}\backslash mathbf\{y\}$ that can also be expressed as a linear combination of $XX$ (or equivalently, is in the span of $XX$) is the orthogonal projection of $\mathbf{y}\backslash mathbf\{y\}$ onto the span of $XX$ as follows. For any vector $\mathbf{b}\backslash mathbf\{b\}$ in the span of $X\text{}X$

We get $\mathrm{\parallel }\mathbf{y}-\mathbf{b}\mathrm{\parallel }\ge \mathrm{\parallel }\mathbf{y}-\widehat{\mathbf{y}}\mathrm{\parallel }\backslash |\backslash mathbf\{y\}-\backslash mathbf\{b\}\backslash |\; \backslash ge\; \backslash |\backslash mathbf\{y\}-\backslash hat\{\backslash mathbf\{y\}\}\backslash |$ by taking square roots, with equivalence only when $\mathbf{b}=\widehat{\mathbf{y}}\backslash mathbf\{b\}\; =\; \backslash hat\{\backslash mathbf\{y\}\}$.

Think about this proof for two minutes.

It tells us that the distance between a vector $\mathbf{y}\mathrm{\notin }\text{span}(X)\backslash mathbf\{y\}\; \backslash notin\; \backslash text\{span\}(X)$ and any vector $\mathbf{b}\in \text{span}(X)\backslash mathbf\{b\}\; \backslash in\; \backslash text\{span\}(X)$ is always greater than or equal to the distance between $\mathbf{y}\backslash mathbf\{y\}$ and the orthogonal projection of $\mathbf{y}\backslash mathbf\{y\}$ onto the span of $XX$, with equality only when $\mathbf{b}\backslash mathbf\{b\}$ is the orthogonal projection of $\mathbf{y}\backslash mathbf\{y\}$ onto the span of $XX$. Or inversely, and more to the point, the orthogonal projection of $\mathbf{y}\backslash mathbf\{y\}$ onto the span of $XX$ is the vector in the span of $XX$ that is closest to $\mathbf{y}\backslash mathbf\{y\}$

Therefore, $\widehat{\mathbf{y}}\backslash hat\{\backslash mathbf\{y\}\}$ is the orthogonal projection of $\mathbf{y}\backslash mathbf\{y\}$ onto the span of $XX$.

Getting ${\mathbf{w}}^{\ast }\text{}\backslash mathbf\{w\}^*$

Remember we want to find ${\mathbf{w}}^{\ast }\backslash mathbf\{w\}^*$ in $X{\mathbf{w}}^{\ast }=\widehat{\mathbf{y}}X\backslash mathbf\{w\}^*\; =\; \backslash hat\{\backslash mathbf\{y\}\}$. $XX$ is given and we have just found that $\widehat{\mathbf{y}}\backslash hat\{\backslash mathbf\{y\}\}$ is the orthogonal projection of $\mathbf{y}\backslash mathbf\{y\}$ onto the span of $XX$. How do we find ${\mathbf{w}}^{\ast }\backslash mathbf\{w\}^*$?

To find ${\mathbf{w}}^{\ast }\backslash mathbf\{w\}^*$, it is important to first know that the vector $\widehat{\mathbf{y}}-\mathbf{y}\backslash hat\{\backslash mathbf\{y\}\}\; -\; \backslash mathbf\{y\}$ is orthogonal (”perpendicular”) to all the vectors in the span of $XX$ and therefore all the column vectors in $XX$ (which are in the span of $XX$ themselves).

Let ${\mathbf{x}}_1,\cdots ,{\mathbf{x}}_d\backslash mathbf\{x\}\_1,\; \backslash cdots,\; \backslash mathbf\{x\}\_d$ be the column vectors in $XX$. Since, as we have just said, $\widehat{\mathbf{y}}-\mathbf{y}\backslash hat\{\backslash mathbf\{y\}\}\; -\; \backslash mathbf\{y\}$ is orthogonal to all the column vectors in $XX$ and the inner product of orthogonal vectors is $00$, we have the following conditions

Remember $\widehat{\mathbf{y}}=X{\mathbf{w}}^{\ast }\backslash hat\{\backslash mathbf\{y\}\}\; =\; X\backslash mathbf\{w\}^*$ therefore, we can write the conditions as

We write these conditions in matrix form

and from this we get

We know $X^{\mathrm{\top }}XX^\backslash top\; X$ is invertible because it is positive semi-definite (I won’t provide the proof for this here) therefore