The Shortest Weights That Fit Best

Chapter 13's lesson When the Normal Equations Break left a fit with no single answer. When columns of the design matrix $X$ repeat the same information, such as a length recorded in both feet and inches, $X^\top X$ is singular, the normal equations have no unique answer, and infinitely many weight vectors $w$ tie for the smallest squared error.

The standard way to break the tie is to choose, among all those best-fitting $w$, the one with the smallest length $\|w\|$. The pseudoinverse $X^+$ finds it directly from the SVD $X = U\Sigma V^\top$ of Chapter 11:

For an $m \times n$ matrix $X$ ($m$ examples, $n$ features), $\Sigma$ is $m \times n$. $\Sigma^+$ is its $n \times m$ counterpart: the same diagonal layout, with each nonzero singular value $\sigma$ replaced by $1/\sigma$. Singular values that are zero stay $0$.

On a computer, a singular value that should be exactly zero usually comes out as a tiny leftover such as $10^{-16}$. So use this rule: a singular value counts as zero when it is at most $10^{-10}$ times the largest singular value.

Task: write min_norm_weights(X, y) returning $w = X^+ y$ as a list, every entry rounded to 4 decimal places.

• X is a list of rows, one per example. Its columns may be redundant, and it may have more columns than rows.
• When the columns of $X$ are independent, this matches the normal-equations answer exactly; the pseudoinverse only changes things when that answer isn't unique.