Loading editor...

23. SVD

A symmetric matrix can be decomposed as where the columns of are its unit eigenvectors (all perpendicular to each other) and is a diagonal matrix of its eigenvalues. If is also positive semi-definite, the diagonal values of are all non-negative.

If you are in a field related to machine learning, this is the one thing you need to understand and take away from linear algebra in my opinion. Singular Value Decomposition (SVD) is a decomposition that works for a matrix of any shape. The inspiration of SVD comes from a simple question:

Can a matrix map a set of orthogonal vectors to a set of orthogonal vectors?

In this chapter, we will investigate this question, first for square matrices and then for matrices of any shape.

Here is the picture to keep in mind. Draw , shown in orange. Now draw : they have been rotated and their lengths have changed, but they remain perpendicular to each other. We want to know which matrices act like this.

23.1 Let's understand the question first

23.1.1 Input

Let's start out with understanding what the input is. The input is a set of perpendicular unit vectors. In other words, the input is an -by- matrix where each column is a unit vector and any pair of two vectors is perpendicular:

  • for all
  • for all

Note that since is a matrix whose columns are unit vectors that are all perpendicular to each other, we have .

23.1.2 Output

We wish the output to also be a set of vectors that are all perpendicular to each other. Now, in the most general case, the norms of these vectors can be anything. Let the norm of the first output vector be , the norm of the second output vector be and so on. To be more precise:

  • for all
  • for all

Note that we can write each vector as where is the norm of and is a unit vector. Using this, we can rewrite as:

  • where is a matrix of perpendicular unit vectors, so just like it satisfies
  • and is a diagonal matrix.

For the picture above, the output pair is the product of a rotation and a diagonal scaling: . The left matrix holds the unit vectors pointing in the directions of the outputs, and the diagonal matrix scales them.

23.2 The complete equation

Now we would like to find a matrix that maps the column vectors of to the column vectors of . In other words, we want to find such that:

Multiplying both sides by on the right and remembering that gives us:

Thus, if a matrix maps a set of perpendicular unit vectors to a set of perpendicular vectors given by (you can interpret it as: a set of column vectors whose norms are the diagonal values of and whose directions are the unit column vectors of ), it can be represented as . This decomposition of the matrix is called its Singular Value Decomposition (or SVD).

Thus, we can re-frame the question as:

Given an -by- matrix , find -by- matrices such that where and have unit column vectors which are perpendicular to each other, i.e. , and is a diagonal matrix.

23.3 Uncovering the solution

Note that we already saw a similar decomposition earlier for a symmetric matrix : where the columns of are unit eigenvectors of and the diagonal values of the diagonal matrix are the corresponding eigenvalues. In other words, for a symmetric matrix , we have .

We will use the following insight to find the SVD for a general -by- matrix :

It is easy to calculate the SVD of a symmetric matrix : one just needs to calculate the eigenvectors and eigenvalues of .

23.3.1 Finding the matrices

Given a matrix , we note that:

since . Similarly:

Note that the matrices and are -by- symmetric positive semi-definite. Thus they have non-negative eigenvalues and eigenvectors that are perpendicular to each other. Some more observations we can make here:

  • is the eigendecomposition of the symmetric PSD matrix . The columns of are the unit eigenvectors of .
  • is the eigendecomposition of the symmetric PSD matrix . The columns of are the unit eigenvectors of .
  • Both matrices and share the same set of non-negative eigenvalues. These eigenvalues are given by the diagonal entries of the matrix .

Why do and have the same eigenvalues?

This is a special case of a general fact: for any two square matrices and , the products and have the same eigenvalues. Indeed, if with , then multiplying by on the left gives , so is also an eigenvalue of (with eigenvector ). Apply this with and .

23.3.2 Complete solution

Thus, given an -by- matrix , the SVD of is given by where:

  • the columns of the -by- matrix are the unit eigenvectors of
  • the columns of the -by- matrix are the unit eigenvectors of
  • is an -by- diagonal matrix whose values are the square roots of the eigenvalues of the symmetric PSD matrix (or ).

23.4 Interpreting the solution

Now let's try to understand what happens when the matrix is multiplied by a vector . We can see that . Thus we can interpret the matrix-vector product as a 3-step process:

  1. : since and are orthonormal matrices (because and ), the vector is first rotated or reflected by .
  2. : since is a diagonal matrix whose entries are all non-negative, it stretches the dimensions of the vector. To be more precise, the -th element of the vector gets multiplied by the -th diagonal element of .
  3. : since and are orthonormal matrices (because and ), the vector is rotated or reflected by .

This is the interpretation that SVD provides:

A matrix first rotates or reflects a vector , scales (or stretches) its dimensions, and rotates or reflects it again.

These transformations (rotations or reflections) are defined by the eigenvectors of the matrices and , and the scaling values are the square roots of the (common) eigenvalues of both these matrices.

23.5 Visualizing SVD

Let's calculate the SVD of . The steps of the calculation look like:

  • Calculate and .
  • Calculate the eigenvalues of (or ): the eigenvalues are and .
  • Create a diagonal matrix whose diagonal values are the square roots of the above eigenvalues:
  • Calculate the unit eigenvectors of :
  • Calculate the unit eigenvectors of :

This gives us .

First let's see how this matrix transforms points on a circle.

Draw . The longest and shortest output vectors have lengths and , the diagonal values of , and they point along the columns of .

Now let's and transform the circle into this ellipse step by step.

Now let's watch the 3-step process act on a single vector.

  • Start with a
  • Transform by : it is a
  • Transform by : it the x and y-axes

This step explains how the singular values are connected to the lengths of the longest and shortest vectors. This is the only transform in SVD that changes the lengths of the vectors. It does so simply by scaling the axes. A vector along axis i is scaled by length .

  • Transform by : another

23.6 SVD of non-square matrices

Now let's say you are given an -by- matrix . In other words, the matrix has rows and columns.

  • This matrix takes as input a -dimensional vector. In other words, the input space of this matrix is -dimensional.
  • This matrix gives as output an -dimensional vector. In other words, the output space of this matrix is -dimensional.

In this case, the input space can contain at most vectors that are all perpendicular to each other. Similarly the output space can contain at most vectors that are all perpendicular to each other. Then the question that we asked initially for square matrices takes the form:

Can an -by- matrix map a set of unit vectors (each vector being -dimensional) perpendicular to each other to a set of vectors (each vector being -dimensional) which also remain perpendicular to each other?

There are two scenarios here: and . Let's address the above question in each of the scenarios.

23.6.1 When

Let's assume and . Such a matrix looks like . Note that this matrix has rank at most . Thus its outputs can never span all of the 3-dimensional space.

We can show this at-most 2-dimensional output like so:

Note how the third column of the left matrix is always ignored because the bottom row of the right matrix is all zeros. Let's name the left matrix . Again, is a matrix whose columns are unit vectors all perpendicular to each other. In other words, .

The input vectors to are the same as before: a -by- matrix such that . This gives us:

  • Just like the previous case, we have and where .
  • The calculation of the matrices is the same as in the case of square matrices.

So the only difference compared to the case of square matrices is that when , rows full of zeros are added to the bottom of the diagonal matrix .

23.6.2 When

Let's assume and . Such a matrix looks like . Note that this matrix also has rank at most . In this case the input is unit vectors perpendicular to each other, each vector being 3-dimensional. The output is vectors still perpendicular to each other, each vector being 2-dimensional. But how is this possible?

This is possible only if the third output vector is the zero vector. In other words, the output matrix looks like:

where the vectors and are perpendicular to each other. This makes all three output vectors perpendicular to each other, because every vector is perpendicular to the vector of zeros: .

We can rewrite the output matrix as:

where the matrix is an -by- matrix such that . Our input matrix is a -by- matrix such that . This gives us the SVD:

  • Just like the previous case, we have and where .
  • The calculation of the matrices is the same as in the case of square matrices.

So the only difference compared to the case of square matrices is that when , columns full of zeros are added to the right of the diagonal matrix .

SVD has applications in wide areas of mathematics and engineering. One of the more popular use cases is dimension reduction. Let's look into it next.

← 22. PSD matrices · 24. Dimension reduction →