28 SVD Theorem and Proof, SVD Abstraction, Pseudoinverse

Lecture from 20.12.2024 | Video: Videos ETHZ

Singular Value Decomposition

Definition: Singular Value Decomposition (SVD)

Recall from last lecture…

Let $A\in {\mathbb{R}}^{m\times n}$ be any matrix. A singular value decomposition of $A$ is a factorization of the form:

$A=U\Sigma V^T$

where:

• $U\in {\mathbb{R}}^{m\times m}$ is an orthogonal matrix whose columns are called the left singular vectors of $A$.
• $V\in {\mathbb{R}}^{n\times n}$ is an orthogonal matrix whose columns are called the right singular vectors of $A$.
• $\Sigma \in {\mathbb{R}}^{m\times n}$ is a diagonal matrix with non-negative entries ${\sigma }_1\ge {\sigma }_2\ge \cdots \ge {\sigma }_{\min \{m,n\}}\ge 0$ on the diagonal, called the singular values of $A$.

Okay, here’s a complete proof of the Singular Value Decomposition (SVD) theorem, first for the general (full) SVD and then for the compact SVD.

Note that the lecturer looked at the case where $m=n,rank(A)=n$, however below is the generalized proof for the complete SVD and the compact SVD…

SVD Theorem

Every matrix $A\in {\mathbb{R}}^{m\times n}$ has a singular value decomposition of the form:

$A=U\Sigma V^T$

where:

• $U\in {\mathbb{R}}^{m\times m}$ is an orthogonal matrix whose columns are the left singular vectors of $A$.
• $V\in {\mathbb{R}}^{n\times n}$ is an orthogonal matrix whose columns are the right singular vectors of $A$.
• $\Sigma \in {\mathbb{R}}^{m\times n}$ is a diagonal matrix with non-negative entries ${\sigma }_1\ge {\sigma }_2\ge \cdots \ge {\sigma }_{\min \{m,n\}}\ge 0$ on the diagonal, called the singular values of $A$.

Proof of the Full SVD

1. Spectral Decomposition of $A{A}^T$: Consider the symmetric matrix $A{A}^T\in {\mathbb{R}}^{m\times m}$. By the spectral theorem, it has a complete set of orthonormal eigenvectors and can be decomposed as: $A{A}^T=U\Lambda U^T$

   where $U\in {\mathbb{R}}^{m\times m}$ is an orthogonal matrix whose columns are the eigenvectors of $A{A}^T$, and $\Lambda \in {\mathbb{R}}^{m\times m}$ is a diagonal matrix containing the eigenvalues of $A{A}^T$.

2. Ordering Eigenvalues: Arrange the eigenvalues in $\Lambda$ in decreasing order: ${\lambda }_1\ge {\lambda }_2\ge \cdots \ge {\lambda }_m\ge 0$. Note that the eigenvalues are non-negative because $A{A}^T$ is positive semidefinite.

3. Rank and Non-zero Eigenvalues: Let $r=\text{rank}(A)$. Then, $A{A}^T$ also has rank $r$, and exactly $r$ eigenvalues are non-zero: ${\lambda }_1\ge \cdots \ge {\lambda }_r>0$ and ${\lambda }_{r+1}=\cdots ={\lambda }_m=0$.

4. Singular Values: Define the singular values ${\sigma }_i=\sqrt{{\lambda }_i}$ for $i=1,\dots ,\min \{m,n\}$. Note that only the first $r$ singular values are non-zero.

5. Constructing $\Sigma$: Let $\Sigma \in {\mathbb{R}}^{m\times n}$ be a diagonal matrix with the singular values ${\sigma }_1,\dots ,{\sigma }_{\min \{m,n\}}$ on the diagonal, arranged in decreasing order.

6. Defining $V_r$: Let $U_r\in {\mathbb{R}}^{m\times r}$ be the matrix containing the first $r$ columns of $U$ (eigenvectors of $A{A}^T$ corresponding to the non-zero eigenvalues). Define: $V_r:=A^T{U}_r{\Sigma }_r^{-1}\in {\mathbb{R}}^{n\times r}$

   where ${\Sigma }_r\in {\mathbb{R}}^{r\times r}$ is the diagonal matrix containing only the first $r$ non-zero singular values.

7. Orthogonality of $V_r$: We need to show that $V_r^T{V}_r=I_r$: $V_r^T{V}_r=({\Sigma }_r^{-1}{)}^T{U}_r^{T}A{A}^T{U}_r{\Sigma }_r^{-1}={\Sigma }_r^{-1}{U}_r^T(U_r{\Lambda }_r{U}_r^T)U_r{\Sigma }_r^{-1}={\Sigma }_r^{-1}{\Lambda }_r{\Sigma }_r^{-1}=I_r$

8. Extending $V_r$ to an Orthogonal Matrix $V$: Since $V_r$ has orthonormal columns, we can extend it to a full orthogonal matrix $V\in {\mathbb{R}}^{n\times n}$ by adding $n-r$ orthonormal columns that are also orthogonal to the columns of $V_r$. We can use the Gram-Schmidt process for this.

9. Showing $AV=U\Sigma$: We’ll show that $AV=U\Sigma$ by demonstrating that their corresponding columns are equal.

   • For $i=1,\dots ,r$: $A{\mathbf{v}}_i=A(A^T{\mathbf{u}}_i{\sigma }_i^{-1})=(A{A}^T){\mathbf{u}}_i{\sigma }_i^{-1}={\mathbf{u}}_i{\lambda }_i{\sigma }_i^{-1}={\mathbf{u}}_i{\sigma }_i$
   • For $i=r+1,\dots ,n$: We need to show that $A{\mathbf{v}}_i=0$. We know ${\mathbf{v}}_i$ is orthogonal to the columns of $V_r$, which are linear combinations of the columns of $A^T$. This means that ${\mathbf{v}}_i$ is orthogonal to every vector in the column space of $A^T$, which is equivalent to being in the null space of $A$. Thus, $A{\mathbf{v}}_i=0$.

   Combining these, we see that $AV=U\Sigma$.

10. Final Step: Since $V$ is orthogonal, $V^{T}V=I$. Multiplying both sides of $AV=U\Sigma$ by $V^T$ on the right, we get:

    $AV{V}^T=U\Sigma V^T⟹A=U\Sigma V^T$

This completes the proof of the full SVD.

Compact SVD Theorem

Every matrix $A\in {\mathbb{R}}^{m\times n}$ of rank $r$ has a compact singular value decomposition of the form:

$A=U_r{\Sigma }_r{V}_r^T$

where:

• $U_r\in {\mathbb{R}}^{m\times r}$ contains the first $r$ left singular vectors of $A$.
• $V_r\in {\mathbb{R}}^{n\times r}$ contains the first $r$ right singular vectors of $A$.
• ${\Sigma }_r\in {\mathbb{R}}^{r\times r}$ is a diagonal matrix containing the first $r$ (non-zero) singular values of $A$.

Proof of the Compact SVD

The proof of the compact SVD follows directly from the proof of the full SVD. We have already constructed $U_r$, ${\Sigma }_r$, and $V_r$ in steps 1-7 above. We also showed that $V_r^T{V}_r=I_r$.

In step 9, we showed that $A{\mathbf{v}}_i={\mathbf{u}}_i{\sigma }_i$ for $i=1,\dots ,r$. This can be written in matrix form as:

$A{V}_r=U_r{\Sigma }_r$

Multiplying both sides on the right by $V_r^T$, and using the fact that $V_r^T{V}_r=I_r$, we get:

$A{V}_r{V}_r^T=U_r{\Sigma }_r{V}_r^T$

From the full SVD proof, we know that $A=U\Sigma V^T$. By considering only the first $r$ columns of $U$, $V$ and non-zero entries in $\Sigma$, and using the fact that the remaining columns of $V$ are in the nullspace of $A$, we can write $A=U_r{\Sigma }_r{V}_r^T$.

This completes the proof of the compact SVD.

Consequence of the SVD: Sum of Rank-1 Matrices

Not part of the lecture, but part of the slides…

Theorem: A rank-$r$ matrix $A\in {\mathbb{R}}^{m\times n}$ can be expressed as a sum of $r$ rank-1 matrices.

Proof: This follows directly from the compact SVD:

$A=U_r{\Sigma }_r{V}_r^T=\left[\begin{array}{ccc}|& & |\\ {\mathbf{u}}_1& \cdots & {\mathbf{u}}_r\\ |& & |\end{array}\right]\left[\begin{array}{ccc}{\sigma }_1& & \\ & \ddots & \\ & & {\sigma }_r\end{array}\right]\left[\begin{array}{ccc}-& {\mathbf{v}}_1^T& -\\ & ⋮& \\ -& {\mathbf{v}}_r^T& -\end{array}\right]={\sum }_{k=1}^r{\sigma }_k{\mathbf{u}}_k{\mathbf{v}}_k^T$

Each outer product ${\mathbf{u}}_k{\mathbf{v}}_k^T$ is a rank-1 matrix, and the SVD expresses $A$ as a weighted sum of these rank-1 matrices, where the weights are the singular values.

This decomposition is fundamental in many applications, including low-rank matrix approximation, dimensionality reduction, and data compression. The SVD provides a powerful and insightful way to understand the structure of any matrix.

Further Remarks on the SVD

Abstraction and Change of Basis: Understanding the Motivation for SVD (Remark 1)

Let’s delve into the core idea behind the Singular Value Decomposition (SVD) by exploring how a linear transformation can be represented differently under a change of basis. This provides a powerful way to understand the motivation and significance of the SVD.

Representing Linear Transformations with Respect to Different Bases

Consider a linear transformation $T:{\mathbb{R}}^n\to {\mathbb{R}}^m$ represented by the matrix $A\in {\mathbb{R}}^{m\times n}$. This means that for any vector $\mathbf{x}\in {\mathbb{R}}^n$, the transformation is computed as $\mathbf{y}=A\mathbf{x}$, where $\mathbf{y}\in {\mathbb{R}}^m$.

• Canonical Basis: Typically, we represent vectors using the standard (canonical) basis. In ${\mathbb{R}}^n$, the canonical basis is $\{{\mathbf{e}}_1,{\mathbf{e}}_2,\dots ,{\mathbf{e}}_n\}$, where ${\mathbf{e}}_i$ is a vector with a 1 in the $i$-th position and 0s elsewhere. Similarly, the canonical basis in ${\mathbb{R}}^m$ is $\{{\mathbf{e}}_1^{\prime },{\mathbf{e}}_2^{\prime },\dots ,{\mathbf{e}}_m^{\prime }\}$. When we write $A\mathbf{x}$, it’s implicitly understood that $\mathbf{x}$ is represented in the canonical basis of ${\mathbb{R}}^n$, and the resulting vector $\mathbf{y}=A\mathbf{x}$ is represented in the canonical basis of ${\mathbb{R}}^m$.

• Expanding in the Canonical Basis: We can express the result of the transformation, $A\mathbf{x}$, as a linear combination of the basis vectors of the codomain, ${\mathbb{R}}^m$. Let $(A\mathbf{x}{)}_i$ denote the $i$-th component of $A\mathbf{x}$. Then, we can write:

  $A\mathbf{x}={\sum }_{i=1}^m(A\mathbf{x}{)}_i{\mathbf{e}}_i^{\prime }$

• The Role of Abstraction: This formula highlights the role of abstraction. We are expressing the action of the linear transformation in terms of its effect on the components of the input vector, and then using the basis vectors of the codomain to construct the output vector.

Changing the Basis

Now, suppose we want to represent our vectors using different bases. Let:

• $V=[{\mathbf{v}}_1,\dots ,{\mathbf{v}}_n]$ be a matrix whose columns form a basis for ${\mathbb{R}}^n$.
• $U=[{\mathbf{u}}_1,\dots ,{\mathbf{u}}_m]$ be a matrix whose columns form a basis for ${\mathbb{R}}^m$.

Any vector $\mathbf{x}\in {\mathbb{R}}^n$ can be expressed as a linear combination of the basis vectors in $V$:

$\mathbf{x}={\alpha }_1{\mathbf{v}}_1+{\alpha }_2{\mathbf{v}}_2+\cdots +{\alpha }_n{\mathbf{v}}_n=V\mathbf{\alpha }$

where $\mathbf{\alpha }=\left[\begin{array}{c}{\alpha }_1\\ {\alpha }_2\\ ⋮\\ {\alpha }_n\end{array}\right]$ is the vector of coordinates of $\mathbf{x}$ with respect to the basis $V$.

Similarly, any vector $\mathbf{y}\in {\mathbb{R}}^m$ can be expressed as a linear combination of the basis vectors in $U$:

$\mathbf{y}={\beta }_1{\mathbf{u}}_1+{\beta }_2{\mathbf{u}}_2+\cdots +{\beta }_m{\mathbf{u}}_m=U\mathbf{\beta }$

where $\mathbf{\beta }=\left[\begin{array}{c}{\beta }_1\\ {\beta }_2\\ ⋮\\ {\beta }_m\end{array}\right]$ is the vector of coordinates of $\mathbf{y}$ with respect to the basis $U$.

Finding a New Representation for the Linear Transformation

Our goal is to find a matrix $B\in {\mathbb{R}}^{m\times n}$ that represents the same linear transformation as $A$, but with respect to the new bases $V$ and $U$. In other words, we want a matrix $B$ such that if $\mathbf{x}=V\mathbf{\alpha }$ and $A\mathbf{x}=\mathbf{y}=U\mathbf{\beta }$, then:

$B\mathbf{\alpha }=\mathbf{\beta }$

This means that $B$ takes the coordinates of $\mathbf{x}$ in the basis $V$ and produces the coordinates of $\mathbf{y}=A\mathbf{x}$ in the basis $U$.

We have $\mathbf{y}=A\mathbf{x}$, which can be written as $U\mathbf{\beta }=AV\mathbf{\alpha }$. Multiplying both sides by $U^{-1}$ on the left gives $\mathbf{\beta }=U^{-1}AV\mathbf{\alpha }$. Since we want $\mathbf{\beta }=B\mathbf{\alpha }$, we can define: $B=U^{-1}AV$ Multiplying both sides on the left by $U$ and on the right by $V^{-1}$, we also get the equivalent relationship $A=UB{V}^{-1}$

The Essence of SVD: The SVD seeks a special form of this relationship where:

1. $U$ and $V$ are orthogonal matrices (their columns are orthonormal bases). This makes inverting them easy, as $U^{-1}=U^T$ and $V^{-1}=V^T$.
2. $B$ is a diagonal matrix (ideally with non-negative entries in decreasing order). This makes the transformation easy to understand, as it simply scales the components along the new basis vectors.

In essence, the SVD aims to find the “nicest” possible bases for the domain and codomain of a linear transformation, such that the transformation’s action is reduced to a simple scaling along the new coordinate axes. This is what makes the SVD such a powerful tool for understanding and manipulating linear transformations and matrices.

SVD and its Connection to the Spectral Theorem (Remark 2)

Let’s explore the connection between the Singular Value Decomposition (SVD) of an arbitrary matrix $A$ and the spectral theorem applied to the symmetric matrices $A{A}^T$ and $A^{T}A$. This connection provides a deeper understanding of the SVD and its relationship to eigenvalues and eigenvectors.

Starting with the SVD

Let $A\in {\mathbb{R}}^{m\times n}$ be an arbitrary matrix, and let its SVD be given by:

$A=U\Sigma V^T$

where $U\in {\mathbb{R}}^{m\times m}$ and $V\in {\mathbb{R}}^{n\times n}$ are orthogonal matrices, and $\Sigma \in {\mathbb{R}}^{m\times n}$ is a diagonal matrix with the singular values of $A$ on its diagonal.

Transpose of A

Taking the transpose of $A$, we get:

$A^T=(U\Sigma V^T{)}^T=V{\Sigma }^T{U}^T$

Forming $A{A}^T$

Now, let’s consider the product $A{A}^T$:

$A{A}^T=(U\Sigma V^T)(V{\Sigma }^T{U}^T)=U\Sigma (V^{T}V){\Sigma }^T{U}^T$

Since $V$ is orthogonal, $V^{T}V=I$. Thus:

$A{A}^T=U\Sigma {\Sigma }^T{U}^T$

Observations

1. Eigenvectors of $A{A}^T$: The equation $A{A}^T=U(\Sigma {\Sigma }^T)U^T$ has the form of an eigendecomposition. The columns of $U$ are the eigenvectors of $A{A}^T$.
2. Eigenvalues of $A{A}^T$: The matrix $\Sigma {\Sigma }^T\in {\mathbb{R}}^{m\times m}$ is a diagonal matrix. Its diagonal entries are the squares of the singular values of $A$ (${\sigma }_i^2$), which are also the eigenvalues of $A{A}^T$. If $m>n$, then the last $m-n$ diagonal entries of $\Sigma {\Sigma }^T$ are zero.
3. Spectral Theorem: This decomposition of $A{A}^T$ is precisely the spectral theorem applied to the symmetric matrix $A{A}^T$. It confirms that $A{A}^T$ has a complete set of orthonormal eigenvectors (the columns of $U$) and real, non-negative eigenvalues (the diagonal entries of $\Sigma {\Sigma }^T$).

Forming $A^{T}A$

Similarly, let’s consider the product $A^{T}A$:

$A^{T}A=(V{\Sigma }^T{U}^T)(U\Sigma V^T)=V{\Sigma }^T(U^{T}U)\Sigma V^T$

Since $U$ is orthogonal, $U^{T}U=I$. Thus:

$A^{T}A=V{\Sigma }^T\Sigma V^T$

Observations

1. Eigenvectors of $A^{T}A$: The equation $A^{T}A=V({\Sigma }^T\Sigma )V^T$ is an eigendecomposition of $A^{T}A$. The columns of $V$ are the eigenvectors of $A^{T}A$.
2. Eigenvalues of $A^{T}A$: The matrix ${\Sigma }^T\Sigma \in {\mathbb{R}}^{n\times n}$ is a diagonal matrix. Its diagonal entries are also the squares of the singular values of $A$ (${\sigma }_i^2$), which are the eigenvalues of $A^{T}A$. If $n>m$, then the last $n-m$ diagonal entries of ${\Sigma }^T\Sigma$ are zero.
3. Spectral Theorem: This decomposition of $A^{T}A$ is the spectral theorem applied to the symmetric matrix $A^{T}A$. It confirms that $A^{T}A$ has a complete set of orthonormal eigenvectors (the columns of $V$) and real, non-negative eigenvalues (the diagonal entries of ${\Sigma }^T\Sigma$).

A Generalized Notion of Eigenvectors

The SVD, through its connection to $A{A}^T$ and $A^{T}A$, provides a generalization of the concept of eigenvectors. While eigenvectors are traditionally defined for square matrices, the singular vectors of a general matrix $A$ (which can be rectangular) can be thought of as analogous to eigenvectors in the following sense:

• The left singular vectors (columns of $U$) are eigenvectors of $A{A}^T$.
• The right singular vectors (columns of $V$) are eigenvectors of $A^{T}A$.
• The singular values of $A$ are the square roots of the non-zero eigenvalues of both $A{A}^T$ and $A^{T}A$.

In other words, the SVD identifies two sets of orthonormal vectors (left and right singular vectors) that are related through the action of $A$ and $A^T$, and it provides a set of scaling factors (singular values) that quantify the “stretching” or “shrinking” effect of the linear transformation along these directions. This provides a more general framework for understanding how a linear transformation acts on vectors, even when the matrix is not square or symmetric.

Here are some additional remarks on the properties and applications of the Singular Value Decomposition (SVD), expanding on the concepts presented in the lecture.

SVD and the (Pseudo)inverse (Remark 3)

Invertible Matrices

If $A\in {\mathbb{R}}^{n\times n}$ is invertible and has an SVD $A=U\Sigma V^T$, then its inverse can be easily computed using the SVD components:

$A^{-1}=V{\Sigma }^{-1}{U}^T$

Explanation

Since $A$ is invertible, all its singular values are non-zero, and $\Sigma$ is a square, diagonal matrix with non-zero entries. Thus, ${\Sigma }^{-1}$ is simply the diagonal matrix with the reciprocals of the singular values on the diagonal. We can verify that this is the inverse:

$A{A}^{-1}=(U\Sigma V^T)(V{\Sigma }^{-1}{U}^T)=U\Sigma (V^{T}V){\Sigma }^{-1}{U}^T=U\Sigma {\Sigma }^{-1}{U}^T=U{U}^T=I$

$A^{-1}A=(V{\Sigma }^{-1}{U}^T)(U\Sigma V^T)=V{\Sigma }^{-1}(U^{T}U)\Sigma V^T=V{\Sigma }^{-1}\Sigma V^T=V{V}^T=I$

Pseudoinverse

The concept of an inverse can be generalized to non-square or singular matrices using the pseudoinverse. The SVD provides a way to define the Moore-Penrose pseudoinverse, denoted by $A^{+}$. If $A=U\Sigma V^T$, then:

$A^{+}=V{\Sigma }^{+}{U}^T$

where ${\Sigma }^{+}$ is obtained from $\Sigma$ by taking the reciprocal of each non-zero singular value, leaving the zeros in place, and transposing the matrix.

Example

If $\Sigma =\left[\begin{array}{ccc}{\sigma }_1& 0& 0\\ 0& {\sigma }_2& 0\\ 0& 0& 0\end{array}\right]$, then ${\Sigma }^{+}={\left[\begin{array}{ccc}1/{\sigma }_1& 0& 0\\ 0& 1/{\sigma }_2& 0\\ 0& 0& 0\end{array}\right]}^T=\left[\begin{array}{ccc}1/{\sigma }_1& 0& 0\\ 0& 1/{\sigma }_2& 0\\ 0& 0& 0\end{array}\right]$. If $\Sigma =\left[\begin{array}{cccc}{\sigma }_1& 0& 0& 0\\ 0& {\sigma }_2& 0& 0\\ 0& 0& 0& 0\end{array}\right]$, then ${\Sigma }^{+}=\left[\begin{array}{ccc}1/{\sigma }_1& 0& 0\\ 0& 1/{\sigma }_2& 0\\ 0& 0& 0\\ 0& 0& 0\end{array}\right]$.

Significance: The pseudoinverse is a powerful tool for solving least-squares problems, finding minimum-norm solutions to underdetermined systems, and analyzing matrix properties.

Compact SVD (Remark 4)

If $A\in {\mathbb{R}}^{m\times n}$ has rank $r$, its SVD can be represented in a compact form:

$A=U_r{\Sigma }_r{V}_r^T$

where:

• $U_r\in {\mathbb{R}}^{m\times r}$ contains the first $r$ left singular vectors of $A$ (corresponding to the non-zero singular values).
• ${\Sigma }_r\in {\mathbb{R}}^{r\times r}$ is a diagonal matrix containing the $r$ non-zero singular values of $A$.
• $V_r\in {\mathbb{R}}^{n\times r}$ contains the first $r$ right singular vectors of $A$ (corresponding to the non-zero singular values).

Example

Let $A$ be a $4\times 5$ matrix with rank 3. Then the compact SVD of $A$ would have the form:

$A=U_3{\Sigma }_3{V}_3^T=\left[\begin{array}{ccc}|& |& |\\ {\mathbf{u}}_1& {\mathbf{u}}_2& {\mathbf{u}}_3\\ |& |& |\end{array}\right]\left[\begin{array}{ccc}{\sigma }_1& 0& 0\\ 0& {\sigma }_2& 0\\ 0& 0& {\sigma }_3\end{array}\right]\left[\begin{array}{ccc}-& {\mathbf{v}}_1^T& -\\ -& {\mathbf{v}}_2^T& -\\ -& {\mathbf{v}}_3^T& -\end{array}\right]$

where $U_3$ is $4\times 3$, ${\Sigma }_3$ is $3\times 3$, and $V_3^T$ is $3\times 5$.

SVD as a Sum of Rank-1 Matrices (Remark 5)

The SVD provides a way to express any matrix as a sum of rank-1 matrices.

Theorem

Let $A\in {\mathbb{R}}^{m\times n}$ have rank $r$, with non-zero singular values ${\sigma }_1,\dots ,{\sigma }_r$, left singular vectors ${\mathbf{u}}_1,\dots ,{\mathbf{u}}_r$, and right singular vectors ${\mathbf{v}}_1,\dots ,{\mathbf{v}}_r$. Then $A$ can be expressed as:

$A={\sum }_{i=1}^r{\sigma }_i{\mathbf{u}}_i{\mathbf{v}}_i^T$

Explanation

This follows directly from the compact SVD:

$A=U_r{\Sigma }_r{V}_r^T=\left[\begin{array}{ccc}|& & |\\ {\mathbf{u}}_1& \cdots & {\mathbf{u}}_r\\ |& & |\end{array}\right]\left[\begin{array}{ccc}{\sigma }_1& & \\ & \ddots & \\ & & {\sigma }_r\end{array}\right]\left[\begin{array}{ccc}-& {\mathbf{v}}_1^T& -\\ & ⋮& \\ -& {\mathbf{v}}_r^T& -\end{array}\right]$

Expanding the matrix multiplication, we get:

$A={\sigma }_1{\mathbf{u}}_1{\mathbf{v}}_1^T+{\sigma }_2{\mathbf{u}}_2{\mathbf{v}}_2^T+\cdots +{\sigma }_r{\mathbf{u}}_r{\mathbf{v}}_r^T={\sum }_{i=1}^r{\sigma }_i{\mathbf{u}}_i{\mathbf{v}}_i^T$

Each term ${\sigma }_i{\mathbf{u}}_i{\mathbf{v}}_i^T$ is a rank-1 matrix because it is the outer product of two vectors, ${\mathbf{u}}_i$ and ${\mathbf{v}}_i$, scaled by the singular value ${\sigma }_i$.

Significance

This decomposition shows that any matrix can be built up from a linear combination of simple rank-1 matrices. This is fundamental to many applications, including:

• Low-rank approximation: Truncating the sum after $k<r$ terms provides the best rank-$k$ approximation of $A$ in terms of the Frobenius norm and the spectral norm.
• Data compression: Storing only the first $k$ singular values and corresponding singular vectors allows for a compressed representation of $A$.
• Dimensionality reduction: The SVD can be used to project data onto a lower-dimensional subspace while preserving as much variance as possible (Principal Component Analysis).

The rest of the lecture didn’t seem useful enough to note down as it was mostly a bit of repetition…

This was the last lecture…