3
$\begingroup$

Hello all,

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).

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.

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.

Cheers!

$\endgroup$

2 Answers 2

4
$\begingroup$

The people aspiring for the Netflix prize like incremental SVDs. See

  1. https://issues.apache.org/jira/browse/MAHOUT-371
  2. 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. (ONLINE)
  3. M. Brand. Fast online svd revisions for lightweight recommender systems. In Proceedings of the 3rd SIAM International Conference on Data Mining, 2003. and his tech report

Have you tried searching the ACM digital library for parallel SVD or singular value decomposition?

EDIT1 based on new input : See the following two papers by Hall, Marshall and Martin

  1. Merging and Splitting Eigenspace Models (Section 3)
  2. On Adding and Subtracting Eigenspaces with EVD and SVD
$\endgroup$
2
  • $\begingroup$ That looks good, thanks! I'll have to sift through the arcane notations and see what it all really means, but I guess that answers my question. If their solution requires some non-obvious, computationally infeasible tricks deep down (I have to implement it, so I'll find out soon enough), I'll reopen the question again, this time more specifically :-) $\endgroup$
    – RedSnow
    Jul 17, 2010 at 6:07
  • $\begingroup$ @RedSnow: It'd be good to hear how you got on with this? $\endgroup$
    – mc0e
    Nov 10, 2013 at 4:22
1
$\begingroup$

You may also be interested in SLEPc 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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.