# PCA with SVD exercice 23.5 understanding machine learning

In understanding machine learning Shai Sharev-Scwartz and Shai Ben-David exercice 23.5.

I would like to use SVD to minimize : $$\text{argmin}_{W \in \mathbb{R}^{n,d}, U \in \mathbb{R}^{d,n}}{\text{ }\sum_{i=1}^{n} \| x_{i} - UWx_{i} \|_{2}^{2} } = \text{argmin}_{W \in \mathbb{R}^{n,d}, U \in \mathbb{R}^{d,n}}{\text{ } \| X - UWX \|_{F}^{2} }$$

Do you know how to do that or do you have a reference for a proof ?

What did I do ? I'm trying to use low rank theorem $$\text{arg}\min_{B ; \text{ rank}(B) \le k < \text{rank}(X) } \|X - B\|_{F}^{2} = \sum_{i=1}^{k} \sigma_{i} u_{i} v_{i}^{T}$$ When the SVD of $$X$$ is $$\sum_{i=1}^{r} \sigma_{i} u_{i} v_{i}^{T}$$

## 1 Answer

Here is a solution if some are interested in : let's $$X = (x_{1},...,x_{m}) \in M_{d,m}(\mathbb{R})$$ it's SVD is $$\sum_{i=1}^{r} \sigma_{i}u_{i}v_{i}^{T}$$ with $$r$$ the rank of $$X$$ and $$u_{i}, v_{i}$$ two orthonormal famillies of $$\mathbb{R}^{d}$$ and $$\mathbb{R}^{m}$$. We have $$\sum_{i=1}^{m} \| x_{i} - UWx_{i} \|_{2}^{2} = \| X - UW X \|^{2}_{F}$$ with $$F$$ the Frobenius norm.

Now we see that the rank of $$U$$ is $$\le n$$ and we know that $$\text{argmin}_{B ; \text{ rank }(B) \le k}{\| X - B \|_{F}^{2} } = \sum_{i=1}^{k} \sigma_{i}u_{i}v_{i}^{T}$$ We can understand the problem is solved if we can find $$U$$ and $$W$$ such that $$UW = \sum_{i=1}^{n} u_{i}u_{i}^{T}$$.

So the solution is $$U$$ the matrix with columns $$u_{1},…,u_{n}$$ and $$W=U^{T}$$.

Noticed you didn't use $$v_{i}$$.