2.7 Exercises

  1. There is a great Twitter thread on the SVD by Daniella Witten. Read it here.

  2. Let \(\bSigma\) be an arbitrary covariance matrix.

    • Show \(\bSigma\) is symmetric and positive semi-definite.
    • Give examples of both singular and non-singular covariance matrices.
    • What condition must the eigenvalues of a non-singular covariance matrix satisfy?



  1. Compute, by hand (but check your answer in R), the singular value decomposition (full and compact) of the following matrices.
    • \(\left(\begin{array}{cc}2&0\\0&-1\end{array} \right)\)
    • \(\left(\begin{array}{cc}1&0\\0&0\\0&0\end{array} \right)\)
  2. Let \[\bX=\left(\begin{array}{cc}1&1\\0&1\\1&0\end{array} \right)\]
    The eigen-decomposition of \(\bX^\top \bX\) is \[\bX^\top \bX =\frac{1}{\sqrt{2}}\left(\begin{array}{cc}1&-1\\1&1\end{array} \right) \left(\begin{array}{cc}3&0\\0&1\end{array} \right)\frac{1}{\sqrt{2}}\left(\begin{array}{cc}1&-1\\1&1\end{array} \right)^\top \] Use this fact to compute answer the following questions:
    • What are the singular values of \(\bX\)?
    • What are the right singular vectors of \(\bX\)?
    • What are the left singular vectors of \(\bX\)?
    • Give the compact SVD of \(\bX\). Check your answer, noting that the singular vectors are only specified up to multiplication by \(-1\)
    • Can you compute the full SVD of \(\bX\)?
    • What is the eigen-decomposition of \(\bX \bX^\top\)?
    • Find a generalised inverse of matrix \(\bX\).

  1. The SVD can be used to solve linear systems of the form \[\bA \bx = \by\] where \(\bA\) is a \(n\times p\) matrix, with compact SVD \(\bA = \bU \bSigma \bV^\top\).

    • If \(\bA\) is a square invertible matrix, show that \[\tilde{\bx} = \bV \bSigma^{-1} \bU^\top \by\] is the unique solution to \(\bA \bx = \by\), i.e., show that \(\bA^{-1} = \bV \bSigma^{-1} \bU^\top\).

    • If \(\bA\) is not a square matrix, then \(\bA^+ = \bV \bSigma^{-1} \bU^\top\) is a generalized inverse (not a true inverse) matrix, and \(\tilde{\bx}=\bA^+\by\) is still a useful quantity to consider as we shall now see. Let \(\bA=\left(\begin{array}{cc}1&1\\0&1\\1&0\end{array} \right)\) and \(\by = \left(\begin{array}{c}2\\1\\1\end{array} \right)\). Then \(\bA\bx=\by\) is an over-determined system in that there are 3 equations in 2 unknowns. Compute \(\tilde{\bx}=\bA^+\by\). Is this a solution to the equation?

    Note that you computed the svd for \(\bA\) in Q2.

    • Now suppose \(\by = \left(\begin{array}{c}1\\-1\\1\end{array} \right)\). There is no solution to \(\bA\bx=\by\) in this case as \(\by\) is not in the column space of \(\bA\). Prove that \({\tilde{\bx}} = \bA^+\by\) solves the least squares problem \[\tilde{\bx} = \arg\min_{\bx}||\by - \bA\bx||_2.\]

    Hint: You can either do this directly for this problem, or you can show that the least squares solution \((\bA^\top \bA)^{-1}\bA^\top \by=\tilde{\bx}\).

  2. Consider the system \[\bB\bx = \by \mbox{ with }\bB =\left(\begin{array}{ccc}1&0&1\\1&1&0\end{array} \right),\by = \left(\begin{array}{c}1\\1\end{array} \right).\] This is an underdetermined system, as there are 2 equations in 3 unknowns, and so there are an infinite number of solutions for \(\bx\) in this case.

    • Find the full SVD for \(\bB=\bU \bSigma \bV^\top\) (noting that \(\bB=\bA^\top\) for \(\bA\) from the previous question).
    • Compute \(\tilde{\bx}=\bB^+\by\), check it is a solution to the equation, and explain why \[\tilde{\bx}= \sum_{i=1}^r \bv_i \frac{\bu_i^\top \by}{\sigma_i}\] in general, where \(r\leq max(n,p)\) is the rank of \(\bB\), and write out \(\tilde{\bx}\) explicitly in this form for the given \(\bB\).
    • Consider \(\bx\) of the form \[\bx = \tilde{\bx} + \sum_{i=r+1}^p \alpha_i \bv_i\] and explain why any \(\bx\) of this form is also a solution to \(\bB\bx=\by\). Thus write out all possible solutions of the equation.
    • Prove that \(\tilde{\bx}\) is the solution with minimum norm, i.e., \(||\tilde{\bx}||_2 \leq ||\bx||_2\). Hint \(\bv_1, \ldots, \bv_p\) form a complete orthonormal basis for \(\mathbb{R}^p\).

  3. Prove proposition 2.4, namely that the eigenvalues of projection matrices are either 0 or 1. Show that \({\bf 1}_n\) is an eigenvector of \(\bH\). What is the corresponding eigenvalue? What are the remaining eigenvalues equal to?