Deriving OLS with Normal Equations

Hello! Welcome to your next lesson.

In our previous session, you successfully derived the Normal Equations by applying multivariate calculus to the least squares cost function. We concluded that the optimal parameters $\hat{\mathbf{\beta }}$ must satisfy a system of $k+1$ linear equations, where the gradient of the cost function is zero.

Today, we will tackle the same problem from a different and arguably more elegant angle: linear algebra. Your learning outcome is to derive the OLS solution using linear algebra, which will culminate in the famous closed-form solution for the Ordinary Least Squares estimator. This approach not only provides a direct method for solving the system but also reveals a powerful geometric interpretation of what linear regression is actually doing.

Let's begin by reformulating the problem in the language of vectors and matrices.

1. The Linear Regression Problem in Matrix Form

Recall the multiple linear regression model for $n$ observations and $k$ features:

$$y_i={\beta }_0+{\beta }_1{x}_{i1}+\cdots +{\beta }_k{x}_{ik}+{ϵ}_i$$

We can express this entire system of $n$ equations using matrix notation. This simplifies the representation and allows us to use the powerful tools of linear algebra.

To learn how to set this up, please read the first section of the following document.

To summarize, we define:

• Response vector $\mathbf{y}$: An $n\times 1$ vector of the observed dependent variable values.
  $\mathbf{y}=\left[\begin{array}{c}{y}_1\\ y_2\\ ⋮\\ y_n\end{array}\right]$
• Design Matrix $\mathbf{X}$: An $n\times (k+1)$ matrix of independent variables. The first column is all ones to account for the intercept term ${\beta }_0$.
  $\mathbf{X}=\left[\begin{array}{cccc}1& x_{11}& \dots & x_{1k}\\ 1& x_{21}& \dots & x_{2k}\\ ⋮& ⋮& \ddots & ⋮\\ 1& x_{n1}& \dots & x_{nk}\end{array}\right]$
• Parameter Vector $\mathbf{\beta }$: A $(k+1)\times 1$ vector of the unknown parameters we want to estimate.
  $\mathbf{\beta }=\left[\begin{array}{c}{\beta }_0\\ {\beta }_1\\ ⋮\\ {\beta }_k\end{array}\right]$

With this notation, the entire system of equations condenses into the compact form:

$$\mathbf{y}=\mathbf{X}\mathbf{\beta }+\mathbf{ϵ}$$

Our goal in OLS is to find the estimated parameters, $\hat{\mathbf{\beta }}$, that minimize the sum of squared residuals. The vector of residuals, $\mathbf{e}$, is given by $\mathbf{e}=\mathbf{y}-\mathbf{X}\hat{\mathbf{\beta }}$. The sum of squared residuals (SSR) is the squared Euclidean norm of this residual vector:

$$\text{SSR}=\sum _{i=1}^n{e}_i^2={\mathbf{e}}^T\mathbf{e}=(\mathbf{y}-\mathbf{X}\hat{\mathbf{\beta }}{)}^T(\mathbf{y}-\mathbf{X}\hat{\mathbf{\beta }})=||\mathbf{y}-\mathbf{X}\hat{\mathbf{\beta }}|{|}^2$$

Finding the $\hat{\mathbf{\beta }}$ that minimizes this quantity is the core of the least squares problem.

2. A Geometric Perspective: Orthogonal Projection

The equation $\mathbf{X}\mathbf{\beta }=\mathbf{y}$ asks if the vector $\mathbf{y}$ can be written as a linear combination of the columns of $\mathbf{X}$. In other words, is $\mathbf{y}$ in the column space of $\mathbf{X}$, denoted $\text{Col}(\mathbf{X})$?

For real-world data with noise, $\mathbf{y}$ will almost never be perfectly in $\text{Col}(\mathbf{X})$. The system is inconsistent and has no exact solution. The least squares problem then becomes: find the vector $\hat{\mathbf{y}}$ within $\text{Col}(\mathbf{X})$ that is closest to $\mathbf{y}$. This $\hat{\mathbf{y}}$ will be our model's prediction, so $\hat{\mathbf{y}}=\mathbf{X}\hat{\mathbf{\beta }}$.

From linear algebra, we know that the closest vector in a subspace to an outside vector is its orthogonal projection.

This next video provides an excellent geometric intuition for this concept.

This geometric intuition is the foundation of our derivation.

The key property we will use is that the residual vector, $\mathbf{e}=\mathbf{y}-\hat{\mathbf{y}}$, is orthogonal to the column space of $\mathbf{X}$.

3. Derivation of the Normal Equations

Now, let's formalize this geometric insight into a rigorous algebraic derivation. If the residual vector $\mathbf{e}=\mathbf{y}-\mathbf{X}\hat{\mathbf{\beta }}$ is orthogonal to $\text{Col}(\mathbf{X})$, then its dot product with every vector in $\text{Col}(\mathbf{X})$ must be zero. This means it must be orthogonal to each of the columns of $\mathbf{X}$.

Let the columns of $\mathbf{X}$ be ${\mathbf{x}}_0,{\mathbf{x}}_1,\dots ,{\mathbf{x}}_k$. Orthogonality means:

$${\mathbf{x}}_j^T(\mathbf{y}-\mathbf{X}\hat{\mathbf{\beta }})=0\text{for }j=0,1,\dots ,k$$

We can stack these $k+1$ equations together. The set of column vectors $\{{\mathbf{x}}_j^T\}$ forms the rows of the matrix ${\mathbf{X}}^T$. Therefore, we can write all $k+1$ orthogonality conditions in a single matrix equation:

$${\mathbf{X}}^T(\mathbf{y}-\mathbf{X}\hat{\mathbf{\beta }})=0$$

Distributing ${\mathbf{X}}^T$, we get:

$${\mathbf{X}}^T\mathbf{y}-{\mathbf{X}}^T\mathbf{X}\hat{\mathbf{\beta }}=0$$

Rearranging this gives us the Normal Equations in matrix form:

$${\mathbf{X}}^T\mathbf{X}\hat{\mathbf{\beta }}={\mathbf{X}}^T\mathbf{y}$$

Notice that this is the same system of equations you derived using calculus in the last lesson, but now expressed in the compact language of linear algebra.

For a formal, text-based derivation of this result, the following reading is highly recommended.

4. Solving for the OLS Estimator

We now have a single matrix equation to solve for $\hat{\mathbf{\beta }}$. The terms ${\mathbf{X}}^T\mathbf{X}$ and ${\mathbf{X}}^T\mathbf{y}$ are known quantities computed from our data.

The matrix ${\mathbf{X}}^T\mathbf{X}$ is a $(k+1)\times (k+1)$ square matrix. If this matrix is invertible, we can solve for $\hat{\mathbf{\beta }}$ by pre-multiplying both sides by its inverse:

$$({\mathbf{X}}^T\mathbf{X}{)}^{-1}({\mathbf{X}}^T\mathbf{X})\hat{\mathbf{\beta }}=({\mathbf{X}}^T\mathbf{X}{)}^{-1}{\mathbf{X}}^T\mathbf{y}$$

Since $(\mathbf{A}{)}^{-1}\mathbf{A}=\mathbf{I}$ (the identity matrix), this simplifies to the closed-form solution for the OLS estimator:

$$\hat{\mathbf{\beta }}=({\mathbf{X}}^T\mathbf{X}{)}^{-1}{\mathbf{X}}^T\mathbf{y}$$

This elegant equation is one of the most fundamental results in classical machine learning and statistics.

When is ${\mathbf{X}}^T\mathbf{X}$ Invertible?

The inverse $({\mathbf{X}}^T\mathbf{X}{)}^{-1}$ exists if and only if the columns of the design matrix $\mathbf{X}$ are linearly independent. In the context of regression, this means that no feature can be written as a perfect linear combination of other features. This condition is known as the absence of perfect multicollinearity. The proof for this is provided in the TU Delft resource under "Proposition 7.4.2".

Test your understanding!

Given $n$ data points and $k$ features, let's verify the dimensions in the OLS solution $\hat{\mathbf{\beta }}=({\mathbf{X}}^T\mathbf{X}{)}^{-1}{\mathbf{X}}^T\mathbf{y}$.

What are the dimensions of:

1. $\mathbf{X}$
2. $\mathbf{y}$
3. ${\mathbf{X}}^T$
4. ${\mathbf{X}}^T\mathbf{X}$
5. $({\mathbf{X}}^T\mathbf{X}{)}^{-1}$
6. ${\mathbf{X}}^T\mathbf{y}$
7. $\hat{\mathbf{\beta }}$

Does the final dimension of $\hat{\mathbf{\beta }}$ make sense?

Show answer

1. $\mathbf{X}$ is $n\times (k+1)$
2. $\mathbf{y}$ is $n\times 1$
3. ${\mathbf{X}}^T$ is $(k+1)\times n$
4. ${\mathbf{X}}^T\mathbf{X}$ is (\underbrace{(k+1) \times n}_{X^T}})(\underbrace{n \times (k+1)}_{X}) \rightarrow (k+1) \times (k+1)
5. $({\mathbf{X}}^T\mathbf{X}{)}^{-1}$ is also $(k+1)\times (k+1)$
6. ${\mathbf{X}}^T\mathbf{y}$ is (\underbrace{(k+1) \times n}_{X^T}})(\underbrace{n \times 1}_{y}) \rightarrow (k+1) \times 1
7. $\hat{\mathbf{\beta }}$ is (\underbrace{(k+1) \times (k+1)}_{(X^T X)^{-1}}})(\underbrace{(k+1) \times 1}_{X^T y}) \rightarrow (k+1) \times 1

Yes, the final dimension of $\hat{\mathbf{\beta }}$ is $(k+1)\times 1$, which matches the definition of our parameter vector containing $k$ feature coefficients and one intercept term.

Conclusion

In this lesson, you have derived the closed-form solution for Ordinary Least Squares using the principles of linear algebra. This approach provides a powerful complement to the calculus-based derivation from the previous lesson, grounding the solution in clear geometric intuition.

Key Takeaways:

• The linear regression problem can be expressed compactly as $\mathbf{y}=\mathbf{X}\mathbf{\beta }+\mathbf{ϵ}$.
• Geometrically, OLS finds the vector $\hat{\mathbf{y}}$ in the column space of $\mathbf{X}$ that is closest to the actual observation vector $\mathbf{y}$.
• This closest vector, $\hat{\mathbf{y}}=\mathbf{X}\hat{\mathbf{\beta }}$, is the orthogonal projection of $\mathbf{y}$ onto $\text{Col}(\mathbf{X})$.
• The orthogonality of the residual vector ($\mathbf{y}-\mathbf{X}\hat{\mathbf{\beta }}$) to $\text{Col}(\mathbf{X})$ directly yields the Normal Equations: ${\mathbf{X}}^T\mathbf{X}\hat{\mathbf{\beta }}={\mathbf{X}}^T\mathbf{y}$.
• Assuming the columns of $\mathbf{X}$ are linearly independent, the Normal Equations have a unique solution: $\hat{\mathbf{\beta }}=({\mathbf{X}}^T\mathbf{X}{)}^{-1}{\mathbf{X}}^T\mathbf{y}$.

Preview of the Next Lesson:
We have now established the OLS solution from both a calculus (optimization) and linear algebra (geometric) perspective. Both of these derivations required no assumptions about the nature of the error term $\mathbf{ϵ}$. In the next lesson, we will introduce a third, probabilistic approach. By assuming the errors follow a Gaussian distribution, we will derive the same OLS solution using the powerful principle of Maximum Likelihood Estimation (MLE). This will provide a statistical justification for why minimizing the sum of squared errors is a reasonable thing to do.