Take the 2-minute tour ×
Computational Science Stack Exchange is a question and answer site for scientists using computers to solve scientific problems. It's 100% free, no registration required.

I would like to do evolving factor analysis using the SVD:

Given $m \times n$ data matrix $\mathcal{A}$, and for each $i$ from 1 to $m$, I want to calculate the singular values of:

$$\mathcal{A}\left[1:i,\ 1:n\right]$$

This would be much faster if there was a way to update the computed SVD after adding a row to $\mathcal{A}$.

I am quite sure such algorithms do exist: is there a open implementation available for Python? Pointers to an open implementation in C or Fortran would also be useful.

share|improve this question
2  
I couldn't understand your initial description of the problem so I tried to clarify, please revert if you think I got it wrong. –  Aron Ahmadia Jul 2 '12 at 18:33
    
Thanks for your edits! –  tillsten Jul 3 '12 at 5:09
add comment

1 Answer 1

up vote 7 down vote accepted

Algorithms for rank-1 updates of the SVD (also called incremental SVD) do exist, but I haven't been able to find a LAPACK-like implementation anywhere.

The one I've seen mentioned repeatedly is that of Brand (2003). Judging from this website, it seems as though Brand's algorithm is relatively simple to implement using existing LAPACK and BLAS routines as building blocks, which could perhaps explain why none of the big names has bothered to write a specialized implementation.

You can find a MATLAB implementations of various algorithms here, here, and here. The last link, to IncPACK, also mentions a C++ implementation buried within a development branch of Trilinos.

A Python implementation of Brand's algorithm (from a 2006 paper of his) can be found buried in the svdAddCols method of the LsiModel class of the gensim package, version 0.5.0. (Note: I could not find this method in gensim version 0.8.4; a similar method, svdUpdate is present in gensim version 0.7.4.)

A different algorithm, by Gu, is implemented in the package isvd, which is in C or C++ (haven't looked at the source to tell which; I arrived at this project from the link here, which discusses compilation flags for isvd). Another C++ (unfortunately, Windows-based) implementation is buried within a Netflix recommendation algorithm here; Netflix recommendation algorithms seem to use incremental SVD frequently, and might be another potential source of implementations.

That's the best I could do with my Google-fu.

share|improve this answer
    
Thanks, i will have a look at all your links. –  tillsten Jul 4 '12 at 13:15
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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