Machine Learning MT23, Singular value decomposition
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?
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?
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
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?
Can you give the Frobenius norm of a matrix $A$ in terms of its singular values $\sigma _ i$?
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?
This can be seen from rearranging $X = U\Sigma V^\top$.
Bite-sized
Frobenius norm via singular values: $\ \vert A\ \vert _ F = $ $\sqrt{\sum _ i \sigma _ i(A)^2}$. Equivalently $\ \vert A\ \vert _ F^2 = \mathrm{Trace}(A^\top A)$.
Eckart-Young in Frobenius norm: $\ \vert A - A _ k\ \vert _ F = $ $\sqrt{\sum _ {i > k} \sigma _ i(A)^2}$, where $A _ k$ is the rank-$k$ truncated SVD. This is the best rank-$k$ approximation under any unitarily invariant norm.
What is the practical interpretation of “the singular values are the eigenvalues of $A^\top A$”?
This is the shortest proof of SVD existence: take the symmetric eigendecomposition $A^\top A = V \Lambda V^\top$ (which exists since $A^\top A$ is symmetric PSD). Then $\sigma _ i = \sqrt{\lambda _ i}$, $V$ gives the right singular vectors, and $U = A V \Sigma^{-1}$ recovers the left singular vectors. In practice, computing the SVD this way is inaccurate for small singular values (forming $A^\top A$ squares the condition number) — so Golub-Kahan bidiagonalisation is used instead.