Singular Value Decomposition

Neo Wang / May 17, 2021

– views

Introduction

This morning, I had just taken a Linear Algebra test, which in the post-mortem discussion of the test, realized that Singular Value Decomposition had most likely been the most missed topic. In fact, people even chose to skip questions that simply contained the wrongly-accursed words of "Singular Value Decomposition." The previous evening, I experienced a similar feeling, though it was through several Youtube videos and quite a bit of lecture notes that I was able to realize the simple algorithm for computing singular value decomposition. Interestingly enough, not many of them covered the method that I'm about to write about.

As usual, explanations often make the most sense with an example, so I will provide one below. Note that this is the same example as this MIT OCW Example, just in case you want to cross reference.

Since this is mainly about the solving process, Wikipedia provides a fairly detailed explanation on what the matrix is being decomposed to.

If you are not yet familiar with solving for eigenvectors, eigenvalues, and such, I would recommend checking out the following resources:

Method

The method that is about to be presented is fairly algorithmic, and involves solving for the eigenvalues and eigenvectors of two special matrices AATAA^T and ATAA^TA. One unique property to note is that the eigenvalues of ATAA^TA and ATAA^TA remain the same; we only need to solve for the eigenvalues once, thus making computation much faster. The steps are as follows:

  1. Find the eigenvalues of either ATAA^TA or AATAA^T
  2. Using the eigenvalues determined, find the eigenvectors of ATAA^TA and AATAA^T.
  3. Normalize the both of the eigenvectors determined in the previous step - making sure to put them into matrices UU and VV respectively. (Note that there exists a shortcut in the form AVi=σiUiAV_i=\sigma_i U_i for finding the UU's that may be used as well).
  4. Place the ii-th eigenvalue into Σii\Sigma_{ii} for each eigenvalue.
  5. Make sure that the ii-th eigenvector in matrix UU and VV correspond to the ii-th eigenvector in Σ\Sigma. If not, rearrange them.
  6. Done, you can put the matrices in the form A=UΣVTA = U\Sigma V^T.

Worked Example

Find the Singular Value Decomposition of AA.

A=[5517]A = \begin{bmatrix}5&5\\-1&7\end{bmatrix}

Standard Method

The key to finding the SVD is through the eigenvalues and eigenvectors of AATAA^T and ATAA^TA. In fact, these two matrices correspond to UU and VV respectively, although they must be normalized first. What's even nicer is that you only have to solve for the eigenvalues once; the eigenvalues of AATAA^T are the same as ATAA^TA. Since both ATAA^TA and ATAA^TA are guranteed to be definite symmetric matrices, I usually chose to solve for the one with lower dimension.

ATA=[26181874]A^TA = \begin{bmatrix}26&18\\18&74\end{bmatrix}

We can then solve for the eigenvalues and eigenvectors respectively using standard methods. Recall that this equates to solving

det([26λ181874λ])=0\det \left (\begin{bmatrix} 26 - \lambda & 18 \\ 18 & 74 - \lambda \end{bmatrix}\right) = 0

In this example, λ1=80\lambda_1 = 80 and λ2=20\lambda_2=20. The eigenvectors then are [13]\begin{bmatrix}1 \\ 3\end{bmatrix} and [31]\begin{bmatrix}-3\\1 \end{bmatrix} respectively. If we normalize these two vectors, then we get

V=[110310310110]V = \begin{bmatrix}\frac{1}{\sqrt{10}}&-\frac{3}{\sqrt{10}}\\[6pt] \frac{3}{\sqrt{10}} & \frac{1}{\sqrt{10}}\end{bmatrix}

Next, we calculate AATAA^T

AAT=[50303050]AA^T = \begin{bmatrix}50&30\\30&50\end{bmatrix}

Recall that since the nonzero eigenvalues are the same for both ATAA^TA and AATAA^T, we can skip the calculation of those and directly find the eigenvectors of AATAA^T.

The eigenvector matrix of AATAA^T then, is equivalent to the nullspaces of

[508030305080]=[30303030]\begin{bmatrix} 50 - 80 & 30 \\ 30 & 50 - 80 \end{bmatrix} = \begin{bmatrix} -30 & 30 \\ 30 & -30 \end{bmatrix}

and

[502030305020]=[30303030]\begin{bmatrix} 50 - 20 & 30 \\ 30 & 50 - 20 \end{bmatrix} = \begin{bmatrix} 30 & 30 \\ 30 & 30 \end{bmatrix}

The eigenvector matrix of AATAA^T then, is

[1111]\begin{bmatrix} 1 & -1 \\ 1 & 1 \end{bmatrix}

which again corresponds to the eigenvalues λ1=80,λ2=20\lambda_1 = 80, \lambda_2 = 20 respectively.

Afterwards, this gets gets normalized to

U=[12121212]U=\begin{bmatrix} \frac{1}{\sqrt{2}} & -\frac{1}{\sqrt{2}} \\[6pt] \frac{1}{\sqrt{2}} & \frac{1}{\sqrt{2}} \end{bmatrix}

That's it! All that's left are the σ\sigma's, which we happen to have already solved for, since σi=λi\sigma_i=\sqrt{\lambda_i}. Since all our eigenvalues are positive (and will always be positive), it's very easy to take the square root of λi\lambda_i

Remember that it's important to "line-up" the values of σi\sigma_i with the appropriate eigenvectors such that the ii-th column of VV and UU correspond to σi\sigma_i. In my calculations, this has already been kept track of, so we find

Σ=[800020]=[450025]\Sigma = \begin{bmatrix} \sqrt{80} & 0 \\ 0 & \sqrt{20} \end{bmatrix} = \begin{bmatrix} 4\sqrt{5} & 0 \\ 0 & 2\sqrt{5} \end{bmatrix}

All that's left now is to plug them into our initial equation, where we get

A=[12121212][450025][110310310110]TA = \begin{bmatrix} \frac{1}{\sqrt{2}} & \frac{1}{\sqrt{2}} \\[6pt] -\frac{1}{\sqrt{2}} & \frac{1}{\sqrt{2}} \end{bmatrix} \begin{bmatrix} 4\sqrt{5} & 0 \\ 0 & 2\sqrt{5} \end{bmatrix} \begin{bmatrix} \frac{1}{\sqrt{10}}&-\frac{3}{\sqrt{10}} \\[6pt] \frac{3}{\sqrt{10}} & \frac{1}{\sqrt{10}} \end{bmatrix}^T

or

A=[12121212][450025][110310310110]A = \begin{bmatrix} \frac{1}{\sqrt{2}} & \frac{1}{\sqrt{2}} \\[6pt] -\frac{1}{\sqrt{2}} & \frac{1}{\sqrt{2}} \end{bmatrix} \begin{bmatrix} 4\sqrt{5} & 0 \\ 0 & 2\sqrt{5} \end{bmatrix} \begin{bmatrix} \frac{1}{\sqrt{10}}&\frac{3}{\sqrt{10}} \\[6pt] -\frac{3}{\sqrt{10}} & \frac{1}{\sqrt{10}} \end{bmatrix}

We can verify our answer as correct using Wolfram Alpha's SVD tool as well as expanding it directly.

Shortcut Method

Recall that for step 3, we can use the shortcut AVi=σiUiAV_i=\sigma_i U_i to calculate our values of UU. Let's see if this works.

A=[5517],V=[110310310110]A = \begin{bmatrix} 5 & 5 \\ -1 & 7 \end{bmatrix}, V = \begin{bmatrix} \frac{1}{\sqrt{10}} & -\frac{3}{\sqrt{10}}\\[6pt] \frac{3}{\sqrt{10}} & \frac{1}{\sqrt{10}}\end{bmatrix}

so using our shortcut, we get the following expansions:

1σ1AV1=145[5517][110310]=[1212]\frac{1}{\sigma_1}AV_{1}= \frac{1}{4\sqrt{5}} \begin{bmatrix} 5 & 5 \\ -1 & 7 \end{bmatrix} \begin{bmatrix} \frac{1}{\sqrt{10}} \\[6pt] \frac{3}{\sqrt{10}} \end{bmatrix} = \begin{bmatrix} \frac{1}{\sqrt{2}} \\[6pt] \frac{1}{\sqrt{2}} \end{bmatrix}
1σ2AV2=125[5517][310110]=[1212]\frac{1}{\sigma_2}AV_{2}= \frac{1}{2\sqrt{5}} \begin{bmatrix} 5 & 5 \\ -1 & 7 \end{bmatrix} \begin{bmatrix} -\frac{3}{\sqrt{10}} \\[6pt] \frac{1}{\sqrt{10}} \end{bmatrix} = \begin{bmatrix} -\frac{1}{\sqrt{2}} \\[6pt] \frac{1}{\sqrt{2}} \end{bmatrix}

which produces the matrix

U=[12121212]U = \begin{bmatrix} \frac{1}{\sqrt{2}} & -\frac{1}{\sqrt{2}} \\[6pt] \frac{1}{\sqrt{2}} & \frac{1}{\sqrt{2}} \end{bmatrix}

which also produces another valid SVD of

A=[12121212][450025][110310310110]TA = \begin{bmatrix} \frac{1}{\sqrt{2}} & -\frac{1}{\sqrt{2}} \\[6pt] \frac{1}{\sqrt{2}} & \frac{1}{\sqrt{2}} \end{bmatrix} \begin{bmatrix} 4\sqrt{5} & 0 \\ 0 & 2\sqrt{5} \end{bmatrix} \begin{bmatrix} \frac{1}{\sqrt{10}}&-\frac{3}{\sqrt{10}} \\[6pt] \frac{3}{\sqrt{10}} & \frac{1}{\sqrt{10}} \end{bmatrix}^T

or

A=[12121212][450025][110310310110]A = \begin{bmatrix} \frac{1}{\sqrt{2}} & -\frac{1}{\sqrt{2}} \\[6pt] \frac{1}{\sqrt{2}} & \frac{1}{\sqrt{2}} \end{bmatrix} \begin{bmatrix} 4\sqrt{5} & 0 \\ 0 & 2\sqrt{5} \end{bmatrix} \begin{bmatrix} \frac{1}{\sqrt{10}}&\frac{3}{\sqrt{10}} \\[6pt] -\frac{3}{\sqrt{10}} & \frac{1}{\sqrt{10}} \end{bmatrix}

We can verify this through expansion as well as noting that the columns of UU are orthonormal to each other.

🌓