Normal equation closed-form solution: Question bank

This is a conceptual stress-test for the normal equation. No heavy arithmetic here — every item targets a misunderstanding or a boundary case that the closed-form solution invites. Try to answer out loud before revealing.

Before we start, three symbols recur — let's pin them to plain words:

Keep in mind two shape facts that decide almost everything below:

Overdetermined = more equations than unknowns = more rows than columns ( $m > n + 1$ ). Usually good.
Underdetermined = more unknowns than equations = more columns than rows ( $m < n + 1$ ). Usually trouble.

See Underdetermined vs Overdetermined Systems if those words are new.

True or false — justify

TF1. "The normal equation and Gradient Descent converge to different answers on the same convex regression problem."

False. Both minimise the same bowl-shaped cost; they reach the same unique minimum (up to tiny numerical error). They differ in how they get there, not where.

TF2. "The normal equation needs a learning rate."

False. There is no step size and no iteration to tune — it is a single algebraic formula. That absence of a learning rate is exactly its selling point over gradient descent.

TF3. "Feature scaling changes the answer the normal equation gives."

False for the predictions. Unlike gradient descent, the normal equation is not affected by feature scale for the fitted line itself — see Feature Scaling. Scaling can still help numerical conditioning of

X^{T} X

, but the mathematical solution is scale-equivariant.

TF4. "If

X^{T} X

is invertible, the least-squares solution is unique."

True. Invertible

X^{T} X

means

X

has full column rank, so no feature is a redundant combination of the others, leaving exactly one minimiser.

TF5. "The residual vector at the optimum is orthogonal to every column of

X

True. That is literally what

X^{T} (X θ - y) = 0

says — each row of

X^{T}

(a feature column) dotted with the residual is zero. This orthogonality is why it's called the "normal" equation.

TF6. "More training examples make

X^{T} X

harder to invert."

False. Adding rows (examples) never shrinks the rank; it tends to stabilise invertibility. What breaks invertibility is redundant or excess columns (features), not extra rows.

TF7. "For a huge number of features

n

, the normal equation is still the smart choice."

False. Inverting an

(n + 1) \times (n + 1)

matrix costs roughly

O (n^{3})

; once

n

is in the tens of thousands, Gradient Descent scales far better.

TF8. "If

X

is rank-deficient, there is no least-squares solution."

False. There are infinitely many solutions, all achieving the same minimum error. The Moore-Penrose Pseudoinverse simply picks the one with smallest norm.

TF9. "Multiplying by

X^{T}

is optional decoration in the formula."

False.

X

is generally not square, so

X^{- 1}

doesn't exist. Multiplying by

X^{T}

produces the square matrix

X^{T} X

, which can have an inverse — that step is what makes solving possible.

TF10. "The

\frac{1}{2 m}

in the cost function changes where the minimum is."

False. A positive constant multiplier rescales the whole bowl but does not move its lowest point, so the optimal

θ

is identical with or without it.

Spot the error

SE1. "

X

isn't square, so I'll just compute

X^{- 1} y

A non-square matrix has no inverse at all — the operation is undefined. You must form

X^{T} X

(square) first; the correct object is

(X^{T} X)^{- 1} X^{T} y

SE2. "

det (X^{T} X) = 0

, so my dataset has no good fit."

A zero determinant means the fit is not unique, not that it's bad. Often a perfect fit exists (as in the redundant-feature example) — you just need the pseudoinverse to select one solution.

SE3. "I have 3 examples and 5 features, but

X^{T} X

5 \times 5

, so I'll invert it."

With

m = 3 < n + 1

you are underdetermined;

X^{T} X

is a

5 \times 5

matrix of rank at most

3

, hence singular and non-invertible. The plain formula cannot apply.

SE4. "Two features are perfectly correlated but I'll keep both — the formula will sort it out."

Perfect correlation makes two columns linearly dependent, so

X^{T} X

becomes singular and the inverse blows up. Drop one feature or use Ridge Regression, which keeps

X^{T} X + λ I

invertible.

SE5. "I forgot the column of

1

's in

X

; that only shifts things a little."

Without that column there is no intercept term

θ_{0}

, forcing the fitted line through the origin. That can massively distort the fit unless the data genuinely passes through zero.

SE6. "

X^{T} X

is symmetric, so its inverse might not be."

The inverse of a symmetric invertible matrix is symmetric. There's no error in the fact, but the reasoning "might not be" is wrong — symmetry is preserved under inversion.

SE7. "My condition number is

1 0^{12}

but the matrix is technically invertible, so I'm fine."

Technically invertible but numerically near-singular: tiny data noise gets amplified enormously, giving unstable

θ

. Prefer QR Decomposition or ridge regularisation over literally inverting.

SE8. "I'll compute

(X^{T} X)^{- 1}

explicitly and store it — cleanest way."

Explicit inversion is the least numerically stable route. Solving the linear system

X^{T} X θ = X^{T} y

directly (e.g. via QR Decomposition) avoids forming the inverse and is more accurate.

Why questions

WHY1. Why is it valid to set the gradient to zero and stop, rather than checking it's a minimum?

The MSE cost is a convex (bowl-shaped) quadratic, so its single stationary point is guaranteed to be the global minimum — there are no other critical points to worry about.

WHY2. Why does

X^{T} X

being invertible correspond to "full column rank"?

X^{T} X

shares the null space of

X

; it is invertible exactly when

X

's columns are linearly independent, i.e. no feature is a combination of the others.

WHY3. Why does the residual being orthogonal to the column space give the best fit?

The prediction

X θ

lives in the column space of

X

; the closest point in that space to

y

is its orthogonal projection, and "closest" means smallest squared error — that projection is precisely the least-squares fit.

WHY4. Why does Ridge Regression rescue a singular

X^{T} X

It adds

λ I

(

λ > 0

) to the diagonal, which lifts every eigenvalue away from zero, guaranteeing

X^{T} X + λ I

is invertible even when

X^{T} X

is not.

WHY5. Why prefer gradient descent when features number in the millions?

Each gradient step is a matrix-vector product (

O (mn)

), whereas the normal equation needs an

O (n^{3})

inversion; for enormous

n

the cubic cost dominates and becomes infeasible.

WHY6. Why can Polynomial Regression still use the normal equation despite being "nonlinear"?

Polynomial regression is linear in the parameters — you just add columns like

x^{2}, x^{3}

X

. The model is a linear combination of fixed feature transforms, so the same closed form applies.

WHY7. Why does the pseudoinverse return the minimum-norm solution among infinitely many?

When solutions form a whole subspace, the Moore-Penrose Pseudoinverse projects onto the part orthogonal to the null space, giving the unique solution with the smallest length — a natural, non-arbitrary tie-breaker.

WHY8. Why is the normal equation immune to learning-rate divergence that plagues gradient descent?

It performs no iterative stepping at all — there is nothing to overshoot. It solves the exact optimality equations algebraically in one shot.

Edge cases

EC1.

m = 1

(a single training example) with

n \geq 1

features.

Underdetermined: one row can't pin down multiple parameters, so

X^{T} X

is singular. Infinitely many lines pass through one point; the pseudoinverse gives the minimum-norm one.

EC2. Exactly

m = n + 1

examples, all rows independent.

X

is square and invertible, so there's a unique zero-error interpolating fit — the model passes exactly through every point (which usually means overfitting).

EC3. A duplicate feature column (feature copied twice).

The two identical columns are linearly dependent, making

X^{T} X

singular. Predictions are still well-defined, but the individual

θ

values for the duplicated pair are not uniquely determined.

EC4. A constant feature column (some feature equals

5

for every example).

It's a scalar multiple of the intercept column of

1

's, so it's redundant — another source of rank deficiency. Remove it; its effect is already absorbed by

θ_{0}

EC5. All target values identical (

y

constant).

Perfectly fittable: the intercept alone captures it (

θ_{0} = c

, other

θ_{j} = 0

), and the residual is exactly zero. No degeneracy in

X

is caused by

y

being constant.

EC6. Two features that are nearly but not exactly collinear.

X^{T} X

is invertible in theory but ill-conditioned; the inverse amplifies noise, so

θ

becomes wildly sensitive. This is the practical case where Ridge Regression shines.

EC7. Adding an example that is an exact copy of an existing row.

Rank is unchanged (no new independent direction), so invertibility is unaffected. The fit shifts slightly because that point now counts twice in the error sum.

EC8.

y

lies exactly in the column space of

X

(a perfect linear relationship exists).

The residual is zero and the fit is exact. If

X

is also full-rank the solution is unique; if not, infinitely many exact fits exist and the pseudoinverse picks the minimum-norm one.

Recall Quick self-check

Singular $X^{T} X$ means the fit is bad. ::: False — it means the fit is non-unique, often with a perfect solution available via the pseudoinverse. The formula requires more features than examples. ::: False — it requires more (or equal) examples than features for a unique solution ( $m \geq n + 1$ , full rank). Why is $X^{T}$ multiplied in front of $y$ ? ::: To project the targets onto the feature (column) space and produce a square, solvable system.