most recent 30 from http://mathoverflow.net 2013-05-24T18:09:14Z http://mathoverflow.net/feeds/question/32158 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/32158/distributed-incremental-svd RedSnow 2010-07-16T12:02:16Z 2010-08-06T16:58:59Z

<p>Hello all,</p> <p>I need some theoretical pointers (formulas, articles, online links) on how to merge Singular Value Decompositions (SVD) of two matrices (two different sets of observations over the same set of features).</p> <p>That is, I have two SVDs: $A=U_A*S_A*V^T_A$ and $B=U_B*S_B*V^T_B$ and want to know SVD $A|B=U_{A|B}*S_{A|B}*V_{A|B}$. The original matrices $A$ and $B$ are unavailable, the solution must make use of the $U_A, S_A, V_A, U_B, S_B, V_B$ matrices only.</p> <p>I need this because I want to implement a distributed version of incremental SVD: have several computation nodes work on different sets of observations independently, and then merge their results into one.</p> <p>Cheers!</p>

http://mathoverflow.net/questions/32158/distributed-incremental-svd/32177#32177 SandeepJ 2010-07-16T14:20:23Z 2010-07-16T21:35:42Z

<p>The people aspiring for the <a href="http://en.wikipedia.org/wiki/Netflix_Prize" rel="nofollow">Netflix prize</a> like incremental SVDs. See </p> <ol> <li><a href="https://issues.apache.org/jira/browse/MAHOUT-371" rel="nofollow">https://issues.apache.org/jira/browse/MAHOUT-371</a></li> <li>B.M. Sarwar, G.Karypis, J.A. Konstan, and J. Reidl. Incremental singular value deocmposition algorithms for highly scalable recommender systems. In Proceedings of the Fifth International Conference on Computer and Information Technology (ICCIT), 2002. (<a href="http://www.grouplens.org/papers/pdf/sarwar_SVD.pdf" rel="nofollow">ONLINE</a>)</li> <li>M. Brand. Fast online svd revisions for lightweight recommender systems. In Proceedings of the 3rd SIAM International Conference on Data Mining, 2003. and <a href="http://www.merl.com/publications/TR2002-024/" rel="nofollow">his tech report</a></li> </ol> <p>Have you tried searching the <a href="http://portal.acm.org/portal.cfm" rel="nofollow">ACM digital library</a> for parallel SVD or singular value decomposition? </p> <p><strong>EDIT1 based on new input</strong> : See the following two papers by Hall, Marshall and Martin </p> <ol> <li><a href="http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.51.804" rel="nofollow">Merging and Splitting Eigenspace Models</a> (Section 3)</li> <li><a href="http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.9.1496" rel="nofollow">On Adding and Subtracting Eigenspaces with EVD and SVD</a></li> </ol>

http://mathoverflow.net/questions/32158/distributed-incremental-svd/34787#34787 Jed 2010-08-06T16:58:59Z 2010-08-06T16:58:59Z

<p>You may also be interested in <a href="http://www.grycap.upv.es/slepc/" rel="nofollow">SLEPc</a> which is a widely used package offering parallel algorithms for computing a few singular values and vectors (and eigensystems). It scales to very large problems and hundreds of thousands of cores.</p>