Week 3

Problem 1

In lecture we computed both matrix norms from the singular values of \(\bfA\in\Rbb^{m\times n}\): if \(\bfA\) has rank \(r\) and singular values \(\sigma_1\geq\cdots\geq\sigma_r>0\), then \[ \|\bfA\|_2=\sigma_1, \qquad \|\bfA\|_F=\left(\sum_{i=1}^r\sigma_i^2\right)^{1/2}, \] by the spectral norm is the largest singular value and the Frobenius norm and all the singular values. In this problem you will use these to compare the two norms.

  1. Show that \(\|\bfA\|_2\leq\|\bfA\|_F\).
  2. Show that \(\|\bfA\|_F\leq\sqrt{r}\,\|\bfA\|_2\).
  3. Compute both norms for the \(n\times n\) identity matrix \(\bfI_n\). Which of the two bounds is tight here, and by how much do the two norms differ as \(n\) grows?

Problem 2

In lecture we collected a few basic facts about the trace (properties of the trace). Recall that \(\bfQ\in\Rbb^{d\times d}\) is orthogonal if \(\bfQ^\top\bfQ=\bfQ\bfQ^\top=\bfI_d\).

  1. Let \(\bfQ\in\Rbb^{d\times d}\) be orthogonal and \(\bfM\in\Rbb^{d\times d}\). Show that \[ \operatorname{tr}(\bfQ^\top\bfM\bfQ)=\operatorname{tr}(\bfM). \] Hint: use the cyclic property of the trace.
  2. Let \(\bfA\in\Rbb^{m\times n}\), and let \(\bfQ\in\Rbb^{m\times m}\) and \(\bfZ\in\Rbb^{n\times n}\) be orthogonal. Show that \[ \|\bfQ\bfA\|_F=\|\bfA\|_F=\|\bfA\bfZ\|_F. \]
  3. Use part 2 together with the full SVD \(\bfA=\bfU\Sigma\bfV^\top\), in which \(\bfU\in\Rbb^{m\times m}\) and \(\bfV\in\Rbb^{n\times n}\) are orthogonal and \(\Sigma\in\Rbb^{m\times n}\) is zero off its main diagonal, to give a proof that \(\|\bfA\|_F=\left(\sum_{i=1}^r\sigma_i^2\right)^{1/2}\).

Problem 3

At the end of lecture we stated that minimizing reconstruction error and maximizing retained variance are the same problem (minimum error equals maximum retained variance). In this problem you will prove the identity behind that statement. Let \(\bfX\in\Rbb^{n\times d}\) be the centered data matrix with rows \((\bfx_i-\bar{\bfx})^\top\), let \(S\subseteq\Rbb^d\) be a subspace, and let \(\bfP_S\) be the orthogonal projection onto \(S\).

  1. Let \(\bfx\in\Rbb^d\). Show that \(\bfP_S\bfx\) and \(\bfx-\bfP_S\bfx\) are orthogonal.
  2. Show that \[ \operatorname{TV} =\operatorname{TV}(S)+\frac1n\Ecal(S), \] where \(\operatorname{TV}\) and \(\operatorname{TV}(S)\) are the total and retained variance and \(\Ecal(S)\) is the reconstruction error.

Problem 4

In this problem you will see the SVD as a statement about ellipses. Keep the ellipse example open while you work.

Let \(\bfA\in\Rbb^{2\times2}\) have rank \(2\) and SVD \(\bfA=\sigma_1\bfu_1\bfv_1^\top+\sigma_2\bfu_2\bfv_2^\top\), with \(\sigma_1\geq\sigma_2>0\).

  1. Show that \(\bfA\) maps the unit circle into an ellipse: \[ \{\bfA\bfx:\|\bfx\|_2=1\} \subseteq\left\{\bfy\in\Rbb^2:\frac{(\bfu_1^\top\bfy)^2}{\sigma_1^2}+\frac{(\bfu_2^\top\bfy)^2}{\sigma_2^2}=1\right\}. \] This is the ellipse with semi-axes \(\sigma_1\bfu_1\) and \(\sigma_2\bfu_2\). (In fact the two sets are equal, so \(\bfA\) maps the unit circle onto the ellipse, but you do not need to show this.) Hint: use \(\bfA\) in singular-vector coordinates.
  2. Which unit vectors \(\bfx\) are sent to the ends \(\pm\sigma_1\bfu_1\) of the long axis?
  3. Explain how this picture shows that \(\|\bfA\|_2=\sigma_1\).

Problem 5

Important

This problem will not be asked as is on a quiz or exam (yet). It is here so you can see a limitation of the SVD for yourself.

Read through the SVD failure example, which compares the point clouds \(y=x+\varepsilon\) and \(y=x^2+\varepsilon\). Both are essentially one-dimensional curves, but the SVD only recognizes the first one as one-dimensional. As you read, look at how the principal directions, the explained variance ratio \(R_1\), and the rank-1 reconstruction differ between the two clouds.