Normal Equation vs Gradient Descent
Comparing closed form analytical matrix inversion against iterative gradient descent for linear regression.
Solving Linear Regression
In Ordinary Least Squares Linear Regression, we want to find weight vector $w$ that minimizes Mean Squared Error:
$$J(w) = \frac{1}{2m} | Xw - y |^2$$
We can solve this problem in two completely different ways:
┌──────────────────────────┬──────────────────────────┐
│ 1. NORMAL EQUATION │ 2. GRADIENT DESCENT │
├──────────────────────────┼──────────────────────────┤
│ Closed-form analytical │ Iterative optimization │
│ matrix math solution. │ step by step. │
│ Exact answer in 1 step! │ Requires tuning rate η. │
│ Slow for large features. │ Scales to millions! │
└──────────────────────────┴──────────────────────────┘
1. The Normal Equation (Analytical Solution)
Setting the derivative $\nabla_w J(w) = 0$ yields an exact closed form equation:
$$w = (X^T X)^{-1} X^T y$$
- $X$: Data feature matrix of shape $[m \times n]$ ($m$ samples, $n$ features).
- $y$: Target vector of shape $[m \times 1]$.
- $w$: Optimal weight vector of shape $[n \times 1]$.
Advantages of Normal Equation
- Zero Iterations: Computes the exact global minimum in a single step.
- Zero Hyperparameters: You do not need to pick or tune a learning rate $\eta$.
- No Feature Scaling Required: Works identically whether features are normalized or un-normalized.
Disadvantages of Normal Equation
- High Computational Complexity: Computing $(X^T X)^{-1}$ requires matrix inversion of shape $[n \times n]$. Matrix inversion takes $\mathcal{O}(n^3)$ computational time.
- Singular Matrix Risk: If features are linearly dependent or $n > m$, $X^T X$ is singular and cannot be inverted directly (requires Moore-Penrose Pseudo-Inverse via SVD).
2. Gradient Descent (Iterative Solution)
Updates weights iteratively:
$$w_{\text{new}} = w_{\text{old}} - \eta \frac{1}{m} X^T (X w - y)$$
Computational complexity per iteration: $\mathcal{O}(m \cdot n)$.
Detailed Comparison Matrix
| Dimension | Normal Equation | Gradient Descent |
|---|---|---|
| Solution Type | Closed Form Analytical | Iterative Approximation |
| Learning Rate $\eta$ | Not Required | Mandatory to tune |
| Iterations | 1 Step | Hundreds to Thousands |
| Feature Count Scaling ($n$) | Slow $\mathcal{O}(n^3)$ (Fails if $n > 10,000$) | Fast $\mathcal{O}(n)$ (Scales to Millions) |
| Sample Count Scaling ($m$) | Linear $\mathcal{O}(m)$ | Scales via Mini Batches |
| Feature Scaling | Not Needed | Mandatory for fast convergence |
Say this out loud
The Normal Equation solves linear regression analytically in one step using w = (X^T X)^-1 X^T y without tuning a learning rate. However, matrix inversion has O(n^3) cubic complexity, making it impractically slow for large feature counts. Gradient Descent uses iterative O(n) steps, scaling smoothly to high dimensional datasets.
Followups to expect
- How does Ridge L2 regularization change the Normal Equation? L2 regularization adds $\lambda I$ to $X^T X$: $w = (X^T X + \lambda I)^{-1} X^T y$. This guarantees $(X^T X + \lambda I)$ is invertible even when $n > m$ or features are collinear!
- Why is pseudo-inverse used in practice for Normal Equation?
np.linalg.pinvuses Singular Value Decomposition (SVD) to compute the pseudo-inverse, handling non invertible singular matrices cleanly.
Check yourself
What is the exact closed form Normal Equation formula for Ordinary Least Squares Linear Regression?