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.

Show that \(\|\bfA\|_2\leq\|\bfA\|_F\).
Show that \(\|\bfA\|_F\leq\sqrt{r}\,\|\bfA\|_2\).
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?

Solution sketch

Every term of \(\sum_{i=1}^r\sigma_i^2\) is non-negative, so dropping all but the first, \[ \|\bfA\|_F^2=\sum_{i=1}^r\sigma_i^2\geq\sigma_1^2=\|\bfA\|_2^2. \] Taking square roots gives \(\|\bfA\|_2\leq\|\bfA\|_F\).
Bounding every term by the largest one instead, \[ \|\bfA\|_F^2=\sum_{i=1}^r\sigma_i^2\leq\sum_{i=1}^r\sigma_1^2 =r\sigma_1^2=r\|\bfA\|_2^2, \] and taking square roots gives \(\|\bfA\|_F\leq\sqrt{r}\,\|\bfA\|_2\).
Every singular value of \(\bfI_n\) is \(1\) and \(r=n\) (Homework 2, Problem 3), so \[ \|\bfI_n\|_2=1, \qquad \|\bfI_n\|_F=\sqrt{n}=\sqrt{r}\,\|\bfI_n\|_2. \] So the upper bound of part 2 is tight, while the lower bound of part 1 is strict for every \(n\geq2\). This happens because all the singular values are equal, so bounding each \(\sigma_i\) by \(\sigma_1\) in part 2 loses nothing. The gap between the norms is \(\sqrt{n}-1\), which grows without bound!

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\).

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.
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. \]
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}\).

Solution sketch

Taking \(\bfB=\bfQ^\top\) and \(\bfC=\bfM\bfQ\) in the cyclic property, \[ \operatorname{tr}(\bfQ^\top\bfM\bfQ) =\operatorname{tr}(\bfQ^\top(\bfM\bfQ)) =\operatorname{tr}((\bfM\bfQ)\bfQ^\top) =\operatorname{tr}(\bfM\bfI_d) =\operatorname{tr}(\bfM). \]
For the left factor, \(\bfQ^\top\bfQ=\bfI_m\) gives \[ \|\bfQ\bfA\|_F^2 =\operatorname{tr}\big((\bfQ\bfA)^\top\bfQ\bfA\big) =\operatorname{tr}(\bfA^\top\bfQ^\top\bfQ\bfA) =\operatorname{tr}(\bfA^\top\bfA) =\|\bfA\|_F^2. \] For the right factor, \(\|\bfA\bfZ\|_F^2=\operatorname{tr}(\bfZ^\top\bfA^\top\bfA\bfZ)=\operatorname{tr}(\bfA^\top\bfA)=\|\bfA\|_F^2\) by part 1 applied to \(\bfM=\bfA^\top\bfA\). Taking square roots gives the claim, since Frobenius norms are non-negative.
Applying part 2 twice, first with \(\bfQ=\bfU^\top\) and then with \(\bfZ=\bfV\), \[ \|\bfA\|_F=\|\bfU^\top\bfA\|_F=\|\bfU^\top\bfA\bfV\|_F=\|\Sigma\|_F, \] where \(\bfU^\top\bfA\bfV=\Sigma\) because \(\bfU^\top\bfU=\bfI_m\) and \(\bfV^\top\bfV=\bfI_n\). The only nonzero entries of \(\Sigma\) are the positive singular values \(\sigma_1,\ldots,\sigma_r\) on its main diagonal, so \(\|\Sigma\|_F^2=\sum_{i=1}^r\sigma_i^2\), and taking square roots gives the claim.

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\).

Let \(\bfx\in\Rbb^d\). Show that \(\bfP_S\bfx\) and \(\bfx-\bfP_S\bfx\) are orthogonal.
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.

Solution sketch

Using \(\bfP_S^\top=\bfP_S\) and then \(\bfP_S^2=\bfP_S\), \[ (\bfP_S\bfx)^\top(\bfx-\bfP_S\bfx) =\bfx^\top\bfP_S\bfx-\bfx^\top\bfP_S^2\bfx =\bfx^\top\bfP_S\bfx-\bfx^\top\bfP_S\bfx =0, \] so \(\bfP_S\bfx\) and \(\bfx-\bfP_S\bfx\) are orthogonal.
For any \(\bfx\in\Rbb^d\), the vectors \(\bfP_S\bfx\) and \(\bfx-\bfP_S\bfx\) are orthogonal by part 1 and sum to \(\bfx\), so the Pythagorean theorem gives \[ \|\bfx\|_2^2=\|\bfP_S\bfx\|_2^2+\|\bfx-\bfP_S\bfx\|_2^2. \] Apply this with \(\bfx=\bfx_i-\bar{\bfx}\) for each \(i=1,\ldots,n\), sum over \(i\), and divide by \(n\): \[ \underbrace{\frac1n\sum_{i=1}^n\|\bfx_i-\bar{\bfx}\|_2^2}_{\operatorname{TV}} =\underbrace{\frac1n\sum_{i=1}^n\|\bfP_S(\bfx_i-\bar{\bfx})\|_2^2}_{\operatorname{TV}(S)} +\frac1n\underbrace{\sum_{i=1}^n\|(\bfx_i-\bar{\bfx})-\bfP_S(\bfx_i-\bar{\bfx})\|_2^2}_{\Ecal(S)}. \]

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\).

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.
Which unit vectors \(\bfx\) are sent to the ends \(\pm\sigma_1\bfu_1\) of the long axis?
Explain how this picture shows that \(\|\bfA\|_2=\sigma_1\).

Solution sketch

Since \(\bfv_1,\bfv_2\) and \(\bfu_1,\bfu_2\) are orthonormal bases of \(\Rbb^2\), \(\bfA\) in singular-vector coordinates says that if \(\bfx=c_1\bfv_1+c_2\bfv_2\), then \(\bfA\bfx=\sigma_1c_1\bfu_1+\sigma_2c_2\bfu_2\) and \(\|\bfx\|_2^2=c_1^2+c_2^2\).

If \(\|\bfx\|_2=1\) and \(\bfy=\bfA\bfx\), then \(\bfu_i^\top\bfy=\sigma_ic_i\), so \[ \frac{(\bfu_1^\top\bfy)^2}{\sigma_1^2}+\frac{(\bfu_2^\top\bfy)^2}{\sigma_2^2}=c_1^2+c_2^2=1. \] (For the reverse inclusion, not required: if \(\bfy\) lies on the ellipse, set \(c_i=\bfu_i^\top\bfy/\sigma_i\) and \(\bfx=c_1\bfv_1+c_2\bfv_2\). Then \(\|\bfx\|_2^2=c_1^2+c_2^2=1\) and \(\bfA\bfx=(\bfu_1^\top\bfy)\bfu_1+(\bfu_2^\top\bfy)\bfu_2=\bfy\).)

In the coordinates \(s=\bfu_1^\top\bfy\), \(t=\bfu_2^\top\bfy\) the set is \(s^2/\sigma_1^2+t^2/\sigma_2^2=1\), the standard ellipse with semi-axes \(\sigma_1\) along \(\bfu_1\) and \(\sigma_2\) along \(\bfu_2\).
The ends \(\pm\sigma_1\bfu_1\) have \((c_1,c_2)=(\pm1,0)\), that is, \(\bfx=\pm\bfv_1\); likewise \(\bfx=\pm\bfv_2\) is sent to the ends \(\pm\sigma_2\bfu_2\) of the short axis.
Since \(\|\bfA\bfx\|_2^2=\sigma_1^2c_1^2+\sigma_2^2c_2^2\leq\sigma_1^2\) for unit \(\bfx\), the points of the ellipse furthest from the origin are the ends of the long axis, which by part 2 are the images of \(\pm\bfv_1\). So \(\|\bfA\|_2=\max_{\|\bfx\|_2=1}\|\bfA\bfx\|_2\) is the length \(\sigma_1\) of the long semi-axis. (The same argument in higher dimensions says \(\bfA\) maps the unit sphere onto an ellipsoid with semi-axes \(\sigma_i\bfu_i\).)

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.