Prev: remove a specific frequency from emg signal
Next: remove a specific frequency from emg signal
From: Josh Moore on 9 Aug 2010 08:09
I'm trying to use eigs to get the dominant eigenvalue and eigenvector for a symmetric, sparse matrix of size about 3.6 million (square). Specifically, the matrix is an adjacency matrix for a graph and has only zeros and ones as entries. Since the matrix is non-negative, the Perron-Frobenius theorem states that the dominant eigenvector should have only non-negative entries. However, the vector that I get from eigs has both positive and negative entries (but no zero entries).

Furthermore, when I choose to take the 10 largest eigenvalues/eigenvectors, I see that the sorting of the eigenvalues is not consistent -- the magnitude is non-increasing for the first 9 or so eigenvalues, but one of the last couple of eigenvalues is larger in magnitude than a previous one.

Any ideas what to do here?

Addendum: at the risk of answering my own question, when I scale the matrix up by multiplying by 1 million or so, I get a strictly negative eigenvector instead. Could this be (a scalar multiple of) the eigenvector that I need, and the previous error is due only to numerical error from the tiny ratio between the magnitude of the entries of the matrix and its size?
From: Josh Moore on 9 Aug 2010 09:49
Ok, I thought I had figured this problem out, but apparently not. I still get inconsistent signs in the eigenvector regardless of the scale I use. Has anyone experienced this before?
From: Matt J on 9 Aug 2010 10:22
"Josh Moore" <wegetsignal(a)gmail.com> wrote in message <i3or53$o7a$1(a)fred.mathworks.com>...

> Furthermore, when I choose to take the 10 largest eigenvalues/eigenvectors, I see that the sorting of the eigenvalues is not consistent -- the magnitude is non-increasing for the first 9 or so eigenvalues, but one of the last couple of eigenvalues is larger in magnitude than a previous one.
========

I see nothing in doc eigs about the eigenvalues be sorted, so I wouldn't assume this to be guaranteed. It certainly isn't for eig().



>
> Addendum: at the risk of answering my own question, when I scale the matrix up by multiplying by 1 million or so, I get a strictly negative eigenvector instead. Could this be (a scalar multiple of) the eigenvector that I need, and the previous error is due only to numerical error from the tiny ratio between the magnitude of the entries of the matrix and its size?
=========

Scaling a matrix wouldn't change the eigenvectors (only the eigenvalues), but there is numerical error in the calculation of eigenvectors, so negatives could result from values that are meant to be zero. Are the negatives you are seeing arbitrarily large in size, relative to the other eigenvector elements?
From: Josh Moore on 9 Aug 2010 10:38

> I see nothing in doc eigs about the eigenvalues be sorted, so I wouldn't assume this to be guaranteed. It certainly isn't for eig().

From the documentation for eigs:
"eigs(A,k) and eigs(A,B,k) return the k largest magnitude eigenvalues."

I'm using eigs(A,1) to get the dominant eigenvector and I'm only using k > 1 outside of the normal routine to try to understand what's going on better.

> Scaling a matrix wouldn't change the eigenvectors (only the eigenvalues), but there is numerical error in the calculation of eigenvectors, so negatives could result from values that are meant to be zero. Are the negatives you are seeing arbitrarily large in size, relative to the other eigenvector elements?

It actually seems like the negative entries are the correct ones and that the positive ones are the extraneous values (this would make sense if the eigenvalue were negative, but having a negative eigenvalue for a positive eigenvector from a non-negative matrix also doesn't make sense...). The positive values are of very small magnitude (and very close to zero) compared to even the smallest magnitude negative entries. For now I'm taking the absolute value of the eigenvector as an approximation (since it actually in my case also wouldn't make sense to have entries equal to zero in this eigenvector) and it seems to not be far off from what I should be getting...
From: Matt J on 9 Aug 2010 10:51
"Josh Moore" <wegetsignal(a)gmail.com> wrote in message <i3p3sc$hk8$1(a)fred.mathworks.com>...
>
> > I see nothing in doc eigs about the eigenvalues be sorted, so I wouldn't assume this to be guaranteed. It certainly isn't for eig().
>
> From the documentation for eigs:
> "eigs(A,k) and eigs(A,B,k) return the k largest magnitude eigenvalues."
=============

Right, but it doesn't say in what order these k largest eigenvalues will appear....




> It actually seems like the negative entries are the correct ones and that the positive ones are the extraneous values (this would make sense if the eigenvalue were negative, but having a negative eigenvalue for a positive eigenvector from a non-negative matrix also doesn't make sense...).
=====================

Why not? The sign of an eigenvector is indeterminate. The following example shows how a positive matrix can easily have a negative-signed dominant eigenvector

>> [V,D]=eig([.1 0.9; .5 .5])

V =

-0.8742 -0.7071
0.4856 -0.7071


D =

-0.4000 0
0 1.0000
 | 
Pages: 1
Prev: remove a specific frequency from emg signal
Next: remove a specific frequency from emg signal