Section 1
Sensitivity to small changes
Every number a computer stores carries a small error, from a measurement or a rounding step. Conditioning asks how far a small change in the input moves the output. When a function moves a lot, rounding in the inputs can cause large changes in the result.
the matrix, the main object
, input and answer vectors
, eigenvalues and singular values
, condition number and errors
, machine epsilon and added amount
How to use this pageClick any colored symbol to see what it means. Answer each prediction before you read its reveal, and read the sentence under each demo.
Picture a lens that magnifies one direction a hundred times and another barely at all. A smudge along the strong direction becomes a smear, and the same smudge along the weak direction stays small. A poorly conditioned matrix works like that lens.
Aim an error and reshape the lens
Challenge +8 XPLower one eigenvalue and aim the arrow until an error of length 1 grows to length 5 or more in the right square. The readout shows the length.
The orange ellipse shows every output error that an input error of length 1 can cause. Its long axis lies along the eigenvector with the smaller eigenvalue. Set both eigenvalues equal and the ellipse becomes a circle. Pull one eigenvalue towards 0.04 and it stretches into a needle. Tick the sign box and the ellipse flips without changing size, so only the size of an eigenvalue matters. That is why the book’s formula uses absolute values.
Predict first. Two inputs have the same length. One lies along the eigenvector of = 4 and the other along the eigenvector of = 0.25. Which output is longer?
The book’s example is the function that multiplies by . It is the operation behind solving a linear system: the answer to is .
Click any coloured symbol to see what it means.
Predict first. The eigenvalues of are 4 and 0.25. Which error does stretch the most?
Suppose has an eigenvalue decomposition (Section 2.7). Then keeps the same eigenvectors, and each eigenvalue becomes its reciprocal. Along the eigenvector for the inverse stretches errors by , so a small eigenvalue means a large stretch. The step that gives the reciprocals is added here and is not printed in the book.
Going deeper: why the inverse has reciprocal eigenvalues (added here, not printed in the book)
Write as with the eigenvectors in the columns of . The product of the proposed inverse with is . The middle factors cancel to the identity matrix , so the proposed inverse is correct.
Click any coloured symbol to see what it means.
The condition number
The lens had a strongest and a weakest direction. Their ratio is one number for the whole matrix. When has an eigenvalue decomposition, the book defines its condition number as
Click any coloured symbol to see what it means.
Predict first. The eigenvalues of are 8, −2 and 0.5. What is its condition number ?
The maximum runs over all pairs. The ratio is never below 1, and it equals 1 only when all eigenvalue magnitudes match. An eigenvalue of 0 makes it infinite.
The book says that when this number is large, inversion is sensitive to error in the input. For a symmetric , the bound below makes this precise. It is added here and is not printed in the book: the relative error of the answer is at most times the relative error of the input.
Click any coloured symbol to see what it means.
Predict first. With = 100, what is the largest amount an input error can grow in relative size?
| Matrix | Eigenvalues | Condition number |
|---|
| identity | 1, 1 | 1 |
| example | 8, −2, 0.5 | 16 |
Going deeper: where the bound comes from (added here, not printed in the book)
Let be symmetric, so every eigenvalue magnitude lies between and . The answer is , and a change in the input gives . The inverse stretches a vector by at most a factor , so . The solution satisfies , so . The first bound, divided by the lower bound on the size of gives , which is the bound with equal to the ratio of the two magnitudes. For a general matrix the eigenvalue ratio can fail to bound the amplification, so the symmetry assumption matters.
How much does the relative error grow?
random pairschosen pairbounds 1/κ and κ
Challenge +8 XPSet the condition number to at least 1000, then set both direction sliders yourself so that the error is amplified by at least 100. The preset buttons do not count. The readout shows the factor.
The horizontal axis is the logarithm of the amplification, so 0 means the error was neither magnified nor shrunk. Most random pairs land well inside the bounds. Only a pair that lines up in the worst way reaches the bound.
Section 3
A property of the matrix itself
Predict first. Where does the sensitivity of the answer come from?
The book makes one point that is easy to miss. This sensitivity is an intrinsic property of the matrix, not a result of rounding during the inversion. Poorly conditioned matrices amplify errors that already exist in the input when they are multiplied by the true inverse.
A test case shows the two sources separately. The Hilbert matrix is a classic example whose condition number grows fast with its size. It is added here and is not printed in the book. Its rounded entries are the input error, and the solve adds the algorithm’s own rounding.
Click any coloured symbol to see what it means.
Predict first. In float32 with = 8, how many correct digits does the full solve keep?
Solving a Hilbert system
perfect solver on rounded inputsfull solve in this formatrule of thumb κ·ε
The violet curve is a perfect solver fed the rounded inputs, with 120-digit arithmetic and so no algorithm error. The orange curve is the real solve in the chosen format, a Gaussian elimination in which every operation is rounded. It can be worse or better than the violet curve, because rounding errors sometimes cancel.
Challenge +8 XPIn the float32 tab, raise the size until the full solve has no reliable digits at all.
Challenge +8 XPIn the float32 tab, raise the size until the rule of thumb reaches 1. From there the rule allows an error as large as the answer itself.
Predict first. Which quantity does the violet curve in the Hilbert chart include?
The gold line is a common rule of thumb, added here and not quoted from the book:
Click any coloured symbol to see what it means.
Here is the machine epsilon, the gap above 1 from Section 4.1. A condition number of in float32 costs about six of the roughly seven decimal digits. In float32 the orange curve stays below the gold line at every size shown.
Going deeper: why the rule of thumb is a heuristic (added here, not printed in the book)
The bound in Section 2 says that a relative change in the input can change the answer by up to times as much, in relative terms. Each stored number carries a rounding error of about in relative size, so estimates the size of the answer error. It is a heuristic: the bound is a worst case, and typical errors fall below it.
Living with a large condition number
The book ends its discussion of conditioning here. Two consequences matter for the later chapters. Both are added here and are not printed in this section of the book.
Predict first. The matrix has = . What is the condition number of ?
- Squaring. The linear least squares example in Section 4.5 of the book works with in its gradient (Equation 4.22). Its condition number is the square of the condition number of . A matrix with of is harmless in float64, but its square has , which hurts in float32.
Click any coloured symbol to see what it means.
Here and are the largest and smallest singular values of . Take the largest as 1. The first bar is the condition number of , the second is exactly its square.
Squaring and regularizing
Challenge +8 XPKeep the smallest singular value at 0.01, then raise the added amount until the condition number of the ridge matrix is 100 or less.
- Regularizing. The term raises every eigenvalue by the same amount, so the smallest one gains the most in relative terms. The constrained version in the same section adds a multiplier times (Equation 4.23). The step that reads as the same kind of term is added here.
Click any coloured symbol to see what it means.
Here is the amount added to the diagonal. The third bar is the condition number after the ridge term, which stays modest whenever is comparable to or larger. The price is a slightly different problem, which is the trade that regularization makes.
Challenge +8 XPDrag the smallest singular value down until the squared condition number passes 1 over the float32 epsilon, so that the squared problem has lost every digit.
What to take away
- A function is poorly conditioned when small input errors produce large output errors.
- For , an eigenvalue stretches errors along its eigenvector by .
- The condition number (Equation 4.2) is the ratio of the largest to the smallest eigenvalue magnitude. It is at least 1, and infinite for a singular matrix.
- The sensitivity belongs to the matrix. For a symmetric , a perfect solver can return up to times the input error, and a real solver adds its own rounding.
- squares the condition number, and adding lowers it.
Final quizCheck yourself
Questions that mix the whole module. Each one is scored, and the score feeds your mastery of this module.
Source: Ian Goodfellow, Yoshua Bengio and Aaron Courville, Deep Learning, MIT Press, 2016, Section 4.2 (pages 82), free to read at deeplearningbook.org. Where the book prints equation numbers, the numbers here follow the book. The order of ideas follows the book. The explanations and all demos were written for this page.