# Item VII

Let $X \in \mathbb{R}^{m \times n}$ with $m \gg n$. Its reduced singular value decomposition is $U \Sigma V^*$ ($X = U \Sigma V^*$). Compute the reduced singular value decomposition of the following matrix $U \Sigma V^* (I - \vec{v}_1 \vec{v}_1^*)$, where $v_1$ is the first column of $V$ and $I$ is the identity matrix. In summary, you need to find $\tilde{U}\tilde{\Sigma}\tilde{V}^*$ such that its product give you $U \Sigma V^* (I - \vec{v}_1 \vec{v}_1^*)$. 

*Hint: This new SVD dependes on the original SVD!*

---

We make
$$
U \Sigma V^* (I - \vec{v}_1 \vec{v}_1^*) = U \Sigma (V^* - V^*\vec{v}_1 \vec{v}_1^*) \,.
$$
Then, we see that
$$
\vec{v}_1 \vec{v}_1^* = \begin{bmatrix}
v_{1,1} \vec{v}_1 \, | \, v_{2,1} \vec{v}_1 | \dots | \, v_{n,1} \vec{v}_1
\end{bmatrix}
$$
and then
$$
V^* \vec{v}_1 \vec{v}_1^* = \begin{bmatrix}
\vec{v}_1^*
\\ \hline \vec{v}_2^*
\\ \hline \vdots
\\ \hline \vec{v}_n^*
\end{bmatrix} \begin{bmatrix}
v_{1,1} \vec{v}_1 \, | \, v_{2,1} \vec{v}_1 | \dots | \, v_{n,1} \vec{v}_1
\end{bmatrix}
$$
Because the $\vec{v}_i$ are orthonormal, this results in:
$$
V^* \vec{v}_1 \vec{v}_1^* = \begin{bmatrix}
v_{1,1} & v_{2,1} & \dots & v_{n,1}
\\ 0 & 0 & \dots & 0
\\ \vdots & \vdots & \ddots & \vdots
\\ 0 & 0 & \dots & 0
\end{bmatrix} = \begin{bmatrix}
\vec{v}_1
\\ \hline \vec{0}
\\ \hline \vdots
\\ \hline \vec{0}
\end{bmatrix}
$$
and
$$
V^* - V^*\vec{v}_1 \vec{v}_1^* =
\begin{bmatrix}
\vec{0}
\\ \hline \vec{v}_2^*
\\ \hline \vdots
\\ \hline \vec{v}_n^*
\end{bmatrix}
$$

---

Let's define the operator $E$ of dimensions $m\times m$ that raises the columns of a matrix 1 position and sends the first one to the last position (let's call that a *circulation*):
$$
E = \begin{bmatrix}
0 & 1 & 0 & \dots & 0 & 0
\\  0 & 0 & 1 & \dots & 0 & 0
\\  \vdots & \vdots & \vdots & \ddots & \vdots & \vdots
\\  0 & 0 & 0 & \dots & 0 & 1
\\  1 & 0 & 0 & \dots & 0 & 0
\end{bmatrix}
$$
We can see that:
$$
E^{-1} = \begin{bmatrix}
 0 & 0 & \dots & 0 & 1
\\ 1 & 0  & \dots & 0 & 0
\\  0 & 1 & \dots & 0 & 0
\\  \vdots & \vdots & \ddots & \vdots & \vdots
\\  0 & 0 & \dots & 1 & 0
\\  0 & 0 & \dots & 0 & 1
\end{bmatrix}
$$
Notice that multiplying by $E^{-1}$ on the right is equivalent to circulate the **columns** of a matrix.

---

If we multiply $(V^* - V^*\vec{v}_1 \vec{v}_1^*)$ by $U \Sigma$ on the left to get our matrix:
$$
U\Sigma(V^* - V^*\vec{v}_1 \vec{v}_1^*) =
U \begin{bmatrix}
\Sigma_1 \vec{0}
\\ \hline \Sigma_2 \vec{v}_2^*
\\ \hline \vdots
\\ \hline \Sigma_n \vec{v}_n^*
\\ \hline \vec{0}
\\ \hline \vdots
\\ \hline \vec{0}
\end{bmatrix} =
U \begin{bmatrix}
0 \cdot \vec{v}_1^*
\\ \hline \Sigma_2 \vec{v}_2^*
\\ \hline \vdots
\\ \hline \Sigma_n \vec{v}_n^*
\\ \hline \vec{0}
\\ \hline \vdots
\\ \hline \vec{0}
\end{bmatrix}
$$
$$
= U E^{-1} E\begin{bmatrix}
0 \cdot \vec{v}_1^*
\\ \hline \Sigma_2 \vec{v}_2^*
\\ \hline \vdots
\\ \hline \Sigma_n \vec{v}_n^*
\\ \hline \vec{0}
\\ \hline \vdots
\\ \hline \vec{0}
\end{bmatrix}
= U E^{-1}
\begin{bmatrix}
\Sigma_2 \vec{v}_2^*
\\ \hline \vdots
\\ \hline \Sigma_n \vec{v}_n^*
\\ \hline \vec{0}
\\ \hline \vdots
\\ \hline \vec{0}
\\ \hline 0 \cdot \vec{v}_1^*
\end{bmatrix}
$$
$$
= U E^{-1} \begin{bmatrix}
\Sigma_2 & 0 & \dots & 0 & 0
\\ 0 & \Sigma_3 & \dots & 0 & 0
\\ \vdots & \vdots & \ddots & \vdots & \vdots
\\ 0 & 0 & \dots & \Sigma_n & 0
\\ 0 & 0 & \dots & 0 & 0
\\ \vdots & \vdots & \ddots & \vdots & \vdots
\\ 0 & 0 & \dots & 0 & 0
\end{bmatrix}
\begin{bmatrix}
\vec{v}_2^*
\\ \hline \vdots
\\ \hline \vec{v}_n^*
\\ \hline \vec{v}_1^*
\end{bmatrix}
$$
$$
= \underbrace{\begin{bmatrix}
\vec{u}_2 | \cdots | \vec{u}_m | \vec{u}_1 
\end{bmatrix}}_{\tilde{U}}
\underbrace{\begin{bmatrix}
\Sigma_2 & 0 & \dots & 0 & 0
\\ 0 & \Sigma_3 & \dots & 0 & 0
\\ \vdots & \vdots & \ddots & \vdots & \vdots
\\ 0 & 0 & \dots & \Sigma_n & 0
\\ 0 & 0 & \dots & 0 & 0
\\ \vdots & \vdots & \ddots & \vdots & \vdots
\\ 0 & 0 & \dots & 0 & 0
\end{bmatrix}}_{\tilde{E}}
\underbrace{\begin{bmatrix}
\vec{v}_2^*
\\ \hline \vdots
\\ \hline \vec{v}_n^*
\\ \hline \vec{v}_1^*
\end{bmatrix}}_{\tilde{V}^*}
$$
Which is equivalent to the SVD of $U\Sigma V(I-\vec{v}_1\vec{v}_1^*)$.

---

# Item VIII

Let $X \in \mathbb{R}^{m \times n}$ with $m \gg n$, prove that maximum of the following maximization problem:
\begin{align}
\max_{w \in \mathbb{R}^n} &\qquad ||X \vec{w} ||^2_2
\\ \text{subject to} &\qquad ||\vec{w}||^2_2 = 1
\end{align}
is obtained for $\vec{w} = \vec{v}_1$, where $\vec{v}_1$ is the first column of $V$ matrix from the singular value decomposition of $X$, i.e. $X = U \Sigma V^*$.

---

We can write
$$
\vec{w} = \sum_{i=1}^n \alpha_i \vec{v}_i
$$

We have that
$$
\begin{align}
X\vec{w} &= U \Sigma V^* \vec{w}
\\ &= U
\begin{bmatrix}
\Sigma_1 \vec{v}_1^*
\\ \hline \Sigma_2 \vec{v}_2^*
\\ \hline \vdots
\\ \hline \Sigma_n \vec{v}_n^*
\\ \hline \vec{0}
\\ \hline \vdots
\\ \hline \vec{0}
\end{bmatrix} \vec{w}
= U
\begin{bmatrix}
\Sigma_1 \alpha_1 \vec{v}_1^*\vec{v}_1
\\ \hline \Sigma_2 \alpha_2 \vec{v}_2^* \vec{v}_2
\\ \hline \vdots
\\ \hline \Sigma_n \alpha_n \vec{v}_n^* \vec{v}_n
\\ \hline \vec{0}
\\ \hline \vdots
\\ \hline \vec{0}
\end{bmatrix}
= U
\begin{bmatrix}
\Sigma_1 \alpha_1
\\ \hline \Sigma_2 \alpha_2
\\ \hline \vdots
\\ \hline \Sigma_n \alpha_n
\\ \hline \vec{0}
\\ \hline \vdots
\\ \hline \vec{0}
\end{bmatrix}
\end{align}
$$
U doens't change the norm 2 of this vector, since it is unitary.
$$
||X \vec{w}||_2^2 = \sum_{i=1}^{n} \Sigma_{i}^2 \alpha_i^2
$$
since there's the restriction that
$$
||\vec{w}||_2^2 = \sum_{i=1}^{n} \alpha_i^2 \quad \leq 1
$$
is clear that the previous expression is maximized when
$$
a_i^2 = \begin{cases}
1 & i=1
\\ 0 & i\neq 1
\end{cases}
$$
as $\Sigma_1^2 \geq \Sigma_i^2 \,\forall i$.

So $\vec{w} = 1 \cdot \vec{v}_1$ maximizes $||X \vec{w}||_2^2$. $\, \square$

---

# Item IX

Repeat the same procedure from the previous questions but for the following maximization problem:
\begin{align}
\max_{w \in \mathbb{R}^n} &\qquad ||X (I - \vec{v}_1 \vec{v}_1^*) \vec{w} ||^2_2
\\ \text{subject to} &\qquad ||\vec{w}||^2_2 = 1
\end{align}

---


We use the SVD for $X (I - \vec{v}_1 \vec{v}_1^*)$ that we found on Item VII:

$$
X (I - \vec{v}_1 \vec{v}_1^*) \vec{w} = \underbrace{\begin{bmatrix}
\vec{u}_2 | \cdots | \vec{u}_m | \vec{u}_1 
\end{bmatrix}}_{\tilde{U}}
\underbrace{\begin{bmatrix}
\Sigma_2 & 0 & \dots & 0 & 0
\\ 0 & \Sigma_3 & \dots & 0 & 0
\\ \vdots & \vdots & \ddots & \vdots & \vdots
\\ 0 & 0 & \dots & \Sigma_n & 0
\\ 0 & 0 & \dots & 0 & 0
\\ \vdots & \vdots & \ddots & \vdots & \vdots
\\ 0 & 0 & \dots & 0 & 0
\end{bmatrix}}_{\tilde{E}}
\underbrace{\begin{bmatrix}
\vec{v}_2^*
\\ \hline \vdots
\\ \hline \vec{v}_n^*
\\ \hline \vec{v}_1^*
\end{bmatrix}}_{\tilde{V}^*} \vec{w}
$$
If we write
$$
\vec{w} = \sum_{i=1}^n \alpha_i \vec{v}_i
$$
again, we have that
$$
\begin{align}
X (I - \vec{v}_1 \vec{v}_1^*) \vec{w} &= \tilde{U} \tilde{\Sigma} \tilde{V}^* \vec{w}
\\ &= \tilde{U}
\begin{bmatrix}
\Sigma_2 \vec{v}_2^*
\\ \hline \Sigma_3 \vec{v}_3^*
\\ \hline \vdots
\\ \hline \Sigma_n \vec{v}_n^*
\\ \hline \vec{0}
\\ \hline \vdots
\\ \hline \vec{0}
\end{bmatrix} \vec{w}
= \tilde{U}
\begin{bmatrix}
\Sigma_2 \alpha_2 \vec{v}_2^* \vec{v}_2
\\ \hline \vdots
\\ \hline \Sigma_n \alpha_n \vec{v}_n^* \vec{v}_n
\\ \hline \vec{0}
\\ \hline \vdots
\\ \hline \vec{0}
\end{bmatrix}
= \tilde{U}
\begin{bmatrix}
\Sigma_2 \alpha_2
\\ \hline \vdots
\\ \hline \Sigma_n \alpha_n
\\ \hline \vec{0}
\\ \hline \vdots
\\ \hline \vec{0}
\end{bmatrix}
\end{align}
$$
The norm of this vector is just
$$
\sum_{i=2}^{n} \Sigma_{i}^2 \alpha_i^2 
$$
as $\tilde{U}$ is unitary.

Again, under the restriction that
$$
||\vec{w}||_2^2 = \sum_{i=1}^{n} \alpha_i^2 \quad \leq 1
$$
we can see that the previous value is maximized when $\alpha_2= 1$ and thus, the other $\alpha_i$ are $0$. Since $\Sigma_{2} \geq \Sigma_{i} \, \forall (i>2)$, and $\Sigma_1$ doesn't add to the norm.

We have So $\vec{w} = 1 \cdot \vec{v}_2$ maximizes the given norm. $\, \square$


```python

```

e5ef6be4a106b66db8379bb4dcff9458ee6be93f
ipynb
Jupyter Notebook
t1_questions/item_07_08_09.ipynb
autopawn/cc5-works
63775574c82da85ed0e750a4d6978a071096f6e7
MIT
t1_questions/item_07_08_09.ipynb
autopawn/cc5-works
63775574c82da85ed0e750a4d6978a071096f6e7
MIT
t1_questions/item_07_08_09.ipynb
autopawn/cc5-works
63775574c82da85ed0e750a4d6978a071096f6e7
MIT
Qwen/Qwen-72B
1. YES
2. YES