Linear algebra Ā· Part 5 of 5
Singular value decomposition
Learn how the singular value decomposition breaks any matrix into rotation, stretch, rotation, and why it works for every matrix.
Linear algebra11 min read
Eigenvalue decomposition is wonderful, but it only exists for square matrices, and even then only for some of them. Yet in applications ā data compression, image processing, least squares, principal component analysis ā we constantly need a similar "best directions" description of rectangular matrices: a matrix that maps a photo of size , or a dataset with features and samples.
The singular value decomposition (SVD) fills this gap. It says that every matrix, square or rectangular, can be written as a rotation, followed by a stretch along perpendicular axes, followed by another rotation. The stretch factors are called the singular values, and they generalize the idea of eigenvalues to arbitrary matrices. In this lesson you will learn what the SVD is, how to compute it for small matrices, and what it tells you geometrically.
The statement of the SVD
For any matrix , there exist an orthogonal matrix , an diagonal matrix with nonnegative entries, and an orthogonal matrix such that
Orthogonal means and : these matrices preserve lengths and angles, so geometrically they are rotations (possibly with reflections). The only matrix that actually stretches space is , whose diagonal entries are the singular values of .
The picture: rotates the input so that the important directions line up with the coordinate axes, stretches each axis by its singular value, and rotates the result into its final position. The columns of are the input directions that get stretched; the columns of are the corresponding output directions.
A useful consequence right away: the largest singular value is the maximum factor by which can lengthen a vector, and the operator norm of is exactly .
Where singular values come from
How do we find the pieces? The key identity is
which is an eigenvalue decomposition of the square symmetric matrix . So:
- Compute . It is symmetric, so it has real nonnegative eigenvalues and orthogonal eigenvectors.
- The singular values are , arranged in decreasing order.
- The eigenvectors of , normalized, are the columns of .
- For each nonzero , the column gives the columns of .
- Check .
Why is the right definition? Because if is a unit eigenvector of with eigenvalue , then
so : the singular value measures exactly how much stretches that direction. This also shows the eigenvalues of are never negative, since they equal squared lengths.
Worked example: a full SVD of a 2x2 matrix
Let's compute the SVD of a diagonal matrix with a negative entry, to see where signs go. The method is the five-step recipe from the previous section; the only new wrinkle is that the negative sign of must be absorbed into or , never into .
Example 1. SVD of a diagonal matrix with a negative entry Find an SVD of .
Step 1: form .
Step 2: eigenvalues and singular values. The eigenvalues of are and , so the singular values are and , in decreasing order.
Step 3: columns of . The eigenvectors of the diagonal matrix are and , so .
Step 4: columns of .
So
Check: . The negative sign of was absorbed into as a reflection ā singular values themselves are always nonnegative.
Worked example: a rectangular matrix
Now a genuinely rectangular case, where is bigger than the number of singular values and we must complete it with extra orthonormal columns.
Example 2. SVD of a 3x2 matrix Find an SVD of , a matrix.
Step 1: , so , , and .
Step 2: and . These are unit vectors in ; to make a full orthogonal matrix we add a third orthonormal column orthogonal to both, e.g. .
Step 3: Assemble
and indeed . The zero row of reflects that maps into only a 2-dimensional slice of .
A quick verification habit: for any claimed pieces, check two things ā that for each , and that the columns of and of are orthonormal. If both hold, the decomposition is correct.
Worked example: SVD of a non-diagonal matrix
Finally, a case where is not the identity and the singular values are irrational. Everything follows the same recipe; the eigenvector computation is the only part that takes real work.
Example 3. SVD of a shear matrix Find the singular values of and the first input direction .
Step 1:
Step 2: Solve , giving . So
(Here we used , which you can verify by squaring.) Note : the product of singular values equals for square matrices.
Step 3: Eigenvectors of for satisfy , i.e. . Normalizing gives a unit vector along ; similarly along . These two directions are perpendicular, as guaranteed, and they are the input directions that stretches by and .
Step 4: Then completes , and . The geometric story: the shear takes the direction (roughly from the -axis) and stretches it the most, by the golden ratio .
Why the SVD matters
Three facts make the SVD the workhorse of applied linear algebra.
Rank from singular values. The rank of is the number of nonzero singular values. If , then really acts like an -dimensional map, and the SVD exhibits this explicitly.
Best low-rank approximation. If you keep only the largest singular values and zero out the rest, you get the matrix of rank that is closest to in both the usual norm and the Frobenius norm. This is the mathematics behind image compression: store a few singular values and vector pairs instead of the whole matrix, and the picture is almost unchanged.
Pseudoinverse. The SVD gives a clean inverse-like object even for singular or rectangular matrices: replace each nonzero in by , transpose the result, and you get the MooreāPenrose pseudoinverse , which solves least-squares problems in one formula.
A compact way to summarize a matrix: its singular values. Two matrices with the same singular values differ only by rotations before and after ā they stretch space in exactly the same way.
Common mistakes
- Assuming singular values can be negative: they are defined as square roots of eigenvalues of , so they are always ; negative signs live in the columns of or instead.
- Computing eigenvalues of instead of : for a rectangular or non-symmetric these are unrelated; the singular values come from (or equivalently ).
- Forgetting to sort the singular values in decreasing order: the decomposition is only unique up to ordering, but the convention must be matched by the ordering of the columns of and .
- Forgetting to normalize the eigenvectors of : the columns of must be unit vectors, otherwise will not absorb the correct stretch factors.
- Thinking the SVD exists only for square matrices: it exists for every matrix, with being , being , and being .
Practice
- Let . Compute , and give the largest singular value of (the other singular value is ).
- Find the largest singular value of (the other singular value is , so has rank ).
- Let with singular values , , , . Verify the relation by computing both sides.
- The matrix has , whose larger eigenvalue is . Find the largest singular value of , i.e. , written in the form with integers .
- Using the SVD with , , , compute the matrix and state its rank.
Answers
- has larger eigenvalue , so .
- has eigenvalues and , so the largest singular value is .
- Both sides equal , so holds.
- , since squaring gives .
- , and its rank is since both singular values are nonzero.
Next, in Probability basics, we leave matrices behind and start building the language of chance, starting with sample spaces and events.