Normal Equations: Closed-Form Least Squares

From Iteration to a Direct Solution

To find the optimal parameters ($\theta$) that minimize the Sum of Squared Errors (SSE), Gradient Descent works by "walking" down the slope of the cost function. This is an iterative approach.

However, for linear regression, the cost function is a simple quadratic-like function (a convex paraboloid). For such functions, we can often find the minimum directly using calculus—by taking the derivative, setting it to zero, and solving. This direct, non-iterative method is called a closed-form solution. The Normal Equation is exactly this: an equation that gives us the optimal parameters in one single calculation.

To understand what a "closed-form" solution is, let's turn to an article that provides a clear definition and introduces the Normal Equation.

As the article states, the Normal Equation is:

$\theta =(X^{T}X{)}^{-1}{X}^{T}y$

This might look intimidating, but it's just a compact way of expressing a solution using linear algebra. Let's break down how we get here.

Two Paths to the Same Equation

There are two powerful ways to understand where this equation comes from: a calculus-based derivation and a geometric one. Your engineering background gives you a great foundation for appreciating both.

1. The Calculus Approach: Finding the Bottom of the Bowl

The cost function for linear regression, $J(\theta )$, is the Sum of Squared Errors. In matrix form, it's written as:

$J(\theta )=(X\theta -y{)}^T(X\theta -y)$

Here:

• $X$ is the design matrix, with a row for each data sample and a column for each feature (plus an extra column of 1s for the intercept).
• $\theta$ is the vector of our model parameters (the intercept and all coefficients).
• $y$ is the vector of true target values.
• $X\theta$ gives the vector of our model's predictions.

To find the minimum of this function, we calculate its derivative (gradient) with respect to $\theta$ and set it to zero. This is analogous to finding the bottom of a bowl where the slope is flat.

The video below provides a fantastic, step-by-step walkthrough of this derivation. It requires some comfort with matrix notation but explains each step clearly.

After all the algebraic steps, we arrive at the Normal Equation:

$X^{T}X\theta =X^{T}y$

And solving for $\theta$ gives us our famous formula.

2. The Geometric Approach: The Power of Projections

This calculus derivation can feel a bit abstract. Fortunately, there's a more intuitive geometric interpretation that resonates well with vector concepts from engineering.

Imagine our target values y as a single vector in a high-dimensional space. The columns of our feature matrix X define a plane (or hyperplane) in that space, known as the column space. Any prediction our linear model can make, $\hat{y}=X\theta$, must lie on this plane.

The goal of least squares is to find the prediction $\hat{y}$ on the plane that is closest to our actual target vector y. Geometrically, the closest point is the orthogonal projection of y onto the plane.

For the error vector $y-\hat{y}$ to be orthogonal to the column space of $X$, it must be orthogonal to every vector in that space. This is mathematically stated as:

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

Substituting $\hat{y}=X\theta$, we get:

$X^T(y-X\theta )=0$

Distributing $X^T$, we have:

$X^{T}y-X^{T}X\theta =0$

And rearranging this gives us the Normal Equation once again:

$X^{T}X\theta =X^{T}y$

This geometric view shows that the Normal Equation isn't just a result of calculus; it's a fundamental statement about finding the closest projection of a vector onto a subspace.

Normal Equation vs. Gradient Descent: Which to Choose?

So we have two methods to find the optimal $\theta$: the direct Normal Equation and the iterative Gradient Descent. Which one should you use? The choice depends almost entirely on the number of features in your dataset.

Let's read a clear comparison of the two approaches.

Here is a summary of the key differences:

The bottleneck for the Normal Equation is calculating the inverse of $X^{T}X$. This is an $n\times n$ matrix, where $n$ is the number of features. The complexity of matrix inversion is typically cubic, $O(n^3)$. This is fine for a few hundred or a few thousand features, but it becomes incredibly slow if you have, say, 100,000 features.

Gradient Descent, on the other hand, works well regardless of the number of features, making it the standard choice for the very large-scale problems common in modern machine learning.

Conclusion

In this lesson, we demystified the Normal Equation, seeing it as a powerful, direct method for solving linear regression. You now understand its purpose as a closed-form solution that analytically minimizes the least squares cost function.

Key Takeaways:

• The Normal Equation provides a direct, one-step solution to find the optimal parameters in linear regression, unlike the iterative Gradient Descent.
• The formula $\theta =(X^{T}X{)}^{-1}{X}^{T}y$ is derived by setting the gradient of the SSE cost function to zero.
• Geometrically, it represents finding the orthogonal projection of the target vector onto the space spanned by the features.
• The primary drawback is its computational complexity ($O(n^3)$), which makes it impractical for datasets with a very large number of features. For those cases, Gradient Descent is the preferred method.

Understanding both methods gives you a deeper appreciation for how models are trained and the trade-offs involved in different optimization strategies.

Preview of the Next Lesson:

Now that we have two powerful methods to fit our model, how do we know if a linear model was a good choice in the first place? Linear regression rests on several key assumptions (like linearity and constant variance of errors). In our next lesson, we will learn how to use residual plots to diagnose violations of these assumptions, a critical step in building robust and reliable models.