First PrinciplesStart anywhere. Prove it, then move on.

Rung 37

SVD and dimensionality reduction

Throw away most of the numbers and keep almost all of the meaning.

Best attempted after 36. Eigenvalues and eigenvectors. Nothing stops you trying this now — the gate will tell you if you were right.

The gate

Compress a greyscale image with the singular value decomposition. Plot reconstruction error against the number of components kept, and report how many are needed to hold ninety per cent of the total. Then show the image at that setting beside the original and say what was actually lost.

Nobody checks this but you. Do it honestly and the rungs above hold; do it loosely and they will not, somewhere further up where the cause is much harder to find.

Eigenvectors need a square matrix and do not always exist. The singular value decomposition has neither limitation: every matrix, of any shape, factors into three pieces — a rotation, a scaling, another rotation.

The scalings are the singular values, and they arrive sorted largest first. That ordering is the useful part: it ranks the directions of the data by how much they matter, so keeping the first few and discarding the rest keeps most of the structure and very little of the noise.

Why this is on the ladder

Because high-dimensional data is almost never genuinely high-dimensional. A thousand-pixel image of a handwritten digit does not wander freely through a thousand dimensions; it lives near a much thinner surface inside that space. SVD is how you find the thin part.

This is also the clearest available demonstration that "most of the information lives in a few directions" is a fact about real data rather than a hope.

Do this

Load a greyscale image as a matrix. Take its SVD. Look at the singular values: they fall off fast, usually by orders of magnitude — a fall best read on rung 10's log axis.

Now reconstruct using only the largest k components, for k = 1, 5, 20, 50. Look at each. Somewhere around k = 50 the image is essentially the original at a fraction of the numbers.

Plot reconstruction error against k. Then compute how much of the total each prefix accounts for and find the k reaching ninety per cent.

Finally, look hard at what disappeared. It is not uniformly distributed: fine texture and sharp edges go first, broad shapes last. Say why in terms of what the early components represent.

Where people get stuck

Reading the compression as merely a trick for storage. The interesting claim is about the data: it says the matrix was close to low-rank all along, and rung 30's rank is exactly the notion being approximated here.

The other snag is forgetting to centre the data when using this for PCA. The uncentred version finds directions dominated by the mean rather than by the variation, which produces a confident and useless answer.

Reading