1.23 Least squares and the normal equation: study notes

Learn AI by Story

1. The idea in one sentence

When no straight line passes exactly through all your data points, least squares picks the line whose squared errors add up to the smallest total, and the normal equation XᵀXw = Xᵀy gives that line in one calculation, because the best fit is the projection of the targets onto the span of the data columns.

2. The story from the video

Ravi sells lemonade. He wrote down three days: on a day with 1 hot hour he sold 2 jugs, with 2 hot hours 2 jugs, and with 3 hot hours 5 jugs. The three points do not sit on one straight line, so he cannot draw a perfect rule. Ravi asks for the line that is wrong by the smallest total amount, with each miss squared so big misses count more. The answer is a simple rule: jugs = 1.5 times hot hours, which predicts 1.5, 3 and 4.5 jugs. (The lemonade numbers are illustrative.)

3. Key definitions (glossary)

Term	Precise definition	Plain meaning
Model (linear)	A prediction rule ŷ = w₀ + w₁x₁ + ... , a weighted sum of the inputs.	A recipe that mixes inputs with fixed weights.
Weights (parameters)	The numbers w that the fitting procedure chooses.	The knobs we tune.
Target vector y	The list of observed answers, one per data row.	What actually happened.
Design matrix X	A matrix with one row per example and one column per feature; usually a column of 1s is added for the intercept.	The data table, ready for matrix maths.
Prediction ŷ	ŷ = Xw.	What the model says.
Residual (error)	e = y − Xw, the difference between actual and predicted for each row.	How far off each guess is.
Sum of squared errors (SSE)	eᵀe = ‖y − Xw‖² = Σ eᵢ², the squared length of the residual vector.	The total of all the squared misses.
Least squares	Choosing w to minimise ‖y − Xw‖², the sum of squared errors.	Pick the line whose total squared miss is smallest.
Normal equation	XᵀXw = Xᵀy.	The condition that tells you where the best w sits.
Gram matrix XᵀX	The square matrix of dot products between columns of X.	A summary of how the columns overlap.
Inner product	xᵀy: multiply matching entries and add.	How much two lists agree.
Norm	The length of a vector: ‖x‖ = √(xᵀx) = √(x₁² + x₂² + …).	How long the arrow is.
Orthogonal	xᵀy = 0.	Perpendicular.
Column space	All vectors Xw you can make by mixing the columns of X.	Every prediction the model is able to make.
Projection	The closest point to y inside the column space; the gap is orthogonal to it.	The shadow of y on the space of possible predictions.
Full rank	The columns of X are independent (no redundant column).	Every feature adds something new.
Pseudo-inverse	(XᵀX)⁻¹Xᵀ when X has independent columns (the Moore-Penrose pseudoinverse in general).	The best stand-in for X⁻¹ when X is tall and not square.
Determinant	A number that is 0 exactly when a square matrix is not invertible.	A warning light for non-invertible matrices.
Ridge regression	Minimise ‖y − Xw‖² + λ‖w‖² for a setting λ > 0.	Least squares plus a penalty that keeps the weights small.
Jitter	The small εI added to XᵀX for numerical stability (the book's name for the same trick).	A tiny nudge so the matrix can be inverted safely.
Condition number	The ratio of the largest to smallest stretching of a matrix; large means small input changes can cause big output changes.	How wobbly the solution is.
QR decomposition	X = QR with Q having orthonormal columns and R upper triangular.	A way to solve least squares without forming XᵀX.
Gradient descent	Repeatedly stepping w downhill: w ← w − η∇L.	Solving it by walking down the error bowl.

4. Detailed step-by-step explanation

Step 1: Write the data as a matrix problem

For the video's data (x, y) = (1, 2), (2, 2), (3, 5), we want ŷ = w₀ + w₁x. Put a column of ones and the x values side by side:

X = [[1, 1], [1, 2], [1, 3]] and y = (2, 2, 5).

The unknown is w = (w₀, w₁). We would like Xw = y, which is three equations in two unknowns. There is no solution, because y does not lie in the column space of X.

Step 2: Choose a score for "wrong"

The residual vector is e = y − Xw. We score a line by SSE = eᵀe. Squaring makes every miss positive, punishes big misses more than small ones, and gives a smooth bowl-shaped function that is easy to minimise by calculus or by geometry.

Step 3: The geometry answer

All possible predictions Xw form the column space of X (a plane inside 3-dimensional space here). The best prediction is the point of that plane closest to y. From video 1.22, the closest point is the projection, and the gap e is orthogonal to the plane. Orthogonal to the plane means orthogonal to each column of X, so Xᵀe = 0.

Step 4: Turn the geometry into the normal equation

Xᵀ(y − Xw) = 0 rearranges to XᵀXw = Xᵀy. This is the normal equation ("normal" here is an old word for perpendicular).

Step 5: The calculus answer agrees

The derivative of ‖y − Xw‖² with respect to w is 2Xᵀ(Xw − y). Setting it to zero gives the same equation, as the d2l book shows. Two roads, one answer.

Step 6: Solve it

If X has independent columns (full rank), XᵀX is invertible and w = (XᵀX)⁻¹Xᵀy. Compute XᵀX (a small square matrix), compute Xᵀy (a small vector) and solve a small system. The size depends on the number of features, not the number of data rows.

Step 7: Read the result

The weights tell you the intercept and slope. The residuals tell you where the line misses. The check Xᵀe = 0 tells you that you really found the optimum: the leftover error has nothing left in common with any feature column.

5. Everything the video skipped

History (background, not from the sources opened for this series). Adrien-Marie Legendre published the method of least squares in 1805, and Carl Friedrich Gauss is commonly credited with using it earlier (he claimed around 1795) and with linking it to the normal (bell-curve) error model. There was a famous priority dispute. Treat these dates as background.

Why squares? If you assume the noise in the targets is Gaussian, then maximum likelihood estimation gives exactly the least-squares answer; the book's linear regression chapter shows that the maximum-likelihood solution satisfies the normal equations. Squares are also smooth, so calculus works. Downsides: squares make the fit sensitive to outliers.

The projection matrix (hat matrix). With full rank, the fitted values are ŷ = X(XᵀX)⁻¹Xᵀy. The matrix X(XᵀX)⁻¹Xᵀ is the projection matrix from video 1.22, so it is idempotent (P² = P).

The pseudo-inverse. (XᵀX)⁻¹Xᵀ plays the role of an inverse for a tall matrix. Goodfellow chapter 2 covers the Moore-Penrose pseudoinverse in general, including the cases where the columns are dependent.

When XᵀX cannot be inverted. If two features are copies of each other (or one is a combination of others), X is not full rank, XᵀX has determinant 0, and there are infinitely many equally good weight vectors. Fixes: drop a redundant feature, use the pseudo-inverse (minimum-norm solution), or add ridge.

Ridge. Adding λI makes XᵀX + λI invertible for λ > 0 and shrinks weights. The book calls the same small addition a jitter term for numerical stability. Larger λ means more shrinkage. In practice the intercept is often left unpenalised; the example below penalises both weights only to keep the arithmetic simple.

Numerical practice. Forming XᵀX squares the condition number, which can lose precision. The book notes that computing an explicit inverse is generally not recommended. Software uses QR or the SVD: factor X = QR, then solve Rw = Qᵀy. For huge data, gradient descent (stochastic or mini-batch) is used instead, and that is how neural networks are trained.

Many features, more than rows. If there are more features than data rows, X cannot have independent columns, and plain least squares has many solutions. Ridge and other regularisation become essential.

Links in the roadmap.

1.17 Norms: the error is the squared Euclidean norm of the residual.
1.20 Rank: full column rank is the condition for the normal equation to have a unique solution.
1.21 Basis: the columns of X are a basis for the column space when independent.
1.22 Orthogonality and projections: the geometric heart of this video.
Later: PCA (projection onto directions of greatest spread) and linear regression in Module 2 (loss, regularisation, gradient descent, evaluating a model on new data).

Limitations. Least squares fits a straight-line (or linear-in-the-weights) rule only; it is sensitive to outliers; with three points the fit says little about the future; a good fit on the training data does not guarantee a good fit on new data.

6. Worked examples

Example A (from the video): hot hours to jugs

Data: (1, 2), (2, 2), (3, 5).

X = [[1, 1], [1, 2], [1, 3]], y = (2, 2, 5).
XᵀX: entries are 1+1+1 = 3, 1+2+3 = 6, and 1+4+9 = 14. So XᵀX = [[3, 6], [6, 14]].
Xᵀy: first entry 2+2+5 = 9, second entry 1·2 + 2·2 + 3·5 = 2 + 4 + 15 = 21. So Xᵀy = (9, 21).
Determinant of XᵀX = 3·14 − 6·6 = 42 − 36 = 6. Nonzero, so invertible.
Inverse = (1/6)[[14, −6], [−6, 3]].
w = inverse times (9, 21): first entry (14·9 − 6·21)/6 = (126 − 126)/6 = 0; second entry (−6·9 + 3·21)/6 = (−54 + 63)/6 = 1.5. So w = (0, 1.5) and the line is ŷ = 1.5x.
Predictions: 1.5, 3, 4.5. Errors e = y − ŷ = 0.5, −1, 0.5.
SSE = 0.25 + 1 + 0.25 = 1.5.
Check Xᵀe: sum of errors = 0.5 − 1 + 0.5 = 0; weighted sum 1·0.5 + 2·(−1) + 3·0.5 = 0.5 − 2 + 1.5 = 0. Both zero, so the errors are orthogonal to both columns.
Compare with another line, ŷ = x + 1: predictions 2, 3, 4, errors 0, −1, 1, SSE = 0 + 1 + 1 = 2, which is more than 1.5. The least-squares line wins.

Example B (new): four days of data

Data: (0, 1), (1, 3), (2, 4), (3, 8). Imagine hours of study versus quiz points (illustrative).

X = [[1, 0], [1, 1], [1, 2], [1, 3]], y = (1, 3, 4, 8).
XᵀX = [[4, 6], [6, 14]] (4 rows; sum of x = 6; sum of x² = 0+1+4+9 = 14).
Xᵀy = (1+3+4+8, 0·1+1·3+2·4+3·8) = (16, 3+8+24) = (16, 35).
Determinant = 4·14 − 6·6 = 56 − 36 = 20.
w₀ = (14·16 − 6·35)/20 = (224 − 210)/20 = 0.7.
w₁ = (−6·16 + 4·35)/20 = (−96 + 140)/20 = 2.2.
The line is ŷ = 0.7 + 2.2x. Predictions: 0.7, 2.9, 5.1, 7.3.
Errors: 0.3, 0.1, −1.1, 0.7. Sum of errors = 0.3 + 0.1 − 1.1 + 0.7 = 0. Weighted sum = 0 + 0.1 − 2.2 + 2.1 = 0. Orthogonality holds.
SSE = 0.09 + 0.01 + 1.21 + 0.49 = 1.8.

Example C (new): ridge on the video's data

Add λ = 1 to the diagonal of the video's XᵀX (penalising both weights for simplicity).

XᵀX + I = [[4, 6], [6, 15]]; right side stays (9, 21).
Determinant = 4·15 − 36 = 24.
w₀ = (15·9 − 6·21)/24 = (135 − 126)/24 = 0.375.
w₁ = (−6·9 + 4·21)/24 = (−54 + 84)/24 = 1.25.
Ridge line: ŷ = 0.375 + 1.25x, with smaller slope than the least-squares 1.5. Shrinkage in action.

7. Comparison tables

Method	Idea	Strength	Weakness
Normal equation	Solve XᵀXw = Xᵀy	One shot, exact, great for few features	Squares the condition number; fails if not full rank
QR	X = QR, solve Rw = Qᵀy	More accurate, standard in libraries	Slightly more work
Pseudo-inverse / SVD	Minimum-norm solution	Works when columns are dependent	Heavier computation
Gradient descent	Walk downhill on the error	Scales to huge data and non-linear models	Needs learning rate and many steps
Ridge	Add λI	Stable, resists overfitting	Adds a setting (λ) and some bias

Geometry view	Algebra view
Closest point to y in the column space	Minimise ‖y − Xw‖²
Gap is orthogonal to the space	Xᵀe = 0
Projection matrix X(XᵀX)⁻¹Xᵀ	ŷ = Xw

8. Common mistakes and myths

Myth: the best line passes through the points. It usually passes through none of them.
Mistake: forgetting the column of ones, which forces the line through the origin. (In Example A the intercept came out as exactly 0 by coincidence of the data, not by assumption.)
Mistake: swapping Xᵀy for Xyᵀ or mixing up shapes. XᵀX is features by features; Xᵀy is a vector with one entry per feature.
Myth: least squares always has one answer. It does only when the columns are independent.
Mistake: inverting XᵀX when features are nearly copies of each other. The result can be wildly unstable.
Myth: smaller training error means a better model. A wiggly model can drive the training error to 0 and still fail on new data.
Mistake: forgetting that squared error is sensitive to outliers.
Mistake: thinking ridge is a different problem. It is least squares plus a small pull toward zero.

9. Real-life and AI uses

Linear regression in statistics, economics and science for trend lines and forecasts.
Baselines in machine learning: a quick least-squares model is often the first thing to try.
Feature-based models: the last layer of many networks can be fitted by least squares or ridge.
Curve fitting and calibration of sensors, using polynomials as features.
Recommender systems: alternating least squares solves many small least-squares problems.
Signal processing and GPS: fitting positions from noisy measurements.
Projection idea behind PCA and other dimensionality-reduction methods.

10. Self-check questions

Why can't Ravi draw a line through all three points? Answer: they are not collinear, so Xw = y has no solution.
What does least squares minimise? Answer: the sum of squared residuals, ‖y − Xw‖².
State the normal equation. Answer: XᵀXw = Xᵀy.
In the video, what are XᵀX and Xᵀy? Answer: [[3, 6], [6, 14]] and (9, 21).
What line does the video find and what is its SSE? Answer: ŷ = 1.5x, SSE 1.5.
What does Xᵀe = 0 mean geometrically? Answer: the error vector is orthogonal to every column of X, so the prediction is the projection of y.
When does the normal equation have a unique solution? Answer: when X has full column rank, so XᵀX is invertible.
What does ridge change in the formula? Answer: it adds λI to XᵀX.
Why do libraries prefer QR over the normal equation? Answer: forming XᵀX squares the condition number and loses accuracy.
Check: for data (0,1), (1,3), (2,4), (3,8), what is the slope? Answer: 2.2.

11. Key takeaways, go deeper, next

Key takeaways

Least squares = smallest sum of squared misses.
Best fit = projection of y onto the column space of X.
Normal equation: XᵀXw = Xᵀy; the errors are orthogonal to the features.
Needs full rank; ridge and QR make it robust.
For very large problems, gradient descent takes over.

Go deeper

Read the book's chapter on linear regression and the section on orthogonal projections.
Fit a line with numpy (np.linalg.lstsq) and confirm Xᵀe = 0.
Try two nearly identical columns and watch the condition number grow.
Try ridge with several λ values and plot the slope.

Next roadmap ID: 1.24 Tensors and einsum.

12. Sources and further reading

Accuracy note: The lemonade data and the quiz-points data are illustrative, not real measurements; all arithmetic was re-checked with Python. The Legendre 1805 and Gauss history is general background not taken from the opened sources.

Search This Blog