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.



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.