\( \newcommand{\vect}[1]{\boldsymbol{\mathbf{#1}}} \newcommand{\mat}[1]{\boldsymbol{\mathbf{#1}}} \newcommand{\R}{\mathbb{R}} \newcommand{\E}{\mathbb{E}} \newcommand{\Prob}{\mathbb{P}} \newcommand{\T}{^{\top}} \newcommand{\norm}[1]{\lVert #1 \rVert} \newcommand{\abs}[1]{\lvert #1 \rvert} \newcommand{\ihat}{\mkern1mu\hat{\boldsymbol{\imath}}\mkern2mu} \newcommand{\jhat}{\mkern1mu\hat{\boldsymbol{\jmath}}\mkern2mu} \newcommand{\pd}[2]{\frac{\partial #1}{\partial #2}} \newcommand{\argmax}{\operatorname*{arg\,max}} \newcommand{\argmin}{\operatorname*{arg\,min}} \newcommand{\cdata}[1]{\class{c-data}{#1}} \newcommand{\cmodel}[1]{\class{c-model}{#1}} \newcommand{\ctruth}[1]{\class{c-truth}{#1}} \newcommand{\cgrad}[1]{\class{c-grad}{#1}} \newcommand{\closs}[1]{\class{c-loss}{#1}} \newcommand{\cparam}[1]{\class{c-param}{#1}} \newcommand{\csecond}[1]{\class{c-second}{#1}} \renewcommand{\,}{\mkern3mu} \)

M03.7 · Least squares and the pseudoinverse

A free, illustrated module of 4 lessons and one interactive in M03 Linear Algebra II: Decompositions: Least squares as projection; Three ways to solve, and which to trust; The pseudoinverse; Ridge, truncation and noise.

M03.7 L2 · Intermediate 4 lessons · about 100 min Live · in review

Part of M03 Linear Algebra II: Decompositions in the Mathematics track.

When a system has more equations than unknowns, there is usually no exact answer, and least squares picks the best one: the x whose image A x is the point of the column space closest to b. These four lessons derive the normal equations from a single right angle, compare three ways of solving them and learn which one to trust, build the pseudoinverse that still gives one answer when the columns are dependent, and read ridge regression and truncated SVD as two filters on the singular values that stop noise from being blown up.

What you need first. Projection onto a subspace and the QR factorisation (M02.10), the four subspaces of a matrix (M02.7), eigenvalues (M03.1) and the singular value decomposition with its four subspaces (M03.5). Linear regression with a design matrix (ML01.4) and ridge regression (ML01.9) supply the machine-learning setting but are not required.

Lessons

1. Least squares as projection M03.7.1 25 min

   The best least-squares fit makes the residual stand at a right angle to every column of A. Derive the normal equations from that one right angle, meet the hat matrix that projects onto the column space, and check it all on four points.

2. Three ways to solve, and which to trust M03.7.2 25 min

   Solve the same least-squares problem by the normal equations, by QR and by the SVD. Derive the SVD formula, compare the cost of the three routes, and measure on a degree-10 polynomial fit how the normal equations lose about twice as many digits.

3. The pseudoinverse M03.7.3 25 min

   When two features are copies of each other, least squares has infinitely many solutions. The pseudoinverse, built from the SVD, picks the shortest one. Prove why, check the four Penrose conditions, and meet numpy.linalg.pinv and its cut-off.

4. Ridge, truncation and noise M03.7.4 25 min

   Through the SVD, least squares divides the noise in b by each singular value, so a small one blows it up. Derive ridge regression’s filter factors, compare them with truncated SVD, and see both tame a fit with a nearly repeated feature.

The interactive

M03.7-X1 · Least squares as projection. Set the heights of three points with sliders or by dragging them. The vector b of the heights is drawn in three dimensions beside the plane of the columns, with its projection and the residual meeting the plane at a right angle, while a second panel shows the same fit as a line. It lives in Least squares as projection.