Skip to content
Tutorials Center
My learning

Topics

Lesson 45 of 62 ยท Eigenvalues and Decompositions

Singular Value Decomposition

Understand the SVD A = U Sigma V^T: its geometry, np.linalg.svd shapes, how singular values reveal rank and condition number, and the pseudoinverse.

Eigenvalues are wonderful but picky. They need a square matrix, and even then the matrix may be defective or have complex eigenvalues. The singular value decomposition (SVD) has no such conditions. Every matrix, of any shape, has one. It is often called the most useful factorization in all of applied mathematics, and it sits underneath PCA, recommendation systems, data compression, least squares and noise filtering.

The idea is simple to state: every linear map is a rotation, then a stretch along coordinate axes, then another rotation. In symbols, A = U Sigma V^T. In this lesson you will read that statement geometrically, see what np.linalg.svd returns, and use the singular values to measure rank and conditioning and to build the pseudoinverse.

A = U Sigma V^T in words

V^T Rotate the input to the right axes.
Sigma Stretch each axis by a singular value.
U Rotate into the output space.

Any matrix, any shape, always exists.

1 / 2

The factorization

Let A be an m x n matrix. Its SVD is

A = U Sigma V^T

  • U is an m x m orthogonal matrix. Its columns, the left singular vectors, are perpendicular unit vectors in the output space.
  • V is an n x n orthogonal matrix. Its columns, the right singular vectors, are perpendicular unit vectors in the input space.
  • Sigma is an m x n matrix that is zero except on its diagonal, which holds the singular values s1 >= s2 >= ... >= 0.

The link to eigenvalues is useful to remember. Since A^T A = V Sigma^T Sigma V^T, the right singular vectors are the eigenvectors of the symmetric matrix A^T A (see symmetric matrices), and the singular values are the square roots of its eigenvalues. Likewise the columns of U are the eigenvectors of A A^T. So the SVD is the spectral theorem applied to both A^T A and A A^T at once, and that is why it exists for every matrix.

What np.linalg.svd returns

np.linalg.svd(A) returns three things: U, a 1-D array S of singular values (not a matrix), and Vt, which is already V^T. Two shapes are possible:

  • Full (the default): U is m x m and Vt is n x n. Extra columns of U just complete an orthonormal basis.
  • Compact, with full_matrices=False: U is m x k and Vt is k x n, where k = min(m, n). This is the one to use in most code, and it is what the later lessons use.

To rebuild A you must turn S into a diagonal matrix (np.diag(S)) or scale the columns of U directly with U * S.

Python Shapes, rebuilding and the eigenvalue link

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The geometry: circle to ellipse

Feed the unit circle through a 2 x 2 matrix and you get an ellipse. The SVD tells you exactly which ellipse. The right singular vectors in V are the input directions that end up along the ellipse's axes, the singular values are the lengths of the semi-axes, and the left singular vectors in U are the directions of those axes in the output. In particular A v1 = s1 u1: the first right singular vector is the unit direction that A stretches the most, by the factor s1.

Two consequences follow. The largest singular value equals the maximum of ||A x|| over unit vectors x (this is the matrix 2-norm, np.linalg.norm(A, 2)), and the smallest is the minimum. And the determinant's size is |det A| = s1 * s2, the area scale factor of the transformation.

Python Watching a circle become an ellipse

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Rank, null space and condition number

Each nonzero singular value is one genuine direction in which the matrix does something. A zero singular value means a direction that is squashed to nothing. That gives the cleanest definition of rank:

  • Rank = the number of nonzero singular values. This is exactly how np.linalg.matrix_rank works, with a tolerance instead of exact zero (see Rank).
  • The right singular vectors for zero singular values span the null space, and the left singular vectors for nonzero ones span the column space (Column Space and Null Space).
  • The condition number is s_max / s_min. It measures how much a linear system can magnify small errors in the data. A huge condition number means the matrix is nearly singular. np.linalg.cond(A) computes it from the SVD.
Python Reading rank and conditioning from S

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The null vector is proportional to [1, 1, -1], which is exactly the relation "column 1 + column 2 - column 3 = 0" that we built in. The SVD found the dependency without being told. The second part shows conditioning getting worse as two columns become nearly parallel, a theme the numerical pitfalls lesson returns to.

The pseudoinverse

Only square matrices with full rank have an inverse. The SVD gives something almost as good for every matrix: the Moore-Penrose pseudoinverse A+. Invert each nonzero singular value, leave the zeros as zeros, and swap the roles of U and V:

A+ = V Sigma+ U^T

When A is square and invertible, A+ is the ordinary inverse. For a tall matrix with independent columns it gives the least-squares solution x = A+ b, the same answer as the normal equations (Least Squares). For a system with infinitely many solutions it picks the one with the smallest length. NumPy's np.linalg.pinv does all this, treating singular values below a cutoff as zero.

Python Building the pseudoinverse from the SVD

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

For a rank-deficient matrix, never invert the zero singular values: that divides by zero. np.linalg.pinv skips singular values below a tolerance, and you should do the same when writing the formula by hand (invert S[i] only if it is above a cutoff).

A word on signs and uniqueness

Singular values are unique, but the singular vectors are not. You can flip the sign of a column of U together with the matching row of Vt and still have a valid decomposition, and when two singular values are equal there is a whole family of valid vectors. Two different libraries (or two versions of one library) may therefore return vectors that differ in sign. Compare quantities that do not depend on that choice, such as S, products like U @ diag(S) @ Vt, or projections, rather than raw vectors.

You now have all the ingredients for the application that made the SVD famous, throwing away the unimportant parts of a matrix. That is the next lesson: Low-Rank Approximation and Image Compression.

Check your understanding

Quick check ยท 5 questions

of 5 answered You scored / 5 ยท perfect!

  1. 1. What does np.linalg.svd(A) return as its second value?

    S is a plain 1-D array sorted from largest to smallest. Use np.diag(S) or U * S when you need to rebuild A.
  2. 2. A 5 x 3 matrix has singular values 4.0, 1.5 and 0.0. What is its rank?

    Rank is the number of nonzero singular values, here two. The zero value marks a direction the matrix squashes to nothing.
  3. 3. How is the condition number of a matrix computed from its singular values?

    cond(A) = s_max / s_min. A large ratio means tiny relative changes in the input can cause large changes in the solution of Ax = b.
  4. 4. What does the pseudoinverse give for a tall system Ax = b with independent columns?

    x = A+ b minimizes ||Ax - b||. When there is an exact solution it returns it; when there are many solutions it returns the shortest.
  5. 5. Two libraries give the same S but U and Vt with some flipped signs. What is going on?

    Flipping a column of U together with the matching row of Vt gives another valid SVD, so compare invariant quantities.

Summary

  • Every matrix has an SVD A = U Sigma V^T: orthogonal U and V, and non-negative singular values in descending order.
  • np.linalg.svd(A, full_matrices=False) returns U, a 1-D S and Vt; the singular values are the square roots of the eigenvalues of A^T A.
  • Geometrically the matrix rotates, stretches by S and rotates again, mapping the unit circle to an ellipse whose semi-axes are the singular values.
  • Rank is the number of nonzero singular values; the condition number is s_max / s_min.
  • The pseudoinverse A+ = V Sigma+ U^T solves least-squares problems and picks the shortest solution when there are many.
  • Singular vectors are unique only up to sign (and rotation within equal singular values), so compare invariants.

Next, learn how to keep only the biggest singular values in Low-Rank Approximation and Image Compression.