Why Matlab function eigs has different results for the same input data?

Dear Matlab friends,

I use Matlab (2014b 64-bit) function eigs to find eigen values (some smallest ones) and vectors of sparse matrix, in LLE (locally linear embedding) algorithm. I find eigs has different results for the same input data. That means, for the same input data, current running results of eigs are different form the next running results of eigs. Another Matlab function eig has similar phenomenon. The last (also smallest) eigen value of the results of eigs is always zero. Why? How can I get the stable output? I'd like to hear from you!

Honggui

[chen naveh]

I have the same problem... Following.

[the cyclist]

Can you load an example of input data and code that exhibits the problem?

[Honggui Li]

Please see the wonderful answer from John D'Errico.

Answer 1

[John D'Errico]

This is because eigs uses a random start. So it need not generate exactly the same result every time it is called.

Worse, since eigenvectors are not unique(!), they may vary in the sign of those vectors generated. That is, you can multiply all elements of an eigenvector by -1 (actually, any constant will suffice) and still have an equally valid eigenvector for that eigenvalue.

That the last eigenvalue as returned by eigs is always zero merely means that your matrix is singular.

For example, if I generate a clearly singular matrix, then one eigenvalue (well, at least one eigenvalue) will be singular, or effectively so.

A = rand(4,3);A = A(:,[1 2 3 3]);
rank(A)
ans =
     3

eigs(A)
ans =
   -2.99458227515929e-17
      0.0967955674503601
      -0.547784486644781
        1.98850968095585

So next, I have a non-singular matrix. No surprise that here no eigenvalues are zero.

A = rand(4);
rank(A)
ans =
     4

eigs(A)
ans =
       -0.126408754855564 +                     0i
       -0.133302928038295 +     0.236757870917361i
       -0.133302928038295 -     0.236757870917361i
         1.93779172327825 +                     0i

Finally, if an eigenvalue is repeated, then there will be infinitely many choices of eigenvectors that span the subspace for that repeated eigenvalue.

As far as getting a stable answer, you can set the seed for the random generator that eigs will use to some fixed value. That will cause eigs to start from the same point every time, so the result will be stable (by some arbitrary definition of stability.) Alternatively, you can pass in an options structure to eigs, with a starting vector already supplied. Thus opts.v0 must be an Nx1 vector.

For example:

A = sprand(100,100,.01);
rank(full(A))
ans =
    54

[V,D] = eigs(A);
[V1,D1] = eigs(A);

sum(V == V1)
ans =
      0     0     0     0     0     0

Nothing was the same here. Now do this:

opts.v0 = rand(100,1);
[V,D] = eigs(A,5,'LM',opts);
[V1,D1] = eigs(A,5,'LM',opts);

sum(V == V1)
ans =
   100   100   100   100   100

As you see, the two results are now identical.

So the things that you are seeing are not any surprise at all. Just mathematical fact, and nothing really beyond a basic linear algebra 101 class. Had you read the help for eigs, you would also have seen the fact that eigs uses a random start vector.

OPTS.v0: starting vector [N-by-1 vector | {randomly generated}]

[Honggui Li]

Hi John D'Errico,

Thank your for the wonderful answer. I am suddenly enlighted. I should develop the habit of reading the technique documents in detail.

Honggui

[Honggui Li]

Hi John D'Errico,

eigs can have stable output if it has a fixed seed for the random generator. It is my unstable input of eigs that leads to the unstable output of eigs.

Honggui

[John D'Errico]

Yes. As I pointed out, you can either fix the random seed, or fix the start vector. Either way will make the result a predictable one.

Both eigs and svds use a random start.

[Brian Mace]

I don't think fixing the seed helps though: getting the same numbers out by seeding the input does not mean they are actually correct eignvalues. We are having problems with real, symmetric matrices: eigs is giving us complex eigenvalues, which of course cannot be.

In our case it looks like the fact that our eigenproblem has repeated zero eigenvalues causes trouble - eigs doesn't like it.

The issue of the eigenvectors is not a problem since you can always normalise them however you want.

[Steven Lord]

Can you send a MAT-file containing the matrix to Technical Support (using the Contact Us link at the top of this page) along with the syntax you use to call eigs so that we can investigate?

[Dharshan]

Does this still apply? Or has matlab updated