2
$\begingroup$

I came across many different derivations of PCA, but still I have some difficulties with fully understanding this algorithm. So, assume we have covariance symmetric matrix of our data $A\in \mathbb R^{n\times n}$ and our PCA task is to maximize variance of projections onto some vector $u$ with constraint $u^T u=1$, which is given by(after some derivations): $$f(u)=u^T Au$$ After using Largrange maximization, we know that expression below maximize above function: $$Au=\lambda u$$ and as a result optimal value of $f(u)$ is given by: $$f(u)=u^T u \lambda = \lambda$$ so our function $f(u)$ has maximal value for eigenvector $u$ with largest eigenvalue $\lambda$. And then we can choose for example two largest eigenvalues in order to have projections of our data onto two dimensional space which is spanned by corresponding orthogonal eigenvectors which explains huge part of variance in our data due to $\operatorname{tr}A=\sum \lambda_i$

My question is following: Why we can choose arbitrarily number of eigenvectors and form them as a basis onto which we project our original data? Why those eigenvectors with largest variance given by corresponding eigenvalues form a basis(our variance maximizing function $f(u)$ is determined by vector $u$ not a matrix $U$)? Derivations of PCA dont seek to maximize variance of projections onto matrix $U$ but only onto vector $u$. So generally how we generalize our formula for maximization of projections onto vector $u(f(u)$ to maximization of variance of projections onto basis given by $U(f(U))$ which is formed from orthogonal eigenvectors? How you can explain that in every PCA derivation, we maximize function of one particular vector ($f(u)$) and finally we can choose arbitrarily number of $n$ eigenvectors with largest eigenvlue to project our data onto $\mathbb R^n$ space.

Sorry for few questions instead of one, but I try to express my concerns best as possible.

$\endgroup$
2
$\begingroup$

We may derive PCA by finding directions that maximize the variance, and eigen vectors naturally arise as solutions. Than we show that any linear combination of these solutions is itself a solution, thus forming a basis spanning the solution space.

$$\operatorname{Var}_u(x)=\operatorname{E}((x\cdot u-\operatorname{E}(x\cdot u))^2)$$ $$\operatorname{E}((u(\cdot (x-\operatorname{E}(x\cdot u)))^2)$$ $$u\cdot \operatorname{E}((x-\operatorname{E}(x))(x-\operatorname{E}(x))^t)\cdot u$$ $$\implies$$ $$\operatorname{Var}_u(x)=u^tCu$$

Let

$$v=U\cdot c$$

and

$$u=\sum_{i=0}^n c_i u_i$$

be the projection of a vector $v$ onto the subspace spanned by the first $n$ basis vectors $U=\{u_i\}$.

This addresses your question about projections onto a subspace, we are computing the entire basis $U$ at once. We employ Lagrange multipliers to constrain our solutions $u_i$ to be of unit length.

$$L=\left(\sum_{i=0}^nc_iu_i\right)^tC\left(\sum_{i=0}^nc_iu_i\right)+\sum_{i=0}^n\lambda_i(1-u_i^tu_i)$$

We require all partial derivatives to be zero.

$$\frac{\partial}{\partial u_i}L=(C^t+C)c^2_iu_i-\lambda_i u_i$$ $$C^t=C$$ $$0=2Cc^2_iu_i-\lambda_i u_i$$

$$Cu_i=\frac{\lambda_i}{2c^2_i}u_i$$ We recognize the familiar eigen-equation, with $\frac{\lambda_i}{2c^2_i}$ being the eigenvalue corresponding to the eigen-vector $u_i$.

Thus, a projection of a vector onto the subspace spanned by particular solutions $U=\{u_i\}$ (eigen-basis) is itself a solution, maximizing the lagrangian.

$\endgroup$
  • $\begingroup$ Thanks for answer, but I fully understand your derivations and this is not my problem ;) My problem is why we can form basis from eigenvectors whereas in your formulas we maximize expression of only one vector u instead of matrix consisting of many vectors(columns) given by U. $\endgroup$ – mokebe Nov 11 '16 at 15:55
  • $\begingroup$ I have explicitly addressed your issue/question, and proved that we can take projections onto the eigen subspace. If anything is still unclear, ask. $\endgroup$ – Žiga Sajovic Nov 11 '16 at 16:23
  • $\begingroup$ thank you very much for elaborated answer. I will digest it soon and ask questions or accept your answer if everything will be clear for me ;) $\endgroup$ – mokebe Nov 11 '16 at 16:28
  • $\begingroup$ First question: mathworld.wolfram.com/VectorSpaceProjection.html what does $c_{i}$ means in formula for projection of $u$ onto eigenvectors? $c_{i}=<u,v_{i}>?$ $\endgroup$ – mokebe Nov 11 '16 at 17:12
  • 2
    $\begingroup$ The vector (c1,c2,..,cn) is the projection of the vector u onto the subspace spanned by u_i, expressed in {u_i} basis, to be more precise. It just means that we are taking the projection of our vector onto the subspace spanned by the eigen vectros, as the question asked for. We showed that this projection maximizes the lagrangian. This concludes the proof. $\endgroup$ – Žiga Sajovic Nov 11 '16 at 17:21

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.