Thread Subject: unsorted eigenvalues

I'm doing eigendecomposition-based spectral analysis, and I
am looking for a way to recover the eigenvalues of a matrix
(positive semidefinite Hermitian, in my case) without having
them sorted for me.

I've seen this topic come up in other threads (such as
"Sorted Eigenvalues & Eigenvectors?" of April 2004 and
"non-sorting SVD" of May 2007), but the answers there
haven't settled my problem.

In my experience, eig() always returns the eigenvalues
sorted in ascending order, despite statements to the
contrary in previous threads. (Perhaps this changed with a
recent version?)

I am aware that the eigenvectors have been sorted so that
eigenvector index i corresponds to eigenvalue index i, and I
know how to reconstruct the signal with the sorted output
given by eig(), but that is not sufficient. I also need to
know the indexes that the significant eigenvalues had before
they were sorted. The ideal way to do this would be if
eig() or some other function had an optional argument I
could use to suppress the sorting function in eig(). (After
all, MATLAB has an easy-to-use sort() function, if I want
sorted output.) Since this seems to be a recurring
question, I suspect other people want this, too.

Thanks for any suggestions,
R

"Robert Sparr" <robertdotsparr@NOSPAMsri.com> wrote in
message <fdhvq6$hok$1@fred.mathworks.com>...
> I'm doing eigendecomposition-based spectral analysis, and I
> am looking for a way to recover the eigenvalues of a matrix
> (positive semidefinite Hermitian, in my case) without having
> them sorted for me.
>
> I've seen this topic come up in other threads (such as
> "Sorted Eigenvalues & Eigenvectors?" of April 2004 and
> "non-sorting SVD" of May 2007), but the answers there
> haven't settled my problem.
>
> In my experience, eig() always returns the eigenvalues
> sorted in ascending order, despite statements to the
> contrary in previous threads. (Perhaps this changed with a
> recent version?)
>
> I am aware that the eigenvectors have been sorted so that
> eigenvector index i corresponds to eigenvalue index i, and I
> know how to reconstruct the signal with the sorted output
> given by eig(), but that is not sufficient. I also need to
> know the indexes that the significant eigenvalues had before
> they were sorted. The ideal way to do this would be if
> eig() or some other function had an optional argument I
> could use to suppress the sorting function in eig(). (After
> all, MATLAB has an easy-to-use sort() function, if I want
> sorted output.) Since this seems to be a recurring
> question, I suspect other people want this, too.
>
> Thanks for any suggestions,
> R

What is the significance of unsorted eigenvalues? I mean,
the eigenvalues are roots of the characteristic polynomial -
in what sense do these roots have order?

Best wishes, S

"Robert Sparr" <robertdotsparr@NOSPAMsri.com> wrote in message
news:fdhvq6$hok$1@fred.mathworks.com...
> I'm doing eigendecomposition-based spectral analysis, and I
> am looking for a way to recover the eigenvalues of a matrix
> (positive semidefinite Hermitian, in my case) without having
> them sorted for me.
>
> I've seen this topic come up in other threads (such as
> "Sorted Eigenvalues & Eigenvectors?" of April 2004 and
> "non-sorting SVD" of May 2007), but the answers there
> haven't settled my problem.
>
> In my experience, eig() always returns the eigenvalues
> sorted in ascending order, despite statements to the
> contrary in previous threads. (Perhaps this changed with a
> recent version?)

I think you may have misunderstood what was said in those previous threads.
We don't guarantee that the eigenvalues are returned in sorted order. We
also don't guarantee that the eigenvalues are not returned in sorted order.
We just return them from EIG in the order that the LAPACK routine that
calculates them returns them to EIG. If you want to guarantee that they are
sorted, sort them using SORT.

> I am aware that the eigenvectors have been sorted so that
> eigenvector index i corresponds to eigenvalue index i, and I
> know how to reconstruct the signal with the sorted output
> given by eig(), but that is not sufficient. I also need to
> know the indexes that the significant eigenvalues had before
> they were sorted.

I don't understand what you're asking for. If I calculate the eigenvalues
of magic(4):

[V, D] = eig(magic(4));
eigenvalues = diag(D)

eigenvalues =

                        34
          8.94427190999916
         -8.94427190999915
     9.41628944095001e-016

what are the "indexes [sic] that the significant eigenvalues had before they
were sorted"? What ordering are you looking for, and how would MATLAB
determine this ordering from the matrix?

If you're thinking about some sort of ordering of the eigenvalues to
correspond to the eigenvectors, just use the 2 output form of EIG. The kth
column of V above is the eigenvector corresponding to the kth eigenvalue in
D, D(k, k).

If you want the eigenvalues in some pseudorandom order, use RANDPERM to
permute them. Note that one of the permutations will order the eigenvalues
in ascending order and one will order them in descending order. You can use
ISSORTED to test for these cases and use RANDPERM again to permute them.

*snip*

--
Steve Lord
slord@mathworks.com

"Robert Sparr" <robertdotsparr@NOSPAMsri.com> writes:

> I am aware that the eigenvectors have been sorted so that
> eigenvector index i corresponds to eigenvalue index i, and I
> know how to reconstruct the signal with the sorted output
> given by eig(), but that is not sufficient. I also need to
> know the indexes that the significant eigenvalues had before
> they were sorted.

What is the true order of the roots of this polynomial?

x^3 - 2*x^2 +3*x -3

-Peter

Hi Robert and all,

I was in the same problem. But, now I have the answer.

> What is the significance of unsorted eigenvalues? I mean,
> the eigenvalues are roots of the characteristic polynomial -
> in what sense do these roots have order?

Since an eigenvector matrix is just a rotating matrix, there
are a CORRESPONDENCE between the original order and the
order of eigenvalues after eigenvalue decomposition. What we
are talking about is this.

Here is the answer:

C=cov(some_data);
[V,D]=eig(C);
unsorted_eigenvalues=V'*C*V;

I hope your answer is the same one:)

Best,
Masakazu

Hi Robert and all,

I was in the same problem. But, now I have the answer.

> What is the significance of unsorted eigenvalues? I mean,
> the eigenvalues are roots of the characteristic polynomial -
> in what sense do these roots have order?

Since an eigenvector matrix is just a rotating matrix, there
are a CORRESPONDENCE between the original order and the
order of eigenvalues after eigenvalue decomposition. What we
are talking about is this.

Here is the answer:

C=cov(some_data);
[V,D]=eig(C);
unsorted_eigenvalues=V'*C*V;

I hope your answer is the same one:)

Best,
Masakazu

Hi,

> Here is the answer:
>
> C=cov(some_data);
> [V,D]=eig(C);
> unsorted_eigenvalues=V'*C*V;

This seems to be my misunderstanding. I couldn't get what I
want:(

Best,
Masakazu

"Masakazu Iwamura" <masa@AHOAHOcs.osakafu-u.ac.jp> wrote in message
<fhpb69$k4u$1@fred.mathworks.com>...
> Hi,
>
> > Here is the answer:
> >
> > C=cov(some_data);
> > [V,D]=eig(C);
> > unsorted_eigenvalues=V'*C*V;
>
> This seems to be my misunderstanding. I couldn't get what I
> want:(

The problem is in your wish for something
that is "unsorted".

A sorted vector means that it has a definite,
known order. Unsorted merely means that
this ordering has not been applied. It does
not mean that you will get any desired
ordering. The ordering may then be arbitrary,
which is not what you seem to be wishing
for.

What people seem to want when they ask
for unsorted eigenvalues is their OWN
(magically chosen) ordering for the
eigenvalues. However, the eigenvalue
code cannot understand this, or know
that ordering. The eigenvalues are merely
a set of polynomial roots in the complex
plane.

John

Peter Boettcher <boettcher@ll.mit.edu> wrote in message <muytzpeaonp.fsf@G99-Boettcher.llan.ll.mit.edu>...
> "Robert Sparr" <robertdotsparr@NOSPAMsri.com> writes:
>
> > I am aware that the eigenvectors have been sorted so that
> > eigenvector index i corresponds to eigenvalue index i, and I
> > know how to reconstruct the signal with the sorted output
> > given by eig(), but that is not sufficient. I also need to
> > know the indexes that the significant eigenvalues had before
> > they were sorted.
>
> What is the true order of the roots of this polynomial?
>
> x^3 - 2*x^2 +3*x -3
>
> -Peter

 I have the same problem and speaking about the order of the eigenvalues it is important because the eigenvectors correspond, in my case, to a rotation matrix used to obtain principal coordinates which changes with frequency. so if eig() organizes the eigenvectors i will never know which vector is which from one frequency to the other as the maximum eigenvalue is not always on the same direction.

Morad

Peter Boettcher <boettcher@ll.mit.edu> wrote in message <muytzpeaonp.fsf@G99-Boettcher.llan.ll.mit.edu>...
> "Robert Sparr" <robertdotsparr@NOSPAMsri.com> writes:
>
> > I am aware that the eigenvectors have been sorted so that
> > eigenvector index i corresponds to eigenvalue index i, and I
> > know how to reconstruct the signal with the sorted output
> > given by eig(), but that is not sufficient. I also need to
> > know the indexes that the significant eigenvalues had before
> > they were sorted.
>
> What is the true order of the roots of this polynomial?
>
> x^3 - 2*x^2 +3*x -3
>
> -Peter

 I have the same problem and speaking about the order of the eigenvalues it is important because the eigenvectors correspond, in my case, to a rotation matrix used to obtain principal coordinates which changes with frequency. so if eig() organizes the eigenvectors i will never know which vector is which from one frequency to the other as the maximum eigenvalue is not always on the same direction.

Morad

"Robert Sparr" <robertdotsparr@NOSPAMsri.com> wrote in message <fdhvq6$hok$1@fred.mathworks.com>...
> I'm doing eigendecomposition-based spectral analysis, and I
> am looking for a way to recover the eigenvalues of a matrix
> (positive semidefinite Hermitian, in my case) without having
> them sorted for me.
>
> I've seen this topic come up in other threads (such as
> "Sorted Eigenvalues & Eigenvectors?" of April 2004 and
> "non-sorting SVD" of May 2007), but the answers there
> haven't settled my problem.
>
> In my experience, eig() always returns the eigenvalues
> sorted in ascending order, despite statements to the
> contrary in previous threads. (Perhaps this changed with a
> recent version?)
>
> I am aware that the eigenvectors have been sorted so that
> eigenvector index i corresponds to eigenvalue index i, and I
> know how to reconstruct the signal with the sorted output
> given by eig(), but that is not sufficient. I also need to
> know the indexes that the significant eigenvalues had before
> they were sorted. The ideal way to do this would be if
> eig() or some other function had an optional argument I
> could use to suppress the sorting function in eig(). (After
> all, MATLAB has an easy-to-use sort() function, if I want
> sorted output.) Since this seems to be a recurring
> question, I suspect other people want this, too.
>
> Thanks for any suggestions,
> R

 robert i have found one way to sort the eigenvectors and eigenvalues in the correct order in my case i hope it will help you.
as i have the eigenvectiors changing with frequency, after applying eig() i perform the dot product between V(frequency) and V(frequency+1) and then i search the indices of the element that are closer to 1 then i reorder my vectors according to the new order.

 i hope i was enough clear and that this will solve your problem

best regards
Morad

"Morad Kassem" <morad_kassem@hotmail.com> wrote in message <gmbtha$dip$1@fred.mathworks.com>...

> robert i have found one way to sort the eigenvectors and eigenvalues in the correct order in my case i hope it will help you.
> as i have the eigenvectiors changing with frequency, after applying eig() i perform the dot product between V(frequency) and V(frequency+1) and then i search the indices of the element that are closer to 1 then i reorder my vectors according to the new order.
>
> i hope i was enough clear and that this will solve your problem

Yes, this is probably the best solution, and one
that I have wanted to do for a while. I wrote it
up this morning, and posted eigenshuffle.m on
the file exchange. Look for it later today or
possibly tomorrow.

John

"Robert Sparr" <robertdotsparr@NOSPAMsri.com> wrote in message <fdhvq6$hok$1@fred.mathworks.com>...
> I'm doing eigendecomposition-based spectral analysis, and I
> am looking for a way to recover the eigenvalues of a matrix
> (positive semidefinite Hermitian, in my case) without having
> them sorted for me.
>
> I've seen this topic come up in other threads (such as
> "Sorted Eigenvalues & Eigenvectors?" of April 2004 and
> "non-sorting SVD" of May 2007), but the answers there
> haven't settled my problem.
>
> In my experience, eig() always returns the eigenvalues
> sorted in ascending order, despite statements to the
> contrary in previous threads. (Perhaps this changed with a
> recent version?)
>
> I am aware that the eigenvectors have been sorted so that
> eigenvector index i corresponds to eigenvalue index i, and I
> know how to reconstruct the signal with the sorted output
> given by eig(), but that is not sufficient. I also need to
> know the indexes that the significant eigenvalues had before
> they were sorted. The ideal way to do this would be if
> eig() or some other function had an optional argument I
> could use to suppress the sorting function in eig(). (After
> all, MATLAB has an easy-to-use sort() function, if I want
> sorted output.) Since this seems to be a recurring
> question, I suspect other people want this, too.
>
> Thanks for any suggestions,
> R

This might work;

 [p,idx]=esort(diag(D)); D=diag(p); P=P(:,idx);

or

http://www.mathworks.com/matlabcentral/fileexchange/18904-sort-eigenvectors-eigenvalues