0
$\begingroup$

The problem: Given a sequence $\left \{ x_i \right \}_{i=1}^N \subseteq \mathbb R^n$ we want to find the best "compression" of these vectors onto a $p$ dimensional affine space. This means, I want to decode each $x_i$ with $c_i \in \mathbb R^p$, as coordinates in the space $U \mathbb R^p + b$ where $U$ semi orthogonal $\mathbb R^{n\times p}$. Those have to minimize $$\sum_{i=1}^N\left \| x_i - (Uc_i +b) \right \|_2^2$$

Well, what I do know is that given a constant choice of affine space, the best $c_i$s are $$c_i = U^T (x_i -b)$$ plugging this in we get $$\sum_{i=1}^N \left \| (I-UU^T)(x_i- b) \right \|$$ The best choice for $b$ assuming constant $U$ is $\frac{1}{N}\sum_{i=1}^N x_i$, and by subtracting it from each $x_i$ we can assume w.l.o.g that $b=0$ and we want to minimize $$\left \| X-UU^T X\right \|_F^2\ \ \text{where}\ X=[x_1,\dots,x_N]$$ Since $UU^TX$ is at best rank $p$, I want to find the best $U$ using low rank approximation. That is, decomposing $X=U_X \Sigma V_X^T$ and deducing that $$UU^T X = U_X \Sigma_p V_X^T = \text{argmin}_{B,\ \text{rank}(B)\leq p}\left \| X-B\right \|_F^2$$ where $\Sigma_p$ is $\Sigma$ with only the first $p$ singular values. However, I cannot find a more compact way to simplify this and find $U$! The exercise says the optimal $U$ should be the first $p$ columns of $U_X$.

Iv'e seen many posts here regarding this subject, but they tackled this problem from different directions..

$\endgroup$
1
$\begingroup$

You've worked so much of the problems out it's not clear to me exactly what your issue is. Let me write out several things and hopefully answer your question in the process.

The Eckart-Young theorem states that for any matrix $X$ with singular values $\sigma_1 \ge \sigma_2 \ge \cdots$, the optimal rank-$p$ approximation to $X$ satisfies

$$ \min_{\hat{X} \in \mathbb{R}^{n\times N}} \|X - \hat{X}\|_F^2 = \sum_{j=p+1}^{\min(n,N)} \sigma_j^2. $$

Moreover, the minimizer $\hat{X}$ to this is the $p$-truncated singular value decomposition of $X$: that is, $\hat{X} = U_p \Sigma_p V_p^\top$ where $U_p$ and $V_p$ are the first $p$ columns of $U$ and $V$ and $\Sigma_p$ is the top left $p\times p$ submatrix of $\Sigma$ for $X = U\Sigma V^\top$ is a full SVD of $X$. Another way of obtaining the $p$-truncated singular value decomposition is to simply "zero out" the singular values in $\Sigma$ except for the first $p$. If we call $\hat\Sigma$ this zeroed out $\Sigma$, you can check by matrix-multiplication that $\hat{X} = U_p\Sigma_p V^\top_p = U\hat\Sigma V^\top$.

The optimal rank-$p$ approximation $\hat{X}$ is unique if $\sigma_p > \sigma_{p+1}$. All of this can be found in a proof of the Eckart-Young theorem, such as the one linked above.

A final question is: why does $U_pU_p^\top X = \hat{X}$ (or $U_XU_X^\top X = \hat{X}$ in your notation)? To show this, write the full SVD of $X$ in the form

$$ X = U\Sigma V^\top = \begin{bmatrix} U_p & U_p' \end{bmatrix} \begin{bmatrix} \Sigma_p & 0 \\ 0 & \Sigma_p' \end{bmatrix} \begin{bmatrix} V_p & V_p' \end{bmatrix}^\top. $$

For example, $U_p$ are the first $p$ columns of $U$ and $U_p'$ the remaining columns. Note that since the columns of $U$ are orthonormal, one see that $U_p^\top U_p = I$ and $U_p^\top U_p' = 0$. Thus, we have that

\begin{align} U_pU_p^\top X &= \begin{bmatrix} U_pU_p^\top U_p & U_pU_p^\top U_p' \end{bmatrix} \begin{bmatrix} \Sigma_p & 0 \\ 0 & \Sigma_p' \end{bmatrix} \begin{bmatrix} V_p & V_p' \end{bmatrix}^\top \\ &= \begin{bmatrix} U_p & 0 \end{bmatrix} \begin{bmatrix} \Sigma_p & 0 \\ 0 & \Sigma_p' \end{bmatrix} \begin{bmatrix} V_p & V_p' \end{bmatrix}^\top \\ &= U_p \Sigma_p V_p^\top \\ &= \hat{X}. \end{align}

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Thanks! the problem was figuring out the last part. Now I see that since $U_p^T U_p X = \hat{X}$ then $U_p$ must be the optimal $U$ for the subspace. exactly what I wanted! $\endgroup$ – Theorem Jun 3 at 6:41

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.