PCA Algorithm: matrix dimensions too large!

I'm trying to implement the Principal Component Analysis (PCA) for
face recognition using C#. PCA requires me to find eigen vectors of an
N dimensional image space (each pixel coordinate is a single
dimension).

I've code and everything looks good for 16 x 16 images but when I try
to apply it to 40x40 or 100x100 images, the dimensions of my
covariance matrix is simply to large and computation is completely is
really slow duty to virtual memory demands.

For an NxN image, my covariance matrix has dimensions of N^2 x N^2.
This is not a problem for N=16 as the covariance matrix would be just
256x256. But for numbers like N=100, my covariance matrix dimensions
are 10000x10000. This is simply to huge and is very slow as i said due
to the virtual memory demands. I just need the covariance matrix to
compute the eigen vectors and then i can discard. Is there an easier
way to calculate Eigen Vectors without the use of a covariance matrix
for a set of images of size NxN. Or is it possible to calculate the
eigen vectors in parts from a partial covariance matrix.

What possible solutions exist to my probem

Thanks a lot

Joel

Joel wrote:
> I'm trying to implement the Principal Component Analysis (PCA) for
> face recognition using C#. PCA requires me to find eigen vectors of an
> N dimensional image space (each pixel coordinate is a single
> dimension).

> I've code and everything looks good for 16 x 16 images but when I try
> to apply it to 40x40 or 100x100 images, the dimensions of my
> covariance matrix is simply to large and computation is completely is
> really slow duty to virtual memory demands.

In the past there were implementations for many algorithms for the
case where the matrix was larger than available memory, one of
the more common ones being solutions to linear equations.

That might be a lost art now, and it might be that it hasn't
been done for PCA.  If you understand the PCA algorithm, and find
the methods for doing large matrix problems, then you should
be able to figure out if it is possible, and then how to do it.

You might have to go back to the older journals when this problem
was more important.

-- glen

On Feb 15, 11:59 am, "Joel" <joelag...@gmail.com> wrote:
> I'm trying to implement the Principal Component Analysis (PCA) for
> face recognition using C#. PCA requires me to find eigen vectors of an
> N dimensional image space (each pixel coordinate is a single
> dimension).
>
> I've code and everything looks good for 16 x 16 images but when I try
> to apply it to 40x40 or 100x100 images, the dimensions of my
> covariance matrix is simply to large and computation is completely is
> really slow duty to virtual memory demands.
>
> For an NxN image, my covariance matrix has dimensions of N^2 x N^2.
> This is not a problem for N=16 as the covariance matrix would be just
> 256x256. But for numbers like N=100, my covariance matrix dimensions
> are 10000x10000. This is simply to huge and is very slow as i said due
> to the virtual memory demands. I just need the covariance matrix to
> compute the eigen vectors and then i can discard. Is there an easier
> way to calculate Eigen Vectors without the use of a covariance matrix
> for a set of images of size NxN. Or is it possible to calculate the
> eigen vectors in parts from a partial covariance matrix.
>
> What possible solutions exist to my probem

Crosspost to sci.math.num-analysis.

Hope this helps.

Greg

Joel ha scritto:

> For an NxN image, my covariance matrix has dimensions of N^2 x N^2.

Suppose you store the images as column vectors of length NxN (the
number of pixels in each image) and that you have M images, you'll end
up with a matrix G (N^2 x M) :

                  1
CovMat =  -------- G G^T
                M - 1

this is what you are trying to find the eigenvalues/eigenvectors for,
right?

There is a trick widely used when doing PCA on sets of images, it is
based on the fact that the (M x M) matrix:


                      1
lmCovMat =  -------- G^T G
                   M - 1


has the same non-zero eigenvalues of CovMat. So what you do is to
compute the eigenvalues and eigenvectors of this low memory covariance
matrix and then, for the eigenvectors, compute:

E = G lmE

where E is a matrix containing the wanted eigenvectors and lmE is the
matrix of the eigenvectors compouted from the lmCovMat.

This is implemented already in the OpenCV libraries.

Hope it helps.

On 15 Feb, 22:53, "Giff" <Giffn...@gmail.com> wrote:

>              1
> CovMat =  --------  G G^T
>            M - 1
>

>                1
> lmCovMat =  -------  G^T G
>              M - 1
>

well it came out quite bad, I hope you understand it anyway

Hi:

Try using SVD of the images instead of calculating the covariance matrix of 
images as a first step.  If you square the singular values you will get the 
eigenvalues.  There is a memory saving option and also be sure to have the 
largest dimension be the number of rows for greater memory efficiency.

[u, s, v] = svd(x, 0);

The eigenvectors of x'*x are contained in the columns of v and the 
eigenvectors of x*x' are contained as the columns of u.

Happy computing!!!

Pete

"Joel" <joelagnel@gmail.com> wrote in message 
news:1171558759.936052.311660@a34g2000cwb.googlegroups.com...
> I'm trying to implement the Principal Component Analysis (PCA) for
> face recognition using C#. PCA requires me to find eigen vectors of an
> N dimensional image space (each pixel coordinate is a single
> dimension).
>
> I've code and everything looks good for 16 x 16 images but when I try
> to apply it to 40x40 or 100x100 images, the dimensions of my
> covariance matrix is simply to large and computation is completely is
> really slow duty to virtual memory demands.
>
> For an NxN image, my covariance matrix has dimensions of N^2 x N^2.
> This is not a problem for N=16 as the covariance matrix would be just
> 256x256. But for numbers like N=100, my covariance matrix dimensions
> are 10000x10000. This is simply to huge and is very slow as i said due
> to the virtual memory demands. I just need the covariance matrix to
> compute the eigen vectors and then i can discard. Is there an easier
> way to calculate Eigen Vectors without the use of a covariance matrix
> for a set of images of size NxN. Or is it possible to calculate the
> eigen vectors in parts from a partial covariance matrix.
>
> What possible solutions exist to my probem
>
> Thanks a lot
>
> Joel
> 

>
>                   1
> CovMat =  -------- G G^T
>                 M - 1
>

Yes that's what I'm trying to do, and its a real memory hog.

>
>                       1
> lmCovMat =  -------- G^T G
>                    M - 1
>

How is this supposed to be a low memory matrix?

G^T G and G^T G is the same thing right?
G is a square matrix so the above trick isn't going to work.

Thanks a lot

Joel

I'm really sorry I got it all mixed up. I will work on what you
mentioned, and will let you know about the result.


Thanks a lot!

Joel

Hi, firstly thanks for your help. but it doesn't seem to work.

I took a very simplistic example of 2 Dimension data with 10 points as
follows:

   x   y
.69 .49
-1.31 -1.21
.39 .99
.09 .29
1.29 1.09
.49 .79
.19 -.31
-.81 -.81
-.31 -.31
-.71 -1.01

Using the tradinal way: I represent the data as 2 X 10 where each row
is a particular dimension.
To find the covariance matrix which is of size 2 X 2, I subtract the
mean of each row of my matrix from each value of that particular row
or dimension, and let me call this G. I take G and multiply with G^T
which gives me a 2X2 matrix. and then I divide it by M-1 which 9 in
this case. This gives me CovMat

Using your method, I do the same thing but I take G^T and multiple
with G which gives me 10X10 (i know the matrix imCovMat appears larger
here but that's because the no.of data is more than the dimensions).
and I then divide it by M-1 which is 9. This gives me ImCovMat

You told me that CovMat and ImCovMat have the same no-non zero eigen
values but how is this possible because one is 2X2 and the other is
10X10. Further, the 2X2 matrix has 2 eigen values and the 10X10 matrix
has 10 Eigen Values.

Can you tell me where I'm going wrong? Also while finding ImCovMat, do
I have to divide by 2 instead of 9 ?

Thanks a lot

Joel

I've looked around the internet with no luck.
I just need a way to get the eigen vectors and eigen values of A A^T
from A^T A.

Can anyone tell me a method that would help me arrive at the above
result?

Thanks

Joel