[SciPy-user] Sparse v. dense matrix, SVD and LSI-like analysis

[Travis Oliphant]

Nick Arnett wrote:

> Robert Kern wrote:
>
>> An SVD is not the same as an eigen decomposition.
>>
>> http://mathworld.wolfram.com/EigenDecomposition.html
>> http://mathworld.wolfram.com/SingularValueDecomposition.html
>
>
> That dawned on me not too long after posting.  Fuzzy brain this week, 
> a birth and a death in the family a few days apart.
>
>> In any case, all of the linalg.* functions only operate on dense 
>> arrays, not sparse matrices.
>
>
> Ummm, now I'm thinking I'm in over my head.  SVD is a matrix operation 
> isn't it?  I was imagining that an array of mostly zeros would be the 
> equivalent of a sparse matrix, so that SVD would apply to it for what 
> I'm doing, which is related to latent semantic analysis.

The SVD of A is constructed using the eigen decompostion of A A^H  and 
A^H A  which have the same real-valued eigenvalues (though one may have 
some zero-valued eigenvalues the other doesn't) and unitary eigenvector 
matrices:   The decompostion provides

A = U D V^H    where U U^H =I  and V V^H = I

so that

AA^H = U D^2 U^H

and

A^H A = V D^2 V^H

showing that

U are the eigenvectors of A A^H  corresponding to non-zero eigenvalues
V are the eigenvectors of A^H A  corresponding to non-zero eigenvalues
D^2 are the non-zero eigenvalues of both

So, while the SVD is not an eigenvector decomposition it is related to one.

-Travis