mahout-user mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From Ted Dunning <ted.dunn...@gmail.com>
Subject Re: eigenvectors and eigenvalues of a matrix
Date Wed, 08 Jan 2014 15:13:35 GMT
I think that your code *looks* correct.  That doesn't mean that is *is*
correct, of course.  All of my code *looks* correct and it never is to
start with.

I would also point out that in the covariance matrix is (X-\mu)' (X-\mu)
for row-oriented data (most common in Mahout).  This means that you can
simply do the singular value decomposition of X-\mu to get exactly the
eigenvectors/values that you want (use the right singular vectors in this
case).  You don't need to square the covariance matrix and then take the
square root of the resulting singular values.  Doing it this way will give
you substantially more accuracy since every time you square things you cut
the number of significant figures in your computation roughly in half.
 (ish).

Note that many sources assume that the observations are column-oriented.
 In that case, you want (X-\mu) (X-\mu)' and thus you will look for the
left singular vectors of (X-\mu)

Regarding your code, Sebastian's comment is correct that ordering is
important.  You may be correct that having a map is what you want.  There
is a middle ground that you can find if you simply use a LinkedHashMap
since it preserves order *and* is a Map.

This line in your code would change:

    Map<Double,DenseVector> eigenMap = Maps.newLinkedHashMap();

In general, I think that your code could look more like this:

/**
 * Decompose the covariance matrix of row-oriented observations.
 */
Map<Double, Vector> eigen(Matrix observations) {
  observations = observations.clone();
  int columns = observations.columnSize();
  for (MatrixSlice row : observations) {
    row.vector().assign(Functions.minus(row.vector().zSum() / columns));
  }

  SingularValueDecomposition svd = new
SingularValueDecomposition(observations);
  Matrix v = svd.getV();

  Map<Double, Vector> r = Maps.newLinkedHashMap();
  for (int i = 0; i < svd,rank(); i++) {
      r.put(svd.getSingularValues()[i], v.viewColumn(i));
  }
  return r;
}

This has better accuracy and better compartmentalization.  Note, for
instance, that the return type is just a Map, not a HashMap.  That allows
the actual implementation to be changed to any other kind of Map if you
want ot.  Not also, the input are the observations.  That simplifies the
calling sequence.



On Wed, Jan 8, 2014 at 4:05 AM, Tharindu Rusira <tharindurusira@gmail.com>wrote:

> On Wed, Jan 8, 2014 at 4:58 PM, Sebastian Schelter <ssc@apache.org> wrote:
>
> > I would rather use a List of Pair<Double,Vector> entries then a HashMap
> > with the eigenvalue as key.
>
> Sure Sebastian, it's a better design. I wanted to verify that the line
> eigenMap.put(singularValues[i] * singularValues[i], (DenseVector)
> eigenVectors.viewRow(i)); is correct.
>
> Thanks,
>
> HashMap don't have an ordering and you will
> > get problems if you have to eigenvalues of the same magnitude.
> >
> >
> > On 08.01.2014 12:13, Tharindu Rusira wrote:
> > > Hi Ted, Thank a lot for your comprehensive reply.
> > >
> > > The following is a simple piece of code I wrote. According to what you
> > have
> > > said, this code would make sense, am I right? Please correct me if I'm
> > > wrong.
> > >
> > > /*respective parameters of the following method are taken from
> > > getSingularvalues() and getV() methods in SingularValueDecomposition
> > class.
> > > */
> > >
> > > public HashMap<Double,DenseVector>
> mapEigenvaluesToEigenVectors(double[]
> > > singularValues, Matrix eigenVectors) {
> > >
> > >     HashMap<Double,DenseVector> eigenMap = new
> > > HashMap<>(singularValues.length);
> > >
> > >     for (int i = 0; i < singularValues.length; i++) {
> > >
> > >       // eigenvalue = singular value ^2
> > >
> > >       // eigenvectors = right singular vectors
> > >
> > >       eigenMap.put(singularValues[i] * singularValues[i], (DenseVector)
> > > eigenVectors.viewRow(i));
> > >
> > >     }
> > >
> > >     return eigenMap;
> > >
> > >   }
> > >
> > >
> > > In case my problem is unclear, here's some context,
> > >
> > > I have an input matrix X and I want to find eigenvalues/eigenvectors of
> > the
> > > covariance matrix XTX. So my workaround is to find singular values and
> > > right singular vector of X in order to use the following equivalency.
> > > " Comparison with the eigenvector factorisation of *X*T*X* establishes
> > that
> > > the right singular vectors *W* of *X* are equivalent to the
> eigenvectors
> > of
> > > *X*T*X*, while the singular values *σ*(*k*) of *X* are equal to the
> > square
> > > roots of the eigenvalues *λ*(*k*) of *X*T*X*. " ~ Wikipedia [1]
> > >
> > > [1]
> > >
> >
> http://en.wikipedia.org/wiki/Principal_component_analysis#Singular_value_decomposition
> > >
> > >
> > > Regards,
> > >
> > >
> > >
> > > On Tue, Jan 7, 2014 at 12:27 PM, Ted Dunning <ted.dunning@gmail.com>
> > wrote:
> > >
> > >> The order of the singular values and vectors should tell you.
> > >>
> > >> For others who might be curious, the singular value decomposition
> > breaks a
> > >> matrix A into three factors
> > >>
> > >>     A = U S V'
> > >>
> > >> Both U and V are orthonormal so that U' U = I and V' V = I.  S is
> > diagonal.
> > >>
> > >> An eigenvalue decomposition decomposes a square matrix into two parts,
> > one
> > >> repeated
> > >>
> > >>     A = U S U*
> > >>
> > >> If A is symmetric, then these are real matrices and U* = U'.
> > >>
> > >> If A is symmetric, we can also decompose it using a Cholesky
> > transformation
> > >>
> > >>     A = R' R
> > >>
> > >> Where R is upper (right) triangular.  We can then decompose R with
> SVD.
> > >>  This gives us:
> > >>
> > >>     A = R' R
> > >>     R = U S V'
> > >>     R' R = (U S V')' (U S V') = V S U' U S V' = V S^2 V'
> > >>
> > >> a nice convenience is that S^2 is also diagonal and contains the
> > elements
> > >> of S, just squared.
> > >>
> > >> So the answer for Tharindu is that the elements of V are not changed
> or
> > >> re-ordered and neither are the elements of S.
> > >>
> > >>
> > >> On Mon, Jan 6, 2014 at 10:22 PM, Tharindu Rusira
> > >> <tharindurusira@gmail.com>wrote:
> > >>
> > >>> Hi,
> > >>> I am currently working with SingularValueDecomposition class and I
> like
> > >> to
> > >>> clarify the following.
> > >>>
> > >>> My goal is to find eigenvalues and corresponding eigenvectors of a
> > >> matrix.
> > >>> I know how to calculate eigenvalues and eigenvectors using svd but
is
> > >> there
> > >>> a way to keep track of which eigenvector corresponds to which
> > eigenvalue?
> > >>>
> > >>> Thanks,
> > >>> --
> > >>> M.P. Tharindu Rusira Kumara
> > >>>
> > >>> Department of Computer Science and Engineering,
> > >>> University of Moratuwa,
> > >>> Sri Lanka.
> > >>> +94757033733
> > >>> www.tharindu-rusira.blogspot.com
> > >>>
> > >>
> > >
> > >
> > >
> >
> >
>
>
> --
> M.P. Tharindu Rusira Kumara
>
> Department of Computer Science and Engineering,
> University of Moratuwa,
> Sri Lanka.
> +94757033733
> www.tharindu-rusira.blogspot.com
>

Mime
  • Unnamed multipart/alternative (inline, None, 0 bytes)
View raw message