How to use this pageClick any colored symbol for a short explanation. Then drag the lines and points, press the buttons and type into the grids. Challenges mark themselves when you reach them.
, , matrix, unknowns, results hoped-for inverse pseudoinverse , , SVD pieces small safety number
Section 1
Systems with no inverse
Press a code on a vending machine and a snack drops out. Now run it backwards: from the snack, find the code. That works only if every snack has exactly one code.
A linear system is the same puzzle with numbers. A matrix turns an unknown vector into a result :
Click any coloured symbol to see what it means.
Predict firstTake a matrix with 3 rows and 2 columns: three equations, two unknowns. For a typical right side, how many exact solutions are there?
The matrix has rows and columns. So holds unknowns, and holds results, one per equation.
Chapter 2 solved this with an inverse. The book writes that idea with a matrix , a left-inverse of , meaning . Multiply both sides of 2.44 by it:
Click any coloured symbol to see what it means.
A true inverse needs a square with independent rows. Machine learning rarely hands you one. Next you see why, and then how to cope.
Hunt for the crossing point
Each equation is a line in the plane of the unknowns. Grab a line and drag it. A solution must sit on every line.
equation 1equation 2equation 3
Challenge +8 XPOpen the tall tab and drag the lines until all three pass through one point. The preset button does not count.
One equation leaves a whole line of answers. Two independent equations cross once. Three lines in a plane meet only by luck, and real data never supplies that luck.
The book names both failures: a tall () can have no solution, and a wide () can have many. The pseudoinverse still returns a definite answer: the best compromise for the tall case, the point nearest the origin for the wide one.
Going deeper
Row of times equals the number . In the plane of the unknowns, that is a straight line. The vector points perpendicular to it, and says how far from the origin it sits (in units of the length of ).
Moving a line changes . Turning a row of would tilt it. The tall demo keeps the rows fixed, so only the right side moves.
The pseudoinverse as a limit
Picture a table with one short leg. It rocks and has no single resting place. Fold a beer mat under the leg and it sits firm. The book's definition does this to a matrix, then pulls the mat away bit by bit:
Click any coloured symbol to see what it means.
Predict firstTake a wide matrix, so that the product has no inverse. As the safety number shrinks to 0, what happens to the answer from the formula inside the limit?
Read it from the inside out. The product is square whatever the shape of , but it has no inverse when the columns of are dependent. Adding is the beer mat.
Why does the mat work? Every eigenvalue of is at least 0, so every eigenvalue of is at least . A matrix with no zero eigenvalue has an inverse. The arrow says shrinks to 0 while staying positive.
Shrinking towards zero
Drag the gold line on the top chart, or use the slider. The dashed lines are , computed by the SVD method of the next section.
Challenge +8 XPGet the distance to below 0.0001. The lower chart shows how.
The entries settle onto the dashed lines. On the log-log chart the gap is a straight line: it shrinks in proportion to . In the tall case the formula already works at , so only distorts the answer.
The limit is elegant, but nobody computes it this way: a tiny makes the inverse inaccurate on a computer. The book gives a practical recipe, and it is the next section.
Going deeper: why the limit exists (added here, not printed in the book)
Section 3 splits into rotations and a diagonal scaling. After the split the limit acts on each diagonal entry on its own. For the factor tends to . For it is for every , so it stays 0. That is exactly how Equation 2.47 treats the diagonal entries.
Computing it with the SVD
To undo a machine you take it apart. Section 2.7 gave the eigendecomposition, which works only for some square matrices:
Click any coloured symbol to see what it means.
Section 2.8 gave the singular value decomposition (SVD), which works for every real matrix of any shape. It splits into a rotation, a stretch and another rotation:
Click any coloured symbol to see what it means.
Build a matrix, get its pseudoinverse
Type the entries of . The demo splits it, builds , then walks a vector through the recipe.
For an by matrix, is by and is by . Both are orthogonal: perpendicular unit columns, so each keeps lengths. is by , with the singular values on its diagonal and zeros elsewhere.
Challenge +8 XPType your own entries (presets do not count) until a singular value is exactly 0 and gets a zero on its diagonal.
The book then gives the formula used in practice:
Click any coloured symbol to see what it means.
is the pseudoinverse of , built by two rules. Reciprocate every non-zero diagonal entry (zeros stay zeros, and 1/0 is never taken). Then transpose.
Challenge +8 XPType your own entries (presets do not count) so that every singular value stays above zero, the smallest is below 0.05, and an entry of is above 50.
Read 2.47 right to left as a recipe: rotates into the frame where acts, undoes each stretch, and rotates back. A direction that flattened to zero cannot be recovered, so sends it to zero.
With Rank 1 a singular value hits 0 and the matching entry of is 0, not huge. With Almost rank 1 the small singular value is tiny but not zero, so its reciprocal is large. That is why libraries treat singular values below a tolerance as zero.
Reciprocal, with and without
Drag on the chart to place a probe on the axis.
Above the violet curve hugs the dashed reciprocal. Near 0 it turns round and heads to 0, while the reciprocal explodes. Equation 2.47 makes the same choice with an exact switch: reciprocal above 0, zero at 0.
Going deeper: shapes and the tolerance
( by ) times ( by ) times ( by ) gives an by matrix. That is the right shape to send in back to in .
The demo's SVD routine comes from an eigendecomposition of . It is a toy stand-in for the library routines used in practice. Its tolerance is one part in a million of the largest singular value, a choice made here.
What the pseudoinverse returns
The pseudoinverse answers 2.44 with
(The star only marks this answer here.) What it is depends on the shape of .
More columns than rows: the shortest solution
A wide has many solutions. The pseudoinverse picks the one with minimal Euclidean norm :
More rows than columns: the closest fit
A tall may have no solution. The pseudoinverse picks the that brings closest to . The leftover is the residual:
Minimal norm and least residual
Wide tab: drag the orange point along the line of solutions to the shortest one. Tall tab: drag it to the lowest point of the contour map.
Challenge +8 XPWide tab: drag the orange point until its length is within 0.05 of the shortest solution, without using the jump button.
Challenge +8 XPTall tab: drag the orange point until its total squared residual is within 0.03 of the minimum.
Wide: the shortest solution is where a circle around the origin touches the line, so is perpendicular to the line. The lower chart shows length against position, with its bottom exactly there.
Tall: the pseudoinverse point sits among the lines, near the small triangle they form. The bars show how it spreads the unavoidable error over the equations.
Going deeper: the two rules combined (added here, not printed in the book)
For any shape and rank: among all that make the residual as small as possible, the pseudoinverse picks the one with the smallest norm. When the residual can reach 0 there may be many such , and the same rule picks the shortest. For a square invertible , is the ordinary inverse.
Fitting a line
This section is an application added to the lesson, not in the book. It is the tall case in the form every machine learning course meets first: draw the best straight line through scattered points.
Each point gives one equation . The two unknowns are the slope and the intercept . In the shape of 2.44:
Least squares with the pseudoinverse
With more than two points the system is tall, and returns the line with the smallest total squared vertical miss: least squares. Drag the points, add some, remove some.
line from vertical missesdata points
Challenge +8 XPDrag the points until the fitted line is flat (slope between −0.05 and 0.05) with at least 3 points on the canvas.
Challenge +8 XPRemove points until only one is left. Read what the pseudoinverse does when the system turns wide.
Pull one point far away and the line tilts towards it: squared misses punish big errors hard. With two points the line passes through both. With one point the system is wide, many lines fit, and the pseudoinverse picks the shortest pair .
The readout compares the answer with the classical normal equations , which is 2.46 at . They agree whenever is invertible.
Going deeper: one point (added here)
For a single point the pair is . That is the pseudoinverse of the single row : its transpose divided by its squared length.
- A system with a non-square has no solution or many, so no ordinary inverse exists.
- The pseudoinverse is the limit of as shrinks to 0 from above.
- In practice it is , where reciprocates the non-zero singular values and transposes.
- For a wide , is the minimal-norm solution. For a tall , it is the whose is closest to .
- Least squares line fitting is the tall case, and the pseudoinverse gives its answer.
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 2.9 (pages 45–48), 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.