Mailing-List: contact mahout-user-help@lucene.apache.org; run by ezmlm
Precedence: bulk
Reply-To: mahout-user@lucene.apache.org
Received-SPF: pass (athena.apache.org: domain of steven.buss@gmail.com
 designates 209.85.218.217 as permitted sender)
DomainKey-Signature: a=rsa-sha1; c=nofws;
        d=gmail.com; s=gamma;
        h=mime-version:from:date:message-id:subject:to:content-type;
        b=n7wQqnBlkIGweuvGfXyZNAWgTGNe86iUzjQG4B0t2AJZ0rb9EPSyB2laqSCdFEvSq4
         HnVjm24vb1mQGTqD4j+qy06e0kQoi/HXke0t8+DDRiC2xWX8BqdaAkO9XHZTDYQduBtJ
         aIPEcWUDs33Oefhd++Z0NIKV9aNIlCYcVYLz4=
MIME-Version: 1.0
From: Steven Buss <steven.buss@gmail.com>
Date: Wed, 24 Feb 2010 16:53:35 -0500
Message-ID: <cc2aa7771002241353h15bd0614o874ae167d904ed47@mail.gmail.com>
Subject: Symmetric eigendecomposition for kernel PCA
To: mahout-user@lucene.apache.org
Content-Type: text/plain; charset=UTF-8

I was chatting with Jake Mannix on twitter regarding mahout 180 and if
that patch is suitable for sparse symmetric positive-definite
matrices, and he suggested we continue the conversation on the mailing
list, so:

My research partner and I have a dataset that consists of 400,000
users and 1.6 million articles, with about 22 million nonzeros. We are
trying to use this data to make recommendations to users. We have
tried using the SVD and PLSI, both with unsatisfactory results, and
are now attempting kPCA.

We have a 400,000 by 400,000 sparse symmetric positive-definite
matrix, H, that we need the top couple hundred eigenvectors/values
for. Jake has told me that I can use mahout 180 unchanged, but it will
be doing redundant work and the output eigenvalues are the squares of
the ones we actually want. This sounds like a good approach, but it
would be great if mahout had an optimized eigendecomposition for
symmetric matrices. Jake suggested I submit a JIRA ticket regarding
this, which I plan to do.

H is the pairwise distance in feature space (calculated using a kernel
function) between each pair of users (or some subset of users). After
I mentioned this to Jake, he asked me "why aren't you just doing it
all in one go? Kernelize on the rows, and do SVD on that? Why do the
M*M^t intermediate step?" Unfortunately, I'm not sure what you're
asking, Jake, can you clarify?

Steven Buss
steven.buss@gmail.com
http://www.stevenbuss.com/