Exercises — Lesson 13: The Singular Value Decomposition
Exercise 13.1. [Hand] Compute the SVD ingredients of \(A = \left(\begin{smallmatrix}3&0\\0&-2\end{smallmatrix}\right)\): singular values, \(v_i\)’s, \(u_i\)’s. (Careful: singular values are positive; where did the sign of \(-2\) go?) Compare with the eigenvalues from Exercise 10.1(a).
Solution. Compute the SVD for \(A = \begin{pmatrix} 3 & 0 \\ 0 & -2 \end{pmatrix}\).
\[ \begin{pmatrix} 3 & 0 \\ 0 & -2 \end{pmatrix} \begin{pmatrix} 3 & 0 \\ 0 & -2 \end{pmatrix} = \begin{pmatrix} 9 & 0 \\ 0 & 4 \end{pmatrix} = A^\mathsf{T} A \]
\[ \begin{aligned} \sigma_1 &= 3 & \sigma_2 &= 2 \\[4pt] \lambda_1 &= 9 & \lambda_2 &= 4 \\[4pt] v_1 &= \begin{pmatrix} 1 \\ 0 \end{pmatrix} & v_2 &= \begin{pmatrix} 0 \\ 1 \end{pmatrix} \end{aligned} \]
Eigenvectors, by row reduction of \((A^\mathsf{T}A - \lambda I)v = 0\):
\[ \begin{pmatrix} 0 & 0 \\ 0 & -5 \end{pmatrix} \qquad\Longrightarrow\qquad x_1 \text{ free},\quad x_2 = 0 \]
\[ \begin{pmatrix} 5 & 0 \\ 0 & 0 \end{pmatrix} \qquad\Longrightarrow\qquad x_1 = 0,\quad x_2 \text{ free} \]
\[ u_1 = \frac{Av_1}{\sigma_1} = \frac{1}{3}\begin{pmatrix} 3 \\ 0 \end{pmatrix} = \begin{pmatrix} 1 \\ 0 \end{pmatrix}, \qquad u_2 = \frac{Av_2}{\sigma_2} = \frac{1}{2}\begin{pmatrix} 0 \\ -2 \end{pmatrix} = \begin{pmatrix} 0 \\ -1 \end{pmatrix} \]
\[ \boxed{\; U = \begin{pmatrix} 1 & 0 \\ 0 & -1 \end{pmatrix}, \qquad \Sigma = \begin{pmatrix} 3 & 0 \\ 0 & 2 \end{pmatrix}, \qquad V^\mathsf{T} = \begin{pmatrix} 1 & 0 \\ 0 & 1 \end{pmatrix} \;} \]
Exercise 13.2. [Hand] For \(A = \left(\begin{smallmatrix}1&2\\2&4\end{smallmatrix}\right)\) (rank 1), find \(\sigma_1, u_1, v_1\) and write \(A = \sigma_1 u_1 v_1^\mathsf{T}\) exactly.
Solution. For \(A = \begin{pmatrix} 1 & 2 \\ 2 & 4 \end{pmatrix}\), find \(\sigma_1, u_1, v_1^\mathsf{T}\) exactly.
\[ \begin{pmatrix} 1 & 2 \\ 2 & 4 \end{pmatrix} \begin{pmatrix} 1 & 2 \\ 2 & 4 \end{pmatrix} = \begin{pmatrix} 5 & 10 \\ 10 & 20 \end{pmatrix} \]
\[ \begin{aligned} (5 - \lambda)(20 - \lambda) - 100 &= 0 \\[6pt] \lambda^2 - 25\lambda + 100 - 100 &= 0 \\[6pt] \lambda(\lambda - 25) &= 0 \end{aligned} \qquad\qquad \begin{aligned} \lambda_1 &= 25 & \boxed{\;\sigma_1 = 5\;} \\[6pt] \lambda_2 &= 0 & \sigma_2 &= 0 \end{aligned} \]
\[ \lambda_1 \;\Longrightarrow\; \begin{pmatrix} 1 \\ 2 \end{pmatrix} \]
Eigenvector for \(\lambda_1\), by row reduction:
\[ \begin{pmatrix} -20 & 10 \\ 10 & -5 \end{pmatrix} \begin{pmatrix} x_1 \\ x_2 \end{pmatrix} = \begin{pmatrix} 0 \\ 0 \end{pmatrix} \qquad\longrightarrow\qquad \begin{pmatrix} 0 & 0 \\ 1 & -\tfrac{1}{2} \end{pmatrix} \qquad\Longrightarrow\qquad x_1 = \tfrac{1}{2}x_2 \]
\[ v_1 = \frac{1}{\sqrt5}\begin{pmatrix} 1 \\ 2 \end{pmatrix} = \begin{pmatrix} 1/\sqrt5 \\ 2/\sqrt5 \end{pmatrix}, \qquad \boxed{\;v_1^\mathsf{T} = \begin{pmatrix} 1/\sqrt5 & 2/\sqrt5 \end{pmatrix}\;} \]
\[ \boxed{\; u_1 = \frac{Av_1}{\sigma_1} = \frac{1}{5}\begin{pmatrix} 5/\sqrt5 \\ 10/\sqrt5 \end{pmatrix} = \begin{pmatrix} 1/\sqrt5 \\ 2/\sqrt5 \end{pmatrix} \;} \]
\[ \begin{aligned} A = \sigma_1 u_1 v_1^\mathsf{T} &= \begin{pmatrix} 1/\sqrt5 \\ 2/\sqrt5 \end{pmatrix} \begin{pmatrix} 5/\sqrt5 & 10/\sqrt5 \end{pmatrix} \\[6pt] &= \begin{pmatrix} 5/5 & 10/5 \\ 10/5 & 20/5 \end{pmatrix} = \begin{pmatrix} 1 & 2 \\ 2 & 4 \end{pmatrix} \end{aligned} \]
Exercise 13.3. [Proof, \(\star\)] Prove that for symmetric PSD \(A\), the singular values equal the eigenvalues and one may take \(u_i = v_i\). Then show by example (Exercise 13.1!) that for symmetric \(A\) with a negative eigenvalue, singular values are the absolute values of eigenvalues.
Proof. Prove for symmetric PSD \(A\), \(\sigma_i\) equal \(\lambda_i\) and \(u_i = v_i\). \(A\) is \(n \times n\).
By the spectral theorem, note \(A\) has all real eigenvalues and they are non-negative, \(A = Q\Lambda Q^\mathsf{T}\). So let \(V^\mathsf{T} = Q^\mathsf{T}\), let \(\Sigma = \Lambda\), and let \(U = Q\). Then
\[ A = Q\Lambda Q^\mathsf{T} = U\Lambda V^\mathsf{T}, \]
so the spectral decomposition of \(A\) is also its singular value decomposition, so \(\sigma_i = \lambda_i\) and \(u_i = v_i\) for all \(i = 1, \dots, n\). \(\square\)
Note if \(A\) is symmetric but not PSD, \(\sigma_i = |\lambda_i|\) but \(\lambda_i\) could be negative so they may not be equal. See Exercise 13.1 as an example of this.
Exercise 13.4. [Proof] Using Corollary 13.4(b) applied to \(A\) and to \(A^{-1}\) (square invertible case), show \(\|Ax\|/\|x\|\) ranges over \([\sigma_n, \sigma_1]\), and interpret \(\kappa = \sigma_1/\sigma_n\) as the worst-case ratio by which \(A\) distorts relative lengths. (\(\kappa\) is the condition number, and it governs how much rounding error a linear solve can amplify.)
Proof. Using \(\|Av\| \le \sigma_1\|v\|\) for all \(v\), with equality at \(v = v_1\), applied to a square invertible matrix \(A\) and its inverse \(A^{-1}\).
Note \(\sigma_1 \ge \sigma_2 \ge \cdots \ge \sigma_n\), and \(\sigma_i > 0\) since \(A\) is invertible.
\[ \frac{\|Ax\|}{\|x\|} \le \frac{\sigma_1\|x\|}{\|x\|} = \sigma_1 \]
So we’ve shown the right bound holds.
For the left bound consider the SVD of \(A\), \(U\Sigma V^\mathsf{T}\). Note \(\Sigma\) is a full rank diagonal matrix whose \(\sigma_1, \dots, \sigma_n > 0\) since \(A\) is invertible. Note
\[ A^{-1} = (U\Sigma V^\mathsf{T})^{-1} = (V^\mathsf{T})^{-1}\Sigma^{-1}U^{-1}, \]
and \(U^{-1} = U^\mathsf{T}\) and \((V^\mathsf{T})^{-1} = V\) because \(U, V\) orthogonal. Thus \(A^{-1} = V\Sigma^{-1}U^\mathsf{T}\), and for that SVD we can see its singular values are the inverse of the singular values in \(A\), so \(\sigma_1^{-1} \le \sigma_2^{-1} \le \cdots \le \sigma_n^{-1}\), and
\[ \frac{\|A^{-1}y\|}{\|y\|} \le \frac{\sigma_n^{-1}\|y\|}{\|y\|} = \sigma_n^{-1}. \]
Let \(y = Ax\). Then
\[ \frac{\|A^{-1}(Ax)\|}{\|Ax\|} = \frac{\|x\|}{\|Ax\|} \le \sigma_n^{-1} \quad\Longrightarrow\quad \sigma_n\|x\| \le \|Ax\| \quad\Longrightarrow\quad \frac{\|Ax\|}{\|x\|} \ge \sigma_n \]
So
\[ \sigma_n \le \frac{\|Ax\|}{\|x\|} \le \sigma_1, \]
as desired. \(\square\)
\[ \kappa = \frac{\sigma_1}{\sigma_n}, \qquad 1 \le \kappa < \infty \]
So \(\kappa = 1\) no length distortion, but very large \(\kappa\) means huge distortion, so numerical stability issues in algorithms trying to compute inverses or solve equalities.
Both endpoints are attained, which is what makes the range the full interval rather than just a pair of bounds: at \(x = v_1\) the corollary’s equality case gives \(\|Av_1\|/\|v_1\| = \sigma_1\), and at \(x = v_n\) we have \(Av_n = \sigma_n u_n\) with \(u_n\) a unit vector, so \(\|Av_n\|/\|v_n\| = \sigma_n\).