Computational Science Stack Exchange is a question and answer site for scientists using computers to solve scientific problems. It only takes a minute to sign up.
Sign up to join this community
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.
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.
