The Problem

• Compute the full SVD and truncate the parts that are not needed. This is wasteful, and often times, prohibitively expensive.
• Transform the singular value problem into a symmetric eigenvalue problem, apply an iterative eigensolver to compute the relevant part of the spectrum, back-transform the eigenvalue solutions into the desired singular value solutions. This is the most popular approach for large SVD problems, especially where the data matrix is sparse.
• Attack directly the singular value problem via some specialized solver:
  • JD-SVD method of Hochstenbach. This is analogous to the Jacobi-Davidson eigensolver. It operates by using a Newton method to compute an update to the current approximation that attempts to set the SVD problem residuals to zero. This is wrapped by a Davidson-type two-sided subspace acceleration strategy, which serves to improve the rate of convergence and globalize the Newton method. JD-SVD is best applied to finding either the largest or smallest singular values.
  • The computation of the dominant singular vectors can be characterized as the maximization of a particular function over a Riemannian manifold. This allows the application of a number of Riemannian optimization techniques. See the GenRTR page for more information. There is currently no analogous method for computing the smallest singular values.
  • There exist a number of efforts which compute the dominant singular vectors via a neural network. Try this or this.
  • A family of so-called low-rank incremental SVD methods allow the approximation of the dominant or dominated singular subspaces in a pass-efficient manner. These methods are the focus of this webpage.

Incremental SVD Publications

The most recent talk of Baker provides a good introduction the the familiy of incremental/streaming SVD methods:

• Incremental Methods for Computing Extreme Singular Subspaces, presented at the 2012 SIAM Conference on Applied Linear Algebra, Valencia, Spain, June 2012.

The family of low-rank incremental SVD methods were originally described in the following papers:

• B. S. Manjunath, S. Chandrasekaran, and Y. F. Wang. "An eigenspace update algorithm for image analysis". In IEEE Symposium on Computer Vision, page 10B Object Recognition III, 1995.
• A. Levy and M. Lindenbaum. "Sequential Karhunen-Loeve basis extraction and its application to images". IEEE Transactions on image processing, 9(8):1371-1374, August 2000.
• Y. Chahlaoui, K. Gallivan, and P. Van Dooren. "An incremental method for computing dominant singular spaces". In Computational Information Retrieval, pages 53-62. SIAM, 2001.
• M. Brand. "Incremental singular value decomposition of uncertain data with missing values". In Proceedings of the 2002 European Conference on Computer Vision, 2002.
• Y. Chahlaoui, K. Gallivan, and P. Van Dooren. "Recursive calculation of dominant singular subspaces". SIAM J. Matrix Anal. Appl., 25(2):445-463, 2003.
• Matthew Brand. "Fast low-rank modifications of the thin singular value decomposition". Linear Algebra and its Applications, 415(1):20-30, May 2006.

Baker's thesis described a generalization of these methods, with an emphasis on efficient implementations:

• C. G. Baker. "A block incremental algorithm for computing dominant singular subspaces". 2004

The following papers present further analysis of these methods, including descriptions of the multipass methods:

• Baker, Gallivan, Van Dooren. "Low-Rank Incremental Methods for Computing Dominant Singular Subspaces" Linear Algebra and its Applications, 436(8):2866-2888, April 2012.
• Baker, Gallivan, Van Dooren. "Low-Rank Incremental Methods for Computing Dominant Singular Subspaces", 10th Copper Mountain Conference on Iterative Methods, 2008.

IncPACK Software

IncPACK contains implementations of the low-rank incremental SVD methods for the approximation of either the largest or smallest singular values of a matrix, along with the associated singular vectors. Currently, the package provides a single solver, an implementation of the of the Sequential Karhunen-Loeve (Levy and Lindenbaum, 2000). This solver, as described by the authors, computes approximations for the left singular subspace. It has been modified to compute also the right singular subspace, and to improve on these approximations via multiple passes through the data matrix.

IncPACK currently provides implementations in MATLAB, released under an open-source modified BSD license. An MPI-based implementation in C++ is available in Trilinos in the RBGen package (development branch only). A beta-implementation for NVIDIA GPUs using CUDA is available below.

Downloads

Authors

The authors of the codes are:

• Chris Baker, Oak Ridge National Laboratory
• Kyle Gallivan, Florida State University
• Paul Van Dooren, Université catholique de Louvain

Funding

Funding for this work came in part from:

• National Science Foundation Award 032944: "Collaborative Research: Model Reduction of Dynamical Systems for Real Time Control"
• National Science Foundation Award 9912415: "Efficient Algorithms for Large Scale Dynamical Systems"

Related software

• The JD Gateway contains information on the JD-SVD method, which can be used to compute the dominant or dominated SVD.
• The GenRTR package provides a solver for computing the dominant SVD.
• The RTRESGEV package provides eigensolvers, which can be used to compute dominant or dominated SVD.