Notes - Machine Learning MT23, Singular value decomposition

Created: January 02, 2024

Flashcards

Suppose $A$ is an $m \times n$ matrix of rank $r$. What does the singular value decomposition of $A$ look like, and what are the corresponding left and right singular vectors?
\[A = U \Sigma V^\top\]

where

  • $U$ is an $m \times r$ matrix such that $U^\top U = I _ r$. The columns are the left singular vectors.
  • $V$ is an $n \times r$ matrix such that $V^\top V = I _ r$. The columns are the right singular vectors.
  • $\Sigma = \text{diag}(\sigma _ 1, \cdots, \sigma _ r)$ where $\sigma _ 1 \ge \cdots \ge \sigma _ r$ are strictly positive.

Suppose $A$ is an $m\times n$ matrix of rank $r$. The singular value decomposition of $a$ looks like

\[A = U \Sigma V^\top\]

where

  • $U$ is an $m \times r$ matrix such that $U^\top U = I _ r$
  • $V$ is an $n \times r$ matrix such that $V^\top V = I _ r$
  • $\Sigma = \text{diag}(\sigma _ 1, \cdots, \sigma _ r)$

What additional conditions do we have on $\sigma _ 1, \cdots, \sigma _ r$?

They are positive and stricly decreasing, i.e.

\[\sigma_1 \ge \cdots \ge \sigma_r \ge 0\]

Suppose $A$ is an $m \times n$ matrix of rank $r$ with SVD given by $A = U \Sigma V^\top$ with singular values $\sigma _ i$ and corresponding left and right singular vectors $\pmb u _ i$ and $\pmb v _ i$. How can you express $A$ as the sum of rank-$1$ matrices?
\[A = \sum^r_{i=1} \sigma_i \pmb u_i \pmb v_i^\top\]

Quickly justify that the singular values of a matrix $A$ are the eigenvalues of $A^\top A$ or $A A^\top$, focussing on the $A^\top A$ case and then explaining where the right singular vectors, collected in a matrix $V$, come from
\[\begin{aligned} A^\top A V &= (U \Sigma V^\top)\top(U \Sigma V^\top) V \\\\ &= V \Sigma^\top U^\top U \Sigma V^\top V \\\\ &= V \Sigma^\top \Sigma V^\top V \\\\ &= V \Sigma^2 \end{aligned}\]

Hence each right singular vector is an eigenvector of $A^\top A$ with non-zero eigenvalue $\sigma _ i^2$.

Can you define the Frobenius norm of an $m \times n$ matrix, and also write it in terms of a trace?
\[||A||_F = \sqrt{\sum^m _ {i = 1} \sum^n _{j = 1} a^2 _{ij}\\,} = \sqrt{\text{trace}(A^\top A)}\]

Can you give the Frobenius norm of a matrix $A$ in terms of its singular values $\sigma _ i$?
\[||A||_F^2 = \text{trace}(A^\top A) = \text{trace}((U\Sigma V^\top)^\top(U\Sigma V^\top)) = \text{trace}(\Sigma^\top \Sigma) = \sum^r_{i=1} \sigma_i^2\]

Suppose $A$ is an $m \times n$ matrix of rank $r$ with SVD given by $A = U \Sigma V^\top$ with singular values $\sigma _ i$ and corresponding left and right singular vectors $\pmb u _ i$ and $\pmb v _ i$. How can you find a low-rank approximation?

Truncate the SVD after the first $k$ terms

\[A_k \triangleq \sum^k_{i=1} \sigma_i \pmb u_i \pmb v_i^\top\]

State the Eckart-Young theorem, which connects SVD, low-rank approximations and the Frobenius norm.

Suppose:

  • $A$ is a matrix
  • $A _ k$ is the matrix obtained after truncating SVD after $k$ steps, i.e. $A _ k \triangleq \sum^k _ {i=1} \sigma _ i \pmb u _ i \pmb v _ i^\top$

Then:

  • For all matrices $B$, $A _ k$ gives the best rank-$k$ approximation of $A$ with respect to the Frobenius norm, i.e. $\forall B$, $ \vert \vert A-A _ k \vert \vert _ F \le \vert \vert A - B \vert \vert _ F$.

Suppose $X$ is a matix with right singular vectors $v _ 1, \cdots, v _ n$. How can you compute the left singular vectors?
\[u_i = \frac{Xv_i}{||Xv_i||}\]

This can be seen from rearranging $X = U\Sigma V^\top$.



Related posts