Chapter 10: Singular Value Decomposition

Topics: computing SVD, low-rank approximation, best direction, principal components analysis

Problems below are collected from past exams; each links back to its full exam. Solutions are in the dropdowns.

Problems

FA25 Final · Problem 12
WN26 Final · Problem 12
SP26 Final · Problem 13

FA25 Final · Problem 12 12 pts 🎥 Walkthrough

Suppose $\tilde X$ is a $24 \times 3$ matrix whose columns are mean-centered (i.e. have a mean of 0). Let $\tilde X = U \Sigma V^T$ be the singular value decomposition of $\tilde X$ , where

\tilde X = U \underbrace{\begin{bmatrix} 12 & 0 & 0 \\\\ 0 & 2 & 0 \\\\ 0 & 0 & 0 \\\\\vdots & \vdots & \vdots \end{bmatrix}}_{\Sigma} \underbrace{\begin{bmatrix} 1/\sqrt{10} & 3/\sqrt{10} & 0 \\\\ \cdots & \vec v_2^T & \cdots \\\\ 0 & 0 & 1 \end{bmatrix}}_{V^T}

2 pts Find $\text{rank}(\tilde X)$ . Give your answer as an integer with no variables.

$\text{rank}(\tilde X) = \_\_\_\_\_\_$

Solution

The rank of a matrix is equal to its number of non-zero singular values. Here, the singular values are 12, 2, and 0, so

\text{rank}(\tilde X) = \boxed{2}.

3 pts It is possible to find $\vec v_2^T$ , the second row of $$V^T$$ , solely using the information provided (without knowing any of the values in $\tilde X$ ). In one English sentence, explain how to find it.

Solution

Since $$V$$ is orthogonal, the rows of $$V^T$$ must be orthonormal, so $\vec v_2^T$ is the unit vector orthogonal to both $\begin{bmatrix} 1/\sqrt{10} \\ 3/\sqrt{10} \\ 0 \end{bmatrix}$ and $\begin{bmatrix} 0 \\ 0 \\ 1 \end{bmatrix}$ .

2 pts True or False: There exists some vector $\vec z \in \mathbb{R}^{24}$ such that $\tilde X \tilde X^T \vec z = 2 \vec z$ .

True False Impossible to tell

Solution

True False Impossible to tell

This is False. The eigenvalues of $\tilde X \tilde X^T$ are the squares of the singular values of $\tilde X$ , so they are $$144$$ , $$4$$ , and $$0$$ . Since 2 is not an eigenvalue of $\tilde X \tilde X^T$ , no such vector $\vec z$ exists.

5 pts What is the largest possible variance of the components of $\tilde X \vec w$ , where $\vec w \in \mathbb{R}^3$ is a unit vector? Select one of the answers below, then justify your answer in the box provided.

Answer:
$$1$$ $$2$$ $$6$$ $$12$$ $$24$$ $$144$$
Justify your answer in the box below.

Solution
$$1$$ $$2$$ $$6$$ $$12$$ $$24$$ $$144$$
Because the columns of $\tilde X$ are mean-centered, the variance of the components of $\tilde X\vec w$ is
$\frac{1}{n}\|\tilde X\vec w\|^2 = \frac{1}{24}\|\tilde X\vec w\|^2$
This is maximized when $\vec w$ is the first right singular vector ( $\vec v_1$ ), and the maximum value is
$\frac{\sigma_1^2}{24} = \frac{12^2}{24} = \frac{144}{24} = 6$
So the largest possible variance is $\boxed{6}$ .

WN26 Final · Problem 12 12 pts

From WN26 Final

Suppose $\tilde X$ is an $n \times 2$ matrix whose columns are mean-centered (i.e. have a mean of 0). Furthermore, suppose

\tilde X^T \tilde X = \begin{bmatrix} 3 & 2 \\\\ 2 & 6 \end{bmatrix}

Note that $\tilde X^T \tilde X$ has eigenvalues of $$7$$ and $$2$$ . Let $\tilde X = U \Sigma V^T$ be the singular value decomposition of $\tilde X$ , and let $\vec v_1$ be the first column of $$V$$ (not $$V^T$$ ).

4 pts What is $\vec v_1$ ? Give your answer as a vector with no variables. If there are multiple correct answers, you only need to provide one.

$\vec v_1 = \_\_\_\_\_\_$

Solution

The first right singular vector, $\vec v_1$ , is an eigenvector of $\tilde X^T\tilde X$ corresponding to the largest eigenvalue, $$7$$ . So we solve

\begin{bmatrix} 3 & 2\\\\ 2 & 6 \end{bmatrix} \begin{bmatrix} a\\\\b \end{bmatrix} = 7 \begin{bmatrix} a\\\\b \end{bmatrix}

The first row gives

3a+2b=7a \implies b=2a

One unit vector in this direction is

\vec v_1 = \boxed{\frac{1}{\sqrt 5}\begin{bmatrix}1\\\\2\end{bmatrix}}

3 pts Suppose the variance of the second principal component is $$1/15$$ . What is $$n$$ , the number of rows in $\tilde X$ ? Give your answer as a number with no variables.

$n = \_\_\_\_\_\_$

Solution

The variance of the second principal component is

\frac{\sigma_2^2}{n}

Since $\sigma_2^2$ is the second-largest eigenvalue of $\tilde X^T\tilde X$ , we have $\sigma_2^2=2$ . So

\frac{2}{n}=\frac{1}{15}

This gives

n=\boxed{30}

5 pts Suppose that $\vec u_2$ is the second column of $$U$$ , corresponding to the singular value $\sigma_2$ , in the singular value decomposition of $\tilde X$ .

Prove that $\tilde X \vec v_1$ and $\sigma_2 \vec u_2$ are orthogonal. You do not need to re-prove any facts about the singular value decomposition, but you should state any facts you use.

Solution

Using the SVD relationship,

\tilde X\vec v_1 = \sigma_1\vec u_1

(\tilde X\vec v_1)^T(\sigma_2\vec u_2) = (\sigma_1\vec u_1)^T(\sigma_2\vec u_2) = \sigma_1\sigma_2 \vec u_1^T\vec u_2

The columns of $$U$$ are orthonormal, so $\vec u_1^T\vec u_2=0$ . Therefore,

(\tilde X\vec v_1)^T(\sigma_2\vec u_2)=0

This proves that $\tilde X\vec v_1$ and $\sigma_2\vec u_2$ are orthogonal.

SP26 Final · Problem 13 12 pts

From SP26 Final

Let $\tilde X$ be a $4 \times 2$ centered matrix (i.e. in which each column has a mean of 0) with columns $\vec a$ and $\vec b$ :

\tilde X = \begin{bmatrix} \mid & \mid \\\\ \vec a & \vec b \\\\ \mid & \mid \end{bmatrix}

Suppose $\tilde X = U \Sigma V^T$ is the singular value decomposition of $\tilde X$ , $\vec v_1 = \begin{bmatrix}3/5\\4/5\end{bmatrix}$ is the first column of $$V$$ , and $\sigma_1 = 10$ is the largest singular value.

3 pts How many possible vectors are there for $\vec v_2$ , the second column of $$V$$ ?

1 2 3 4 infinitely many

\vec v_2

’s are possible

Solution

1 2 3 4 infinitely many

\vec v_2

’s are possible

Since $$V$$ is an orthogonal matrix, its columns must be unit vectors that are orthogonal to each other. In $\mathbb{R}^2$ , there are exactly two unit vectors orthogonal to $\begin{bmatrix}3/5\\4/5\end{bmatrix}$ , namely $\begin{bmatrix}-4/5\\3/5\end{bmatrix}$ and $\begin{bmatrix}4/5\\-3/5\end{bmatrix}$ . So there are two possible vectors for $\vec{v}_2$ .

5 pts Write $\vec u_1$ , the first column of $$U$$ , as a linear combination of the columns of $\tilde X$ . Show your work, and fill in each box with a number with no variables.

Solution

Recall that the key relationship linking the first column of $$U$$ and the first column of $$V$$ in $\tilde X = U \Sigma V^T$ is

\tilde{X}\vec{v}_1=\sigma_1\vec{u}_1

This means

\vec{u}_1=\frac{1}{\sigma_1}\tilde{X}\vec{v}_1

Since the columns of $\tilde{X}$ are $\vec{a}$ and $\vec{b}$ ,

\tilde{X}\vec{v}_1 = \tilde{X}\begin{bmatrix}3/5\\\\4/5\end{bmatrix} = \frac{3}{5}\vec{a}+\frac{4}{5}\vec{b}

and since $\sigma_1=10$ ,

\vec{u}_1 = \frac{1}{10}\left(\frac{3}{5}\vec{a}+\frac{4}{5}\vec{b}\right) = \frac{3}{50}\vec{a}+\frac{2}{25}\vec{b}

4 pts Given the information above, what is the maximum possible variance of principal component $$2$$ ? Give your answer as a number with no variables.

maximum possible variance of principal component $$2$$ = ______

Solution

Chapter 10.4 tells us that the variance of principal component $$j$$ is

\frac{\sigma_j^2}{n}

We also know that the singular values are sorted from largest to smallest, so $\sigma_1 \geq \sigma_2$ . So, the variance of principal component $$2$$ , $\frac{\sigma_2^2}{n}$ , is at most equal to the variance of principal component $$1$$ , $\frac{\sigma_1^2}{n}$ .

Therefore, the maximum possible variance of principal component $$2$$ is the variance of principal component $$1$$ :

\frac{\sigma_1^2}{n}=\frac{10^2}{4}=25