Eckert-Young and factor analysis. last minute qns.

[Subbarao Kambhampati <rao@parichaalak.eas.asu.edu>]

From: Marc Chung <mchung@asu.edu>
Subject: Re: I will be near the classroom 30min before the exam..for any last minute qns.
Date: Wed, 23 Oct 2002 14:23:54 -0700 (MST)
Message-ID: <20021023142136.R70370-100000@gandalf.marcchung.com>

mchung> I was reading up on LSI, and I found out about Eckart &
mchung> Young's theorem.  And maybe I'm a little confused as to how it
mchung> works, but does this allow you to approximate the SVD of a
mchung> matrix, or does it confirm that the SVD of a matrix is
mchung> correct?

[I am relieved  that people still have energy left to ask
question... the exam mustn't have been all that hard. ]

Ecker-Young is the fundamental theorem that just shows the existence
of SVD decomp--that every matrix will have an SVD decomposition.

Check out, for example, 

http://www.ldeo.columbia.edu/~jortiz/EarthStats/Week08notes.html

for some further information (first section is enough for your
question, although other stuff is interesting too). 

If you want to know about approximation methods for SVD analysis, the
right paper is 

http://citeseer.nj.nec.com/frieze98fast.html

This  idea is extended and used as basis for an LSI-based
clustering technique in 

http://www.cs.yale.edu/homes/kannan/Papers/cluster.ps

and is used by Manjara clustering engine (which, alas, is no 
longer available at http://cluster.cs.yale.edu )

[If these two papers seem to come from another planet--it is because
they are from the STOC/FOCS conferences--the premier conferences on
Theory of CS. If you like this stuff, you should consider some
algorithms courses--especially the one on approximation algorithms
offered by Goran Konjevod.]

Rao