Singular Value Decomposition (SVD) of a Matrix

1. The SVD Construction Algorithm

Let's say we are given an $m\times n$ matrix $A$. We want to find the matrices $U$, $\Sigma$, and $V$ such that $A=U\Sigma V^T$, where $U$ is $m\times m$ orthogonal, $\Sigma$ is $m\times n$ diagonal, and $V$ is $n\times n$ orthogonal.

Here is a reliable procedure to find them:

1. Form $A^{T}A$ or $A{A}^T$. A practical tip for your future work in computer science: choose the smaller of the two matrices to reduce computation. If $A$ is a "tall" matrix ($m>n$), then $A^{T}A$ ($n\times n$) will be smaller than $A{A}^T$ ($m\times m$). Let's assume for this algorithm we start with $A^{T}A$.

2. Find Eigenvalues and Eigenvectors of $A^{T}A$. Since $A^{T}A$ is symmetric and positive semi-definite, it will have $n$ real, non-negative eigenvalues (${\lambda }_1,{\lambda }_2,\dots ,{\lambda }_n$) and a corresponding set of orthonormal eigenvectors (${\mathbf{v}}_1,{\mathbf{v}}_2,\dots ,{\mathbf{v}}_n$).

3. Construct $V$ and $\Sigma$.

   • The matrix $V$ is formed by using the eigenvectors from Step 2 as its columns: $V=[{\mathbf{v}}_1|{\mathbf{v}}_2|\dots |{\mathbf{v}}_n]$.
   • The singular values are the square roots of the eigenvalues: ${\sigma }_i=\sqrt{{\lambda }_i}$. By convention, we sort them in descending order, ${\sigma }_1\ge {\sigma }_2\ge \cdots \ge 0$.
   • The matrix $\Sigma$ is an $m\times n$ matrix with these singular values on its main diagonal. The rest of its entries are zero.

4. Find the Left Singular Vectors for $U$.

   • Recall the key relationship from our last lesson: $A{\mathbf{v}}_i={\sigma }_i{\mathbf{u}}_i$. For each non-zero singular value ${\sigma }_i\ne 0$, we can find the corresponding left singular vector ${\mathbf{u}}_i$ using the formula:
     ${\mathbf{u}}_i=\frac{1}{{\sigma }_i}A{\mathbf{v}}_i$
     This gives us the first $r$ columns of $U$, where $r$ is the rank of the matrix (the number of non-zero singular values).

5. Complete the Basis for $U$. The vectors we found in Step 4 form an orthonormal set. If $m>r$, the matrix $U$ is not yet complete. We need to find $m-r$ more orthonormal vectors that are orthogonal to the ones we already have. These additional vectors form an orthonormal basis for the null space of $A^T$. You can find them by solving $A^T\mathbf{x}=0$ and using the Gram-Schmidt process on the resulting basis vectors.

6. Assemble the Full SVD. Combine the matrices you have found: $A=U\Sigma V^T$.

2. A Step-by-Step Example

This process is best understood by walking through an example. The following video does an excellent job of applying this algorithm to a 3x2 matrix.

Let's summarize the key steps from the video's example with matrix $A=\left(\begin{array}{cc}1& 1\\ 0& 1\\ 1& 0\end{array}\right)$ (Note: The video uses a slightly different matrix, but the process is identical).

• Step 1: Form $A^{T}A$, which is a $2\times 2$ matrix.
• Step 2: Find its eigenvalues ${\lambda }_1=3,{\lambda }_2=1$ and orthonormal eigenvectors ${\mathbf{v}}_1,{\mathbf{v}}_2$.
• Step 3: Construct $V=[{\mathbf{v}}_1|{\mathbf{v}}_2]$ and $\Sigma$, a $3\times 2$ matrix with ${\sigma }_1=\sqrt{3},{\sigma }_2=1$ on its diagonal.
• Step 4: Find ${\mathbf{u}}_1=\frac{1}{\sqrt{3}}A{\mathbf{v}}_1$ and ${\mathbf{u}}_2=\frac{1}{1}A{\mathbf{v}}_2$.
• Step 5: Since $A$ is $3\times 2$, $U$ must be $3\times 3$. We need one more vector, ${\mathbf{u}}_3$. This vector is found by solving $A^T\mathbf{x}=0$ and normalizing the result.
• Step 6: Assemble $A=[{\mathbf{u}}_1|{\mathbf{u}}_2|{\mathbf{u}}_3]\Sigma V^T$.

3. Full vs. Reduced SVD

The decomposition we just constructed is known as the full SVD. It results in square orthogonal matrices $U$ and $V$. However, notice that if $m>n$, the bottom $m-n$ rows of $\Sigma$ are all zeros. When we multiply $U\Sigma V^T$, these zero rows in $\Sigma$ will effectively nullify the last $m-n$ columns of $U$.

This observation leads to a more compact and often more useful version called the reduced SVD (sometimes called "economy SVD").

In reduced SVD, we trim the matrices to remove the parts that get multiplied by zero.

• If $m\ge n$: We keep only the first $n$ columns of $U$ and the top $n\times n$ block of $\Sigma$.

  • $A_{m\times n}=U_{m\times n}{\Sigma }_{n\times n}{V}_{n\times n}^T$

• If $n>m$: We keep only the first $m$ columns of $V$ and the left $m\times m$ block of $\Sigma$.

  • $A_{m\times n}=U_{m\times m}{\Sigma }_{m\times m}{V}_{m\times n}^T$

The image below gives a nice visualization of this "trimming" process for the $m\ge n$ case.

The following reading provides a concise summary of the full and reduced SVD, along with another numerical example.

Let's apply this to the example from the video. The full SVD had:

• $U$: $3\times 3$
• $\Sigma$: $3\times 2$
• $V^T$: $2\times 2$

The reduced SVD for this $m\ge n$ case would be:

• $U_R$: $3\times 2$ (the first two columns of the full $U$)
• ${\Sigma }_R$: $2\times 2$ (the top square part of the full $\Sigma$)
• $V_R^T$: $2\times 2$ (the same as the full $V^T$)

The reduced SVD is computationally more efficient and is the version returned by default in many numerical libraries like NumPy.

Conclusion

Today, we've bridged the gap from theory to practice by developing a concrete algorithm for computing the SVD of any matrix.

Key Takeaways:

• The SVD can be constructed by finding the eigenvalues and eigenvectors of $A^{T}A$ (or $A{A}^T$).
• The Full SVD produces square orthogonal matrices $U$ and $V$, but often involves padding $\Sigma$ with rows or columns of zeros.
• The Reduced SVD is a more compact form that eliminates the zero-padding in $\Sigma$ and the corresponding unnecessary vectors in $U$ or $V$, resulting in a more computationally efficient representation.
• The general algorithm is:
  1. Calculate eigenvectors (${\mathbf{v}}_i$) of $A^{T}A$ to form $V$.
  2. Calculate singular values (${\sigma }_i=\sqrt{{\lambda }_i}$) to form $\Sigma$.
  3. Calculate the initial left singular vectors using ${\mathbf{u}}_i=\frac{1}{{\sigma }_i}A{\mathbf{v}}_i$.
  4. If necessary, complete the basis for $U$ with vectors from the null space of $A^T$.

Preview of the Next Lesson:

Now that we can define and construct the SVD, our next lesson will delve deeper into its profound geometric meaning. We will explore how $A=U\Sigma V^T$ can be interpreted as breaking down any linear transformation into a sequence of a rotation, a scaling, and another rotation, which is a foundational concept for understanding its power in both deep learning and quantum mechanics.