ResearchBlog‎ > ‎

[Software] Incremental SVD Packages

posted Mar 8, 2012, 11:34 AM by Teng-Yok Lee   [ updated Aug 21, 2013, 2:00 PM ]

2 MATLAB implementations:

1. C. G. Baker's algorithm*, which was also implemented by C. G. Baker.
http://www.math.fsu.edu/~cbaker/IncPACK/
*C. G. Baker. "A block incremental algorithm for computing dominant singular subspaces". 2004

2. M. Brand's algorithm+, which was implemented by David Wingate.
http://www.mit.edu/~wingated/resources.html (Search for the section Incremental SVD updates)
+Matthew Brand, "Fast low-rank modifications of the thin singular value decomposition".
 

A C/C++ implementation:

This version is based on the algorithm by Gu*. According to this post, the author is Attila Axt.

http://sourceforge.net/projects/isvd/

Quoted from the official website:

Description

Incremental singular value decomposition (SVD) routines for the Gnu Scientific Library (GSL). It outperforms the standard batch-SVD methods in running/windowed SVD applications.

* M. Gu, Studies in numerical linear algebra, Ph.D. thesis, Yale University, New Haven, CT, USA (1993) (ACM Portal). I cannot find the original thesis, but I found the following related publications:
  1. M. Gu, S. C. Eisenstat, Downdating the singular value decomposition, Research Report, YALEU/DCS/RR-939, Dept. of Computer Science, Yale University, New Haven, CT, 1993, May (link).
  2. M. Gu, S. C. Eisenstat, A stable and fast algorithm for updating the singular value decomposition, Research Report, YALEU/DCS/RR-966, Dept. of Computer Science, Yale University, New Haven, CT, 1993, June
  3. Ming Gu, Stanley C. Eisenstat, A stable and efficient algorithm for the rank-one modification of the symmetric eigenproblem, SIAM J. Matrix Anal. Appl., 15 (1994), 1266–1276 [ISI] [ZentralblattMath] [MathRev]

Notes when compiling isvd


First, gsl is required.

Second, when configuring isvd, use the following command s.t. configure can find gsl:

env CPPFLAGS="-I</gsl/to/path>/include" LDFLAGS="-L</gsl/to/path>/lib" ./configure CPPFLAGS=-I</gsl/to/path>/include CFLAGS=-I</gsl/to/path>/include LDFLAGS=-L</gsl/to/path>/lib



Comments