IncPACK contains implementations of low-rank incremental Singular Value Decomposition (SVD) methods for approximating the dominant or dominated singular values and vectors of a matrix.
Many applications require only a subset of the singular values and vectors of a given matrix. Numerous approaches exist for this:
- Full SVD with truncation — computationally wasteful, and often prohibitively expensive.
- Transform to symmetric eigenvalue problem — apply an iterative eigensolver to the relevant part of the spectrum, then back-transform to singular value solutions. The most popular approach for large, sparse matrices.
- Specialized SVD solvers, including:
- JD-SVD (Hochstenbach) — analogous to the Jacobi-Davidson eigensolver; uses a Newton method wrapped by a Davidson-type two-sided subspace acceleration strategy. Best applied to finding either the largest or smallest singular values.
- Riemannian optimization — the dominant singular vectors can be computed by maximizing a function over a Riemannian manifold.
- Neural network methods — various Hebbian/neural-network-based approaches.
- Low-rank incremental SVD methods — approximate the dominant or dominated singular subspaces in a pass-efficient manner. These methods are the focus of this package.
- Sketching/Randomized methods — See (eg) HMT11, Woodruff14, or Murray23.
IncPACK currently provides a MATLAB implementation, released under an open-source modified BSD license. An MPI-based C++ implementation is available in the Trilinos RBGen package (development branch).
The package provides a single solver: an implementation of the Sequential Karhunen-Loeve algorithm (Levy and Lindenbaum, 2000). As described by the original authors, this solver computes approximations for the left singular subspace. It has been extended to also compute the right singular subspace and to improve approximations via multiple passes through the data matrix.
- Simple restarting
- Steepest descent (variant A)
- Steepest descent (variant B)
An introduction to the family of incremental/streaming SVD methods:
- C. G. Baker. Incremental Methods for Computing Extreme Singular Subspaces. 2012 SIAM Conference on Applied Linear Algebra, Valencia, Spain, June 2012.
Foundational papers describing the family of low-rank incremental SVD methods:
- B. S. Manjunath, S. Chandrasekaran, and Y. F. Wang. "An eigenspace update algorithm for image analysis". IEEE Symposium on Computer Vision, 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". 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.
- M. 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, describing a generalization of these methods with an emphasis on efficient implementations:
- C. G. Baker. "A block incremental algorithm for computing dominant singular subspaces". 2004.
Further analysis, including 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.
- Chris Baker, NVIDIA
- Kyle Gallivan, Florida State University
- Paul Van Dooren, Université catholique de Louvain
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"
- GenRTR — a Riemannian trust-region solver that can be used to compute the dominant SVD.
Modified BSD. See LICENSE.