2
$\begingroup$

I am following this article on face recognition. In "calculating eigenfaces" section, the authors present a solution for the problem of calculating a very big matrix:

Let $A_{N^2\times M}$ be an $M$ sized dataset, where each column in an $N\times N$ image. Instead of calculating the $M$ large eigenvectors of the $N^2\times N^2$ co-variance matrix they calculate the $M$ eigenvectors of $L=A^TA$ matrix which is of size $M\times M$.

  • Why is this a valid\good enough solution?
  • What are the criteria for a largest vector? larger in which seance?
$\endgroup$
  • 2
    $\begingroup$ Questions like these are yet another reason why I prefer the SVD presentation of these results as opposed to the eigenvalue versions. $\endgroup$ – J. M. is a poor mathematician Jan 7 '17 at 11:23
4
$\begingroup$

If $A$ and $B^T$ are $m\times n$ matrices (so both products $AB$ and $BA$ exist) then their characteristic polynoms $p_{AB}(\lambda)$ and $p_{BA}(\lambda)$ are almost the same (look for the sketch of proof at Wikipedia): $$ p_{AB}(\lambda)=(-\lambda)^{m-n}p_{BA}(\lambda). $$ Therefore, their non-zero eigenvalues are the same as well.

Also, for any eigenvector $x$ of matrix $AB$ corresponding to a non-zero eigenvalue $\lambda$ the vector $Bx$ becomes an eigenvector of $BA$ and corresponds to the same eigenvalue. $$ (BA)(Bx)=B(AB)x=B(\lambda x)=\lambda(Bx). $$

$\endgroup$
  • $\begingroup$ Could you add some more detail on how this leads to the OP's result? $\endgroup$ – nbubis Jan 7 '17 at 11:39
  • $\begingroup$ @nbubis Ah, sorry, I've concentrated on eigenvalues and forgot to add a note on eigenvectors. Will do in a minute. $\endgroup$ – Sergei Golovan Jan 7 '17 at 11:43
  • $\begingroup$ @SergeiGolovan How long are your minutes :D. If possible I would still like further clarification on the eigenvectors. $\endgroup$ – Shinobii Jan 9 '18 at 17:09
  • 1
    $\begingroup$ @Shinobii What do you need to be clarified? $\endgroup$ – Sergei Golovan Jan 10 '18 at 8:23
  • 1
    $\begingroup$ @Shinobii: The other eigenvalues are zero. Basically, since the matrix in question is symmetric, the orthogonal complement of the $M$ eigenvectors' span is the nullity of the matrix. $\endgroup$ – Sergei Golovan Jan 10 '18 at 14:06

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.