2
$\begingroup$

I am trying to understand the solution of the optimization problem in geometric PCA. In my lecture notes I have the following:

Given $$\{x_{1}, ..., x_n\}\in\mathbb{R}^{D}$$ we seek a low-dim representation $$\{y_1, ..., y_n\}\in\mathbb{R}^d$$ such that: $$x_i=Uy_i+\epsilon_i\ \ where\ \ U=[u_1, ..., u_d]\in\mathbb{R}^{D\times d}$$ So we have the following optimization problem: $$\underset{U,\ \{y_i\}}{min}\underset{i}{\sum}||x_i-Uy_i||^2\ \ s.t.\ U^TU=I_d\ \ \ \ \ \ (1)$$ And following Lagrangian: $$L=\underset{i}{\sum}||x_i-Uy_i||^2+Tr((I_d-U^TU)\Lambda)\ \ \ \ \ \ (2)\\ where\ \Lambda=\Lambda^T\ is\ a \ matrix\ of\ Langrangian\ multipliers$$ My first problem here is that I don't understand the trace representation. Since matrix U consists of orthonormal vectors I would write it like this: $$L=\underset{i}{\sum}||x_i-Uy_i||^2-\underset{i,\ j=1,\ i\neq\ j}{\sum}\lambda_{ij}u_i^Tu_j+\underset{i}{\sum}\lambda_{ii}(1-u_i^Tu_i)\ \ \ \ \ \ (3)$$

How do I get from (3) to (2)? I tried to write it with indices of each element in each matrix taking U to be 3x2, but is there an easier way to prove it?

After differentiation with respect to y we get: $$y_i=U^Tx_i$$ Then, in order to optimize over U we substitute y into (1) and we have: $$\underset{i}{\sum}||x_i-UU^Tx_i||^2\underset{(*)}{=}\underset{i}{\sum}x_i^T(I_D-UU^T)x_i\underset{(**)}{=}Tr((I_D-UU^T)XX^T)\ \ \ \ \ \ (4)$$ My second problem is that I don't understand these equalities in (4). For (*) I get: $$\underset{i}{\sum}||x_i-UU^Tx_i||^2=\underset{i}{\sum}x_i^T(I_D-UU^T)^2x_i$$ And the (**) I don't understand completely.

After substitution of y we obtain the optimization problem: $$\underset{U}{max}\ Tr(UU^TXX^T)\ s.t.\ U^TU=I_d\ \ \ \ \ \ (5)$$ for which Lagrangian is: $$L=Tr(U^TXX^TU)+Tr((I_d-U^TU)\Lambda)\ \ \ \ \ \ (6)$$ Differentiation with respect to U gives: $$\Lambda=U^TXX^TU$$ And then in my lecture notes I have the following:

From (1) and (2) the reconstruction error can be computed as: $$\epsilon=Tr((I_D-UU^T)XX^T)=\overset{D}{\sum}\lambda_i-\overset{d}{\sum}\lambda_i=\sum_{i=d+1}^{D}\lambda_i$$ So my third question(s) is why is this the error? Why eigenvalues of those eigenvectors that aren't included in a new low dimension represent an error? I would be glad to some intuitive explanation too.

I tried to read Generalized Principal Component Analysis by Vidal, Ma, Sastry but explanation there is a bit more generalized and doesn't differ much. I also tried to use The Matrix Cookbook to understand those matrix formulas but couldn't find anything helpful.

Thanks.

$\endgroup$

Your Answer

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

Browse other questions tagged or ask your own question.