Singular Values

In a previous post, we have seen the effect of multiplying a matrix with its eigenvectors. The vector does not change in direction, merely shrinks/stretches by an amount proportional to the corresponding eigenvalue.

I reproduce the before and after plots below for three matrices $\mathbf{A}$, $\mathbf{B}$, and $\mathbf{C}$.

There is one subtle difference between $\mathbf{B}$, $\mathbf{C}$, and $\mathbf{A}$. Take $\mathbf{B}$ for example, the length of $\mathbf{B}{\mathbf{u}}_1$ is the maximum of $\Vert \mathbf{B}\mathbf{x}\Vert$ over all unit vectors $\mathbf{x}$. And the length of $\mathbf{B}{\mathbf{u}}_2$ is the maximum of $\Vert \mathbf{B}\mathbf{x}\Vert$ over all unit vectors $\mathbf{x}$ that are perpendicular to ${\mathbf{u}}_1$. The same pattern applies to $\mathbf{C}$ as well. However, $\mathbf{A}{\mathbf{u}}_1$ is certainly NOT the maximum of $\Vert \mathbf{A}\mathbf{x}\Vert$ over all unit vectors $\mathbf{x}$.

As always, there is no coincidence in mathematics. Nor is this one. For a symmetric matrix $\mathbf{M}$, $\mathbf{M}{\mathbf{u}}_i$ returns the maximum of $\Vert \mathbf{M}\mathbf{x}\Vert$ over all unit vectors $\mathbf{x}$ that are perpendicular to the first $i-1$ eigenvectors of $\mathbf{M}$. The question remains then: among all unit vectors $\mathbf{x}$, which one maximizes $\Vert \mathbf{A}\mathbf{x}\Vert$ when $\mathbf{A}$ is not necessarily symmetric?

Let’s digress here for a moment and consider, not $\mathbf{A}$, but ${\mathbf{A}}^{\mathrm{\top }}\mathbf{A}$. Given that the transpose of a product is the product of the transpose in the reverse order, we have

$$({\mathbf{A}}^{\mathrm{\top }}\mathbf{A}{)}^{\mathrm{\top }}={\mathbf{A}}^{\mathrm{\top }}({\mathbf{A}}^{\mathrm{\top }}{)}^{\mathrm{\top }}={\mathbf{A}}^{\mathrm{\top }}\mathbf{A}$$

In other words, ${\mathbf{A}}^{\mathrm{\top }}\mathbf{A}$ is equal to its transpose, and therefore is a symmetric matrix. From previous posts, we know that a symmetric matrix such as ${\mathbf{A}}^{\mathrm{\top }}\mathbf{A}$ has $n$ real eigenvalues and $n$ linearly independent and orthogonal eigenvectors.

Next, let’s calculate the eigenvalues and eigenvectors of ${\mathbf{A}}^{\mathrm{\top }}\mathbf{A}$.

Let’s label these eigenvectors as ${\mathbf{v}}_1$ and ${\mathbf{v}}_2$, and we can assume that they are normalized.

Before we proceed, take a guess at what you would see if we plot ${\mathbf{v}}_1$, ${\mathbf{v}}_2$, $\mathbf{A}{\mathbf{v}}_1$ and $\mathbf{A}{\mathbf{v}}_2$.

Recall the question we asked earlier: Among all unit vectors $\mathbf{x}$, which one maximizes $\Vert \mathbf{A}\mathbf{x}\Vert$? It seems that we have found the answer. It is the eigenvectors of ${\mathbf{A}}^{\mathrm{\top }}\mathbf{A}$.

We have shown that this is true in the example of matrix $\mathbf{A}$. In general, for an $m\times n$ matrix $\mathbf{A}$, it can be shown that $\mathbf{A}{\mathbf{v}}_i$ has the greatest length and is perpendicular to the pervious $i-1$ eigenvectors, where ${\mathbf{v}}_1,{\mathbf{v}}_2,\dots ,{\mathbf{v}}_n$ are eigenvectors of ${\mathbf{A}}^T\mathbf{A}$.

For each of these eigenvectors, we can use the definition of length and the rule for the product of transposed matrices to have:

$$\Vert \mathbf{A}{\mathbf{v}}_i{\Vert }^2=(\mathbf{A}{\mathbf{v}}_i{)}^T\mathbf{A}{\mathbf{v}}_i={\mathbf{v}}_i^T{\mathbf{A}}^T\mathbf{A}{\mathbf{v}}_i$$

Let’s assume that the corresponding eigenvalue of ${\mathbf{v}}_i$ is ${\lambda }_i$

$${\mathbf{v}}_i^T{\mathbf{A}}^T\mathbf{A}{\mathbf{v}}_i={\mathbf{v}}_i^T{\lambda }_i{\mathbf{v}}_i={\lambda }_i{\mathbf{v}}_i^T{\mathbf{v}}_i$$

And because ${\mathbf{v}}_i$ is normalized, so

$$\Vert {\mathbf{v}}_i{\Vert }^2={\mathbf{v}}_i^T{\mathbf{v}}_i=1$$

and

$$\Vert \mathbf{A}{\mathbf{v}}_i{\Vert }^2={\lambda }_i{\mathbf{v}}_i^T{\mathbf{v}}_i={\lambda }_i$$

This result shows that all the eigenvalues of ${\mathbf{A}}^{\mathrm{\top }}\mathbf{A}$ are non-negative. If we label them in descending order, we have:

$${\lambda }_1\ge {\lambda }_2\ge \cdots \ge {\lambda }_n\ge 0$$

The singular value of $\mathbf{A}$ is defined as the square root of ${\lambda }_i$, denoted ${\sigma }_i$.

$${\sigma }_i=\sqrt{{\lambda }_i}=\Vert \mathbf{A}{\mathbf{v}}_i\Vert ,{\sigma }_1\ge {\sigma }_2\ge \cdots \ge {\sigma }_n\ge 0$$

Therefore, the singular values of $\mathbf{A}$ are the length of vectors $\mathbf{A}{\mathbf{v}}_i$. An important theory that forms the backbone of the SVD method: the maximum value of $\Vert \mathbf{A}\mathbf{x}\Vert$, subject to the constraints

$$\Vert \mathbf{x}\Vert =1,{\mathbf{x}}^{\mathrm{\top }}{\mathbf{v}}_1=0,{\mathbf{x}}^{\mathrm{\top }}{\mathbf{v}}_2=0,\dots ,{\mathbf{x}}^{\mathrm{\top }}{\mathbf{v}}_{k-1}=0$$

is ${\sigma }_k$, and this maximum value is attained at ${\mathbf{v}}_k$, the $k$-th eigenvector of ${\mathbf{A}}^T\mathbf{A}$.

In an earlier post, we mentioned that a symmetric matrix transforms a vector by stretching or shrinking the vector along the eigenvectors of this matrix.

With a non-symmetric matrix $\mathbf{A}$, it transforms a vector by stretching or shrinking the vector along the direction of $\mathbf{A}{\mathbf{v}}_i$, where ${\mathbf{v}}_i$ is an eigenvector of ${\mathbf{A}}^T\mathbf{A}$, ordered based on its corresponding eigenvalue, $\Vert {\mathbf{v}}_i\Vert =1$. The corresponding singular value ${\sigma }_i$ is the scalar that determines the length of the stretching, ${\sigma }_i=\sqrt{{\lambda }_i}$, where ${\lambda }_i$ is the corresponding eigenvalue of ${\mathbf{A}}^{\mathrm{\top }}\mathbf{A}$.

How can we reconcile these two seemingly different rules? Let’s take a symmetric metrix, $\mathbf{B}$. Suppose that its $i$-th eigenvector is ${\mathbf{u}}_i$ and the corresponding eigenvalue is ${\lambda }_i$. If we multiply ${\mathbf{B}}^{\mathrm{\top }}\mathbf{B}$ by ${\mathbf{u}}_i$ we get:

$$\left({\mathbf{B}}^{\mathrm{\top }}\mathbf{B}\right){\mathbf{u}}_i=\mathbf{B}\left(\mathbf{B}{\mathbf{u}}_i\right)=\mathbf{B}{\lambda }_i{\mathbf{u}}_i={\lambda }_i\mathbf{B}{\mathbf{u}}_i={\lambda }_i^2{\mathbf{u}}_i$$

which means that ${\mathbf{u}}_i$ is also an eigenvector of ${\mathbf{B}}^{\mathrm{\top }}\mathbf{B}$, but its corresponding eigenvalue is ${\lambda }_i^2$! Now we can see that the previous rule about a symmetric matrix is nothing but a special case of the more general rule:

A matrix $\mathbf{A}$ transforms a vector by stretching or shrinking the vector along the direction of $\mathbf{A}{\mathbf{v}}_i$, where ${\mathbf{v}}_i$ is an eigenvector of ${\mathbf{A}}^T\mathbf{A}$, ordered based on its corresponding singular value. The corresponding singular value ${\sigma }_i$ is the scalar that determines the length of the stretching or shrinking, ${\sigma }_i=\sqrt{{\lambda }_i}$, where ${\lambda }_i$ is the corresponding eigenvalue of ${\mathbf{A}}^{\mathrm{\top }}\mathbf{A}$.

When $\mathbf{A}$ is symmetric, the direction of $\mathbf{A}{\mathbf{v}}_i$ will be identical to that of $\mathbf{A}{\mathbf{u}}_i$, because $\mathbf{A}$ has the same eigenvectors as ${\mathbf{A}}^{\mathrm{\top }}\mathbf{A}$. Moreover, $\mathbf{A}{\mathbf{u}}_i={\lambda }_i{\mathbf{u}}_i$. Therefore, the direction of $\mathbf{A}{\mathbf{v}}_i$ is the direction of $\mathbf{A}{\mathbf{u}}_i$, which is the direction of ${\mathbf{u}}_i$. That is, a symmetric matrix transforms a vector by stretching or shrinking the vector along the direction of ${\mathbf{u}}_i$, its eigenvector!

What about the length of the stretching or shrinking? We know that ${\lambda }_i=\sqrt{{\lambda }_i^2}$, where ${\lambda }_i^2$ is the corresponding eigenvalue of ${\mathbf{A}}^{\mathrm{\top }}\mathbf{A}$, and ${\lambda }_i$ is the corresponding eigenvalue of $\mathbf{A}$. Therefore, a symmetric matrix transforms a vector along its eigenvectors ${\mathbf{u}}_i$, scaled by its corresponding eigenvalues ${\lambda }_i$. We have come a full circle! In the next post, we are finally ready to present the singular value decomposition equation!