What a map does to a circle

Everything so far in this ladder has depended on a map having invariant directions, and not every map has any. A quarter turn leaves nothing pointing where it started. A map from three dimensions to two has no eigenvector because $Av = \lambda v$ compares arrows living in different spaces and does not even parse.

So the eigen-idea, powerful as it is, applies to a restricted class of maps and fails on the rest with nothing to offer. What follows is what to reach for instead, and it applies to every linear map without exception.

The picture is the theorem #

A linear map takes the unit circle to an ellipse. That much is easy to believe and easy to check: the circle is the set of unit arrows, the map is linear, and the image of a circle under a linear map is an ellipse — possibly a degenerate one, flattened to a segment, when the map throws a dimension away.

The theorem is the extra clause. There is a pair of perpendicular directions in the circle whose images are also perpendicular, and those images are the axes of the ellipse. Every map has such a pair. The map does not have to be symmetric, or square, or invertible, or anything else.

The two directions in the circle are the right singular vectors, their images divided by their lengths are the left singular vectors, and the lengths themselves are the singular values, always written $\sigma_1 \geq \sigma_2 \geq \cdots \geq 0$. In matrix form the statement is

$$A = U\Sigma V^{\mathsf{T}},$$

read right to left: rotate the circle so the special directions land on the axes, stretch the axes by $\sigma_1$ and $\sigma_2$, rotate the result to where it belongs. Every linear map is a rotation, then a stretch along perpendicular axes, then another rotation. There is nothing else a linear map can do.

Where the perpendicular pair comes from #

The proof is a short one and it borrows the whole of the previous rung.

Ask what happens to lengths. The squared length of $Av$ is $Av \cdot Av$, which by moving the matrix across the dot product is $v \cdot (A^{\mathsf{T}}A) v$ — a quadratic form, in the matrix $A^{\mathsf{T}}A$. And $A^{\mathsf{T}}A$ is symmetric, always, whatever $A$ is: its $(i,j)$ entry is the dot product of the $i$-th and $j$-th columns of $A$, and a dot product does not care about order.

So the spectral theorem applies to it, unconditionally, and hands over perpendicular eigenvectors $v_1, v_2$ with real eigenvalues. Those eigenvalues cannot be negative, since $v\cdot(A^{\mathsf{T}}A)v = |Av|^2$ is a squared length; call them $\sigma_1^2$ and $\sigma_2^2$. Then $|Av_i| = \sigma_i$, which names the singular values, and

$$Av_1 \cdot Av_2 = v_1 \cdot (A^{\mathsf{T}}A)v_2 = \sigma_2^2 (v_1 \cdot v_2) = 0,$$

which says the images are perpendicular too. That is the theorem, and every step of it was already available.

The move is worth naming because it is the standard one for getting a symmetric matrix out of a situation that has none: do not study the map, study what it does to lengths. Lengths are quadratic, quadratic means symmetric, and symmetric means the spectral theorem.

What the numbers measure #

The two singular values say most of what anyone wants to know about a map.

Their product is the area factor. $\sigma_1\sigma_2 = |\det A|$, since the ellipse has area $\pi\sigma_1\sigma_2$ and the circle has area $\pi$. The absolute value is the only loss: the singular values cannot see whether the map reversed orientation, because a reflected ellipse is the same ellipse.

The largest is the most the map can stretch anything. $\sigma_1 = \max_{|v| = 1}|Av|$, which is the definition of the operator norm — the answer to how much can this map amplify? And the smallest is the least it can stretch anything, which answers how close is this map to crushing something?

The figure measures both rather than computing them. It samples the circle at 721 angles, applies the map, and takes the longest and shortest images found, then compares those with the values obtained from $A^{\mathsf{T}}A$. Two routes sharing no arithmetic, and the assertion is that they agree to four decimal places.

These two are worth holding together, because they answer the two halves of the same practical worry. The largest says how badly a small error in the input can be amplified; the smallest says how badly a small error in the output misleads about the input. Neither alone is enough, and the second is the one people forget — a map can be perfectly stable to compute forwards and hopeless to invert.

Their ratio is the condition number. $\sigma_1/\sigma_2$ says how eccentric the ellipse is, and it is the factor by which the map can magnify a relative error. A map with a large ratio takes a nearly-round set of possible inputs to a long thin set of possible outputs, so solving $Ax = b$ with an uncertain $b$ gives an $x$ uncertain by that factor. It is the single number that decides whether a linear system can be solved usefully, and it is a property of the ellipse rather than of any algorithm.

Compared with the eigenvalues #

The two decompositions are easy to confuse and they answer different questions.

Eigenvalues describe what a map does when it is applied repeatedly, because that is where the invariant directions matter: iterating multiplies each eigen-component by its own eigenvalue, so the eigenvalues govern growth over time. Singular values describe what a map does once, to lengths.

The two agree only in a special case. For a symmetric matrix the singular values are the absolute values of the eigenvalues and the singular vectors are the eigenvectors — which is the spectral theorem again, wearing the other name. For everything else they can be wildly different. A shear has both eigenvalues equal to 1, so it never grows anything under iteration in the eigen-sense; its singular values are about 1.6 and 0.6, so it certainly stretches things once.

The example that makes the difference vivid: a matrix can have every eigenvalue smaller than 1 in size — so that its powers eventually go to zero — while its largest singular value is enormous, so that the first few powers grow by orders of magnitude before turning round. Eventual decay and immediate growth are not in conflict; they are answers to different questions, and only the singular values are answering the second.

The other order, and what it is worth #

The same information can be regrouped. Since $U$ and $V$ are rotations, writing $A = U\Sigma V^{\mathsf{T}} = (UV^{\mathsf{T}})(V\Sigma V^{\mathsf{T}})$ splits the map into a rotation followed by a symmetric stretch, or the other way round by grouping the other way. That is the polar decomposition, and it is the matrix version of writing a complex number as a modulus times a direction: a size and a turn.

It answers a question the singular values alone do not. Given a map that is supposed to be a rotation but has drifted — measurement error, accumulated rounding, a matrix reconstructed from noisy data — the nearest actual rotation to it is the rotation factor of its polar decomposition. Setting every singular value to 1 and leaving the two frames alone is the closest rotation, in exactly the same least-squares sense in which truncating the sum gives the closest low-rank matrix.

The two facts are the same fact seen twice: the singular values are the only place a map keeps its magnitudes, so any question of the form what is the nearest map with such-and-such magnitudes is answered by changing them and touching nothing else.

Maps that are not square, and maps that lose a dimension #

Nothing in the construction assumed a square matrix. For an $m \times n$ map, $A^{\mathsf{T}}A$ is $n \times n$ and symmetric, the argument runs unchanged, and the result is $\min(m, n)$ singular values with perpendicular frames in both spaces.

That is the reason this decomposition rather than the eigen one is the working tool of applied linear algebra. Data matrices are not square. A table with one row per person and one column per measurement is a map from the space of measurements to the space of people, and nothing about it invites the question which arrow does this leave alone? — the two spaces are not the same space, and the question does not parse. A matrix of ratings, of measurements, of pixel intensities, of word counts has one dimension for the rows and another for the columns, and asking for its eigenvectors is asking a question with no meaning.

When a singular value is zero, the map sends its direction to the origin: the ellipse has collapsed in that direction and the map has thrown a dimension away, which is what a kernel is. So the number of non-zero singular values is the rank, which makes rank a measured quantity rather than a combinatorial one — and that turns out to matter, because a matrix built from real measurements is almost never exactly rank-deficient and is frequently nearly so. Counting exact zeros gives the wrong answer; looking at where the singular values fall off a cliff gives the right one.

The approximation that made it famous #

Here is the property that took the decomposition out of textbooks and into everything.

Writing the map as a sum of its pieces, $A = \sigma_1 u_1 v_1^{\mathsf{T}} + \sigma_2 u_2 v_2^{\mathsf{T}} + \cdots$, each term is a rank-one matrix and the terms are ordered by size. Keeping the first $k$ and discarding the rest gives the best possible rank-$k$ approximation to $A$ — best in the sense of least total squared error, and best also in the sense of smallest largest error, which is unusual: two different notions of “closest” picking out the same answer.

The proof is not short and the statement is worth having without it. It says that the question what is the simplest map that is nearly this one? has an answer, that the answer is unique, and that computing it requires no search. Nothing in the eigen-decomposition does anything of the kind.

There is a matching statement about how much is kept. The total squared size of a matrix, entry by entry, is the sum of the squares of its singular values — a fact worth pausing over, since the left-hand side is written in one coordinate system and the right-hand side is written in none. So the fraction of the matrix a rank-$k$ truncation retains is a ratio the singular values state directly, and it can be read off before anything is discarded. That is why the spectrum is plotted first and the cut is chosen afterwards.

The consequences run a long way. Compressing an image by keeping its largest singular values; finding the few underlying factors behind many measured variables; fitting the flat that lies closest to a cloud of points, which is the same computation on the centred data; recovering a signal from a noisy matrix by discarding the directions whose singular values look like noise. In each case the discarded part is precisely the part the ellipse is thinnest in.

Two directions worth separating #

It is easy to come away with the impression that the singular value decomposition is a better version of the eigen one, and it is not — it is a different one, and the difference is worth stating in a sentence each.

An eigenvector is a direction the map does not turn. That is a statement about the map alone, and it survives any change of coordinates: if $A$ and $B$ describe one map against two grids, they have the same eigenvalues.

A singular value is a length. Lengths need a notion of length, which is extra structure — a dot product — and the decomposition is a statement about the map and that structure together. Change the grid to a skewed one and the singular values change, while the eigenvalues do not.

So the eigen-decomposition is the more intrinsic object and the singular one is the more useful, which is not the usual trade. It is useful precisely because it uses more: having a notion of length is what makes “nearest”, “largest”, “best approximation” and “worst case” mean anything, and every application in the previous section is one of those words.

What the picture cannot show #

The drawing is of a map from the plane to the plane, and the two most important applications are not.

For a map between spaces of different dimensions the picture would need two pages of different sizes, and the interesting phenomenon — a circle in one space going to an ellipse in a subspace of the other — cannot be drawn side by side without the eye reading the subspace as the whole thing.

And a rank-one approximation to a two-by-two matrix is a flattening, which looks like destruction rather than like compression. The reason discarding small singular values is a good idea only becomes visible when there are many of them and the spectrum falls away sharply, and a figure with two of them cannot show a spectrum falling away.

The second omission is more serious than it sounds. A two-by-two example makes the decomposition look like a curiosity about ellipses. What it is, in practice, is the observation that a large matrix of measurements is usually almost a small one — and that is a statement about the world rather than about linear algebra, which no picture of a circle can make.

The ladder from here #

Rungs above: the polar decomposition, which is the same theorem regrouped as a stretch followed by a rotation. The pseudoinverse, which is what to solve a system with when the matrix has no inverse. The relation between the singular values of a matrix and the eigenvalues of the symmetric matrix built from it. The algorithms that compute the decomposition, none of which forms $A^{\mathsf{T}}A$, because squaring a matrix squares its condition number and throws away half the precision. And the interlacing theorems, which say how much a singular value can move when a matrix is perturbed — the reason a decomposition computed from noisy data means anything at all.