wikipedia article implies that if A is positive definite (and normal which is true for symmetric) then SVD is the same as eigendecomposition.
however being positive definite is a fairly strong requirement... On Thu, Jul 26, 2012 at 2:06 PM, Aniruddha Basak <[email protected]> wrote: > If A is symmetric, I observe from small tests in Matlab, the eigenvalues > and singular values are same (might not always be true) in magnitude. > Similarly eigenvectors and columns of V are same but some have opposite sign. > > Now, there are two questions, > 1. How to retrieve eigenvectors with correct sign from U or V? > 2. If we ignore this difference, and perform the next steps of spectral > kmeans, will the results be correct? > > > Aniruddha > > > -----Original Message----- > From: Dan Brickley [mailto:[email protected]] > Sent: Thursday, July 26, 2012 1:56 PM > To: [email protected] > Cc: [email protected] > Subject: Re: eigendecomposition of very large matrices > > > > > > On 26 Jul 2012, at 21:21, Aniruddha Basak <[email protected]> wrote: > >> Actually that's my confusion. I don't need the eigenvectors of AA' >> but of A ! >> If I can find a matrix B such that BB'=A, then from the SVD >> decomposition of B we can get the eigenvectors of A. But how to get B in >> that case ? > > Does it help us if A is symmetric? > > Dan > >> >> Aniruddha >> >> >> -----Original Message----- >> From: Dmitriy Lyubimov [mailto:[email protected]] >> Sent: Thursday, July 26, 2012 1:18 PM >> To: [email protected] >> Subject: Re: eigendecomposition of very large matrices >> >> See http://en.wikipedia.org/wiki/Singular_value_decomposition, >> "relation to eigenvalue decomposition". >> >> Depending on what you consider source for the eigendecompostion, AA' >> or A'A, the eigenvectors would be column vectors of U or V respectively. >> >> On Thu, Jul 26, 2012 at 1:12 PM, Aniruddha Basak <[email protected]> >> wrote: >>> Hi, >>> I am trying to use SSVD instead of Lanczos, as a part of Spectral Kmeans. >>> However, I could not find the relation between the eigenvectors and U, V >>> matrices. >>> Can someone please tell me, how to retrieve the eigenvectors from SSVD >>> decomposition ? >>> >>> Thanks, >>> Aniruddha >>> >>> >>> >>> -----Original Message----- >>> From: Dmitriy Lyubimov [mailto:[email protected]] >>> Sent: Thursday, July 19, 2012 10:53 PM >>> To: [email protected] >>> Subject: RE: eigendecomposition of very large matrices >>> >>> Pps if you do insist on having a lot of k then you'll benefit from smaller >>> hdfs block size, not larger. >>> On Jul 19, 2012 10:50 PM, "Dmitriy Lyubimov" <[email protected]> wrote: >>> >>>> Yeah I see OK. Both two experiments conducted with mahout ssvd I am >>>> familiar with dealt with input size greater than yours element wise, >>>> on a quite modest node count. So i don't think your input size will >>>> be a problem. But the number of singular values will be. >>>> >>>> But I doubt any input will yield anything useful beyond k=200 but >>>> statistical noise. Even if you have a good decay of the singular values. >>>> But I bet you don't need that many. You can fit significantly more >>>> 'clusters' on a 'fairly small' dimensional space. >>>> On Jul 19, 2012 6:33 PM, "Aniruddha Basak" <[email protected]> wrote: >>>> >>>>> Thanks Dmitriy for your reply. >>>>> The matrix I am working on, has 10-20 non zero entries per row. So >>>>> its very sparse. >>>>> I am trying to do spectral clustering which involves eigen-decomposition. >>>>> I am wondering whether anyone has tried to do spectral clustering >>>>> using mahout for very large affinity matrix (input). >>>>> >>>>> Aniruddha >>>>> >>>>> >>>>> -----Original Message----- >>>>> From: Dmitriy Lyubimov [mailto:[email protected]] >>>>> Sent: Thursday, July 19, 2012 6:28 PM >>>>> To: [email protected] >>>>> Subject: Re: eigendecomposition of very large matrices >>>>> >>>>> very significant sparsity may be a problem though for -q >=1 parameters. >>>>> Again, depends on the hardware you have and the # of non-zero >>>>> elements in the input. but -q=1 is still the most recommended setting >>>>> here. >>>>> >>>>> >>>>> On Thu, Jul 19, 2012 at 6:20 PM, Dmitriy Lyubimov >>>>> <[email protected]> >>>>> wrote: >>>>>> you may try SSVD. >>>>>> https://cwiki.apache.org/confluence/display/MAHOUT/Stochastic+Sing >>>>>> u >>>>>> lar >>>>>> +Value+Decomposition >>>>>> >>>>>> but 4k eigenvectors (or, rather, singular values) is kind of still >>>>>> a lot though and may push the precision out of the error estimates. >>>>>> I don't we had precision study for that many. Also need quite a >>>>>> bit of memory to compute that (not to mention flops). More >>>>>> realistically you probably may try 1k singular values . You may >>>>>> try more if you have access to more powerful hardware than we did >>>>>> in the studies but distributed computation time will grow at about >>>>>> k^1.5, i.e. faster than linear, even if you have enough nodes for the >>>>>> tasks. >>>>>> >>>>>> -d >>>>>> >>>>>> On Thu, Jul 19, 2012 at 6:12 PM, Aniruddha Basak >>>>>> <[email protected]> >>>>> wrote: >>>>>>> Hi, >>>>>>> I am working on a clustering problem which involves determining >>>>>>> the largest "k" eigenvectors of a very large matrix. The >>>>>>> matrices, I work on, are typically of the order of 10^6 by 10^6. >>>>>>> Trying to do this using the Lanczos solver available in Mahout, I >>>>>>> found it is very slow and takes around 1.5 minutes to compute >>>>>>> each >>>>> eigenvectors. >>>>>>> Hence to get 4000 eigenvectors, it takes 100 hours or 4 days !! >>>>>>> >>>>>>> So I am looking for something faster to solve the "Eigen decomposition" >>>>>>> problem for very large sparse matrix. Please suggest me what >>>>>>> should I >>>>> use ? >>>>>>> >>>>>>> >>>>>>> Thanks, >>>>>>> Aniruddha >>>>>>> >>>>> >>>>
