Singular value decomposition

This is the deepest, most universal, and most widely used theorem in all linear algebra applications. Absolutely any matrix admits this decomposition. Once you calculate it, you have access to almost all of its properties, from its range to its inverse, through its determinant and a complete interpretation of its associated linear transformation.
In a sense, this is why you've been learning linear algebra. In this introductory topic, you'll analyze this decomposition in detail, learn how to calculate it efficiently, and finally take a look at the first sample of its geometric implications. In the next topic, you'll see its power in action.

The best decomposition

For any $m \times n$ matrix $A$ , there exist orthogonal matrices $U$ and $V$ (of sizes $m$ and $n$, respectively), and a diagonal $m \times n$ matrix $\Sigma$ with non-negative entries, such that:
$$\begin{align*} A=U \Sigma V^T \end{align*}$$

The fact that the rectangular matrix $\Sigma$ is meant to be diagonal simply means that its $(i,j)$-entry is $0$ whenever $i \neq j$. This decomposition brings with it a bit of terminology that's worth knowing now.

Actually, these definitions give you a rough method to calculate the decomposition:

1. Compute $A \, A^T$ and $A^T \, A$.
2. Find the eigenvalues of both $A \, A^T$ and $A^T \, A$ (they share the same eigenvalues).
3. Calculate the non-negative roots of these eigenvalues. Then put them in the diagonal entries of a matrix $\Sigma$.
4. Compute the eigenvectors of $A \, A^T$ and scale them in order to have length $1$. Put them as the columns of $U$.
5. Repeat the last step for $A^T \, A$ building the matrix $V$.
6. Finally, $A=U \Sigma V^T$.

In the following section, you'll develop a much shorter algorithm.

Building the decomposition

The method from the previous section has a serious drawback: you have to build two matrices, $A \, A^T$ and $A^T \, A$, and then build a spectral decomposition for each one. This sounds like a lot of work. Let's take a closer look at the pieces of the decomposition in order to improve the algorithm.

It's customary to denote the singular values as $\sigma_1, \sigma_2, \dots, \sigma_n$ and to order them in non-increasing order $\sigma_1 \geq \sigma_2 \dots \geq \dots \sigma_{\min(m.n)}$. .

Since $\Sigma$ is diagonal, its rank is the number of nonzero rows it has, which is, therefore, the number of non-zero singular values of $A$. Well, if $r$ is the rank of $A$, then $r= rank(A) = rank(U \Sigma V^T) = rank(\Sigma)$, thus:

Thus, $\sigma_1 \geq \sigma_2 \dots \geq \dots \sigma_r >0$ and $\sigma_{r+1} = \dots= \sigma_{\min(m.n)} =0$. Let's analyze the pieces by expressing $U$ and $V$ in terms of its columns:

$$U = \left[\begin{array}{l|l|l|l} \mathbf{u}_1 & \mathbf{u}_2 & \cdots & \mathbf{u}_m \end{array}\right]$$

$$V=\left[\begin{array}{l|l|l|l} \mathbf{v}_1 & \mathbf{v}_2 & \cdots & \mathbf{v}_n \end{array}\right]$$The matrix equation $A=U \Sigma V^T$ implies that $A V=U \Sigma$. Take a closer look at the columns of these new matrices:

$$A V =\left[\begin{array}{l|l|l|l} A \mathbf{v}_1 & A \mathbf{v}_2 & \cdots & A \mathbf{v}_n \end{array}\right]$$$$U \Sigma = \left[\begin{array}{l|l|l|l|l|l|l} \sigma_1 \mathbf{u}_1 & \sigma_2 \mathbf{u}_2 & \cdots &\sigma_r \mathbf{u}_r & 0 & \cdots &0 \end{array}\right]$$

Since these two matrices are equal, their columns are equal too. This implies that the first $r$ columns of $U$ can be obtained by:
$$\mathbf{u}_j=\frac{1}{\sigma_j} A \mathbf{v}_j \quad \text { for all } \quad j \in \{1, 2, \dots, r\}$$Then the rest of the columns of $U$ can be calculated by extending the available ones so that they form an orthonormal basis. So, you have developed an easier method to get the decomposition:

Now, you should get your hands dirty with some examples.

A direct example

Consider the following rectangular matrix:

$$A= \begin{pmatrix} 1 & 1 & -1 \\ -1 & 1 & 1 \\ \end{pmatrix}$$The first step is computing a spectral decomposition for the positive definite matrix:

$$A^T A=\begin{pmatrix} 2 & 0 & -2 \\ 0 & 2 & 0 \\ -2 & 0 & 2 \end{pmatrix}$$Its eigenvalues are $4$, $2$ and $0$. This means the singular values of $A$ are their square roots, so $\sigma_1 = \sqrt{4} = 2$ and $\sigma_2 = \sqrt{2}$. This also implies that $rank(A)=2$ since there are only two positive singular values. Now, an orthonormal basis corresponding to the eigenvalues is:

$$\mathbf{v}_1= \frac{1}{\sqrt{2}} \begin{pmatrix} -1 \\ 0 \\ 1 \end{pmatrix} \qquad \mathbf{v}_2= \frac{1}{\sqrt{2}} \begin{pmatrix} 0 \\ \sqrt{2} \\ 0 \end{pmatrix} \qquad \mathbf{v}_3= \frac{1}{\sqrt{2}} \begin{pmatrix} 1 \\ 0 \\ 1 \end{pmatrix}$$Now put these vectors as the columns of the matrix $V$ and the singular values on the diagonal of the matrix $\Sigma$:

$$\Sigma= \begin{pmatrix} 2 & 0 & 0 \\ 0 & \sqrt{2} & 0 \end{pmatrix} \qquad V= \frac{1}{\sqrt{2}} \begin{pmatrix} -1 & 0 & 1 \\ 0 & \sqrt{2} & 0 \\ 1 & 0 & 1 \end{pmatrix}$$After that, the two columns of $U$ can be obtained via:

• $$u_1 = \frac{1}{\sigma_1} A \mathbf{v}_1 = \frac{1}{2} \begin{pmatrix} 1 & 1 & -1 \\ -1 & 1 & 1 \\ \end{pmatrix} \left[ \frac{1}{\sqrt{2}} \begin{pmatrix} -1 \\ 0 \\1 \end{pmatrix} \right] = \frac{1}{\sqrt{2}} \begin{pmatrix} -1 \\ 1\end{pmatrix}$$
• $$u_2 = \frac{1}{\sigma_2} A \mathbf{v}_2 = \frac{1}{\sqrt{2}} \begin{pmatrix} 1 & 1 & -1 \\ -1 & 1 & 1 \\ \end{pmatrix} \left[ \frac{1}{\sqrt{2}} \begin{pmatrix} 0 \\ \sqrt{2} \\0 \end{pmatrix} \right] = \frac{1}{\sqrt{2}} \begin{pmatrix} 1 \\ 1\end{pmatrix}$$

Hence:
$$U=\frac{1}{\sqrt{2}} \begin{pmatrix} -1 & 1 \\ 1 & 1 \\ \end{pmatrix}$$And that's it. The SVD decomposition of $A$ is complete. You should verify that $A=U \Sigma V^T$.

More steps

Let's see a more difficult decomposition. Take a square matrix:

$$A= \begin{pmatrix} 2 & 2 & -2 \\ -4 & -1 & 4 \\ -4 & 2 & 4 \\ \end{pmatrix}$$Start by computing the positive definite matrix:

$$A^T A=\begin{pmatrix} 36 & 0 & -36 \\ 0 & 9 & 0 \\ -36 & 0 & 36 \\ \end{pmatrix}$$Since its eigenvalues are $72$, $9$ and $0$, the singular values of $A$ are their square roots $\sigma_1 = 6 \sqrt{2}$ and $\sigma_2 = 3$. An orthonormal basis corresponding to these eigenvalues is:

$$\mathbf{v}_1= \frac{1}{\sqrt{2}} \begin{pmatrix} -1 \\ 0 \\ 1 \end{pmatrix} \qquad \mathbf{v}_2= \frac{1}{\sqrt{2}} \begin{pmatrix} 0 \\ \sqrt{2} \\ 0 \end{pmatrix} \qquad \mathbf{v}_3= \frac{1}{\sqrt{2}} \begin{pmatrix} 1 \\ 0 \\ 1 \end{pmatrix}$$Now you can build matrices $\Sigma$ and $V$:

$$\Sigma= \begin{pmatrix} 6 \sqrt{2} & 0 & 0 \\ 0 & 3 & 0 \\ 0 & 0 & 0 \end{pmatrix} \qquad V= \frac{1}{\sqrt{2}} \begin{pmatrix} -1& 0 &1 \\ 0 & \sqrt{2} & 0 \\ 1 & 0 &1\\ \end{pmatrix}$$But $A$ only has two singular values, so you can only compute the first two columns of $U$:

$$u_1 = \frac{1}{\sigma_1} A \mathbf{v}_1 = \frac{1}{6\sqrt{2}} \begin{pmatrix} 2 & 2 & -2 \\ -4 & -1 & 4 \\ -4 & 2 & 4 \\ \end{pmatrix}\left[ \frac{1}{\sqrt{2}} \begin{pmatrix} -1 \\ 0 \\1 \end{pmatrix} \right] = \frac{1}{3} \begin{pmatrix}-1 \\ 2 \\ 2 \end{pmatrix}$$$$u_2 = \frac{1}{\sigma_2} A \mathbf{v}_2 = \frac{1}{3} \begin{pmatrix} 2 & 2 & -2 \\ -4 & -1 & 4 \\ -4 & 2 & 4 \\ \end{pmatrix}\left[ \frac{1}{\sqrt{2}} \begin{pmatrix} 0 \\ \sqrt{2} \\ 0 \end{pmatrix}\right] = \frac{1}{3} \begin{pmatrix} 2 \\ -1 \\ 2 \end{pmatrix}$$You can find the last column of $U$ by extending $\{ \mathbf{u}_1, \mathbf{u}_2 \}$ to an orthonormal basis of $\mathbb{R}^3$, perhaps with the Gram-Schmidth process or with the cross product. This can lead you to the vector $\mathbf{u}_3= \frac{1}{3}(-2, -2,1) ^T$. Thus:

$$U = \frac{1}{3} \begin{pmatrix} -1& 2 &-2 \\ 2 & -1 & -2 \\ 2 & 2 &1\\ \end{pmatrix}$$Again, try to check that $A=U \Sigma V^T$.

Geometry

You can easily decompose the geometric behavior of any matrix $A$ in simple steps. First, notice that the linear operator of $A$ is given by the following composition of simpler pieces:$$L_A=L_U \circ L_D \circ L_{V^T}$$So, the behavior of $L_A$ is described by three stages:

• As $V^T$ is orthogonal, the action of $L_{V^T}$ is just a rotation and/or reflection of $\mathbb{R}^m$,
• after that, the fact that $D$ is diagonal implies that $L_D$ only stretches and then embeds $\mathbb{R}^m$ in $\mathbb{R}^n$,
• finally $L_{U}$ is a rotation and/or reflection of $\mathbb{R}^n$,.

Furthermore, the two radii of the ellipse are exactly the singular values σ 1 and σ 2 of the matrix,

Conclusion

Take a $m \times n$ matrix $A$ with a rank equal to $r$.

• There are orthogonal matrices $U$ and $V$ (of sizes $m$ and $n$, respectively), and a diagonal $m \times n$ matrix $\Sigma$ with non-negative entries, such that $A=U \Sigma V^T$.

• The diagonal entries of $\Sigma$ are the singular values of $A$.

• There are exactly $r$ non-zero singular values which are in decreasing order $\sigma_1 \geq \sigma_2 \dots \geq \dots \sigma_r >0$.

• In order to compute the decomposition, you first calculate a spectral decomposition for $A^T A= VDV^T$ and then the first $r$ columns of $U$ are given by $\mathbf{u}_j=\frac{1}{\sigma_j} A \mathbf{v}_j$.

• The geometry of the linear transformation associated with $A$ is the composition of an isometry, a stretching, and other isometry.