\( \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.8 · Matrix norms and conditioning

A free, illustrated module of 4 lessons and one interactive in M03 Linear Algebra II: Decompositions: Measuring the size of a matrix; The condition number; Ill-conditioning in data; Conditioning and gradient descent.

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

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

How big is a matrix, and how much can it magnify a small error? These four lessons measure the size of a matrix in several honest ways (the length of its entries, its largest stretch, its largest column and row sums), turn the ratio of its largest to its smallest stretch into the condition number that says how many digits a linear solve can lose, find that number at work in nearly collinear data, and show that the same number sets the speed of gradient descent on a quadratic bowl.

What you need first. Vector norms and their unit shapes (M02.3), inverses (M02.7) and determinants (M02.8), the Rayleigh quotient of a symmetric matrix (M03.3), positive definite quadratics and their gradient (M03.4), the singular value decomposition (M03.5) and least squares with ridge (M03.7). The last lesson uses gradient descent as met in ML01.5.

Lessons

1. Measuring the size of a matrix M03.8.1 25 min

   Four honest ways to measure how big a matrix is: the length of its entries, its largest stretch, its largest column sum and its largest row sum. Derive each from the singular values or the unit shapes, and prove that the stretch of a product is at most the product of the stretches.

2. The condition number M03.8.2 25 min

   Why a 1.7% change in the data can move the solution of a linear system by 25%. Derive the condition number as the worst error amplification, compute it from the singular values, prove that forming A-transpose A squares it, and see why the determinant says nothing about it.

3. Ill-conditioning in data M03.8.3 25 min

   Nearly collinear features make the condition number of a design matrix explode, so that one nudged data point swings the fitted coefficients. Measure it on Hilbert and polynomial matrices, count the digits it costs, and test three remedies: standardising, QR and ridge.

4. Conditioning and gradient descent M03.8.4 25 min

   Gradient descent on a quadratic bowl splits into one simple race per eigenvalue. Derive the largest safe step, the best fixed step and its rate (kappa - 1)/(kappa + 1), and see why rescaling the features turns a slow zigzag into one straight step.

The interactive

M03.8-X1 · Condition explorer. Drag the two columns of a 2 by 2 matrix and watch a small disc of perturbed targets turn into a long ellipse of solutions as the columns line up, with the singular values, the condition number, the determinant and the worst error amplification read out beside the bound. It lives in The condition number.